递归函数设计技巧

列举了一些较为简单的题

HZOJ-235 递归实现指数型枚举

int arr[15];
void print(int n)
{
    for (int i = 0; i <= n; i++)
    {
        if (i != 0)
            cout << " ";
        cout << arr[i];
    }
    cout << endl;
    return;
}
void f(int i, int j, int n)
{
    if (j > n)
        return;
    for (int k = j; k <= n; k++)
    {
        arr[i] = k;
        print(i);
        f(i + 1, k + 1, n);
    }
}
int main()
{
    int n;
    cin >> n;
    f(0, 1, n);
    return 0;
}

HZOJ-236 递归实现组合型枚举

void print_one_result(int n) {
    for (int i = 0; i < n; i++) {
        if (i) cout << " ";
        cout << arr[i];
    }
    cout << endl;
    return ;
}

void f(int i, int j, int n, int m) {
    if (i == m) {
        print_one_result(m);
        return ;
    }
    for (int k = j; k <= n && m - i - 1 <= n - k; k++) {
        arr[i] = k;
        f(i + 1, k + 1, n, m);
    }
    return ;
}

int main() {
    int n, m;
    cin >> n >> m;
    f(0, 1, n, m);
    return 0;
}

HZOJ-237 递归实现排列型枚举

int arr[10], vis[10] = {0};

void print_one_result(int n) {
    for (int i = 0; i < n; i++) {
        if (i) cout << " ";
        cout << arr[i];
    }
    cout << endl;
    return ;
}

void f(int i, int n) {
    if (i == n) {
        print_one_result(n);
        return ;
    }
    for (int k = 1; k <= n; k++) {
        if (vis[k]) continue;
        arr[i] = k;
        vis[k] = 1;
        f(i + 1, n);
        vis[k] = 0;
    }
    return ;
}

int main() {
    int n;
    cin >> n;
    f(0, n);
    return 0;
}

HZOJ-239 不规则的街道

分形系统

假设,现在已计算得到对应区域点在原图中的坐标为(x, y)
当前城市等级为 n,原图等级为 n-1,边长为 L=$2^{n-1}$

分为①②③④四个区域

例:12号点
位于③区域
12-8=4
f(1,4)=(1,0)
(1,0)+(2,2)=(3,2)

①:所有编号减 0,等价于原图顺时针旋转90度,再做轴对称,所有坐标加 (0, 0)
②:所有编号减 4,等价于原图,所有坐标加 (0, n)
③:所有编号减 8,等价于原图,所有坐标加 (n, n)
④:所有编号减12,等价于原图逆时针旋转90度,再做轴对称,所有坐标加 (n, 0)

N*M的矩阵,坐标为(x, y),坐标从0开始,经过如下操作:
顺时针旋转90度:(x, y) $\rightarrow$ (y, N-x-1)
逆时针旋转90度:(x, y) $\rightarrow$ (M-y-1, x)
轴对称:(x, y) $\rightarrow$ (x, M-y-1)

①:(x, y) $\rightarrow$ (y, L-x-1) $\rightarrow$ (y, x)
②:(x, y) $\rightarrow$ (x, y+L)
③:(x, y) $\rightarrow$ (x+L, y+L)
④:(x, y) $\rightarrow$ (L-y-1, x) $\rightarrow$ (L-y-1,L-x-1) $\rightarrow$ (2L-y-1,L-x-1)

#define S(a) ((a) * (a))

void f(long long n, long long s, long long &x, long long &y) {
    if (n == 1) {
        if (s == 1) x = 0, y = 0;
        else if (s == 2) x = 0, y = 1;
        else if (s == 3) x = 1, y = 1;
        else x = 1, y = 0;
        return;
    }
    long long L = 1LL << (n - 1);
    long long block = L * L;
    long long xx, yy;
    if (s <= block) { // 1: (x, y) -> (y, x)
        f(n - 1, s, xx, yy);
        x = yy, y = xx;
    } else if (s <= 2 * block) { // 2: (x, y) -> (x, y + L)
        f(n - 1, s - block, xx, yy);
        x = xx, y = yy + L;
    } else if (s <= 3 * block) { // 3: (x, y) -> (x + L, y + L)
        f(n - 1, s - 2 * block, xx, yy);
        x = xx + L, y = yy + L;
    } else { // 4: (x, y) -> (2 * L - y - 1, L - x - 1)
        f(n - 1, s - 3 * block, xx, yy);
        x = 2 * L - yy - 1, y = L - xx - 1;
    }
    return;
}

int main() {
    long long t, n, s, d;
    cin >> t;
    while (t--) {
        cin >> n >> s >> d;
        long long sx, sy, dx, dy;
        f(n, s, sx, sy);
        f(n, d, dx, dy);
        cout << round(10 * sqrt(S(sx - dx) + S(sy - dy))) << endl;
    }
    return 0;
}
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇