设计师做单页的网站/宁波网站推广优化外包

这是⼀道「递归」算法的经典题⽬，我们可以先从「最简单」的情况考虑：

• 假设n = 1 ，只有⼀个盘⼦，很简单，直接把它从a 中拿出来，移到 c 上；
• 如果n = 2呢？这时候我们就要借助b了，因为⼩盘⼦必须时刻都在⼤盘⼦上⾯，共需要3步
  （为了⽅便叙述，记a中的盘⼦从上到下为1，2 ）：
  a. 1 号盘⼦放到b 上；
  b. 2 号盘⼦放到c 上；
  c. 1 号盘⼦放到c 上。
  ⾄此，c 中的盘⼦从上到下为1号，2号
• 如果n = 3呢？这是我们需要⽤到n = 2时的策略，将a上⾯的2个盘⼦挪到b上，再将最⼤的盘⼦挪到c上，最后将b上的2个盘⼦挪到c上。其中转移2个盘⼦的策略正好是n = 2的⽅式。
  在处理n - 1 的时候，问题⼜转化成了相同的⼦问题，此时就可以⽤递归帮助我们解决。
• 由此我们可以类⽐出n 为任意值的处理⽅式：
  • 当n > 1时：将a上⾯的n - 1个盘⼦挪到b上，再将最⼤的盘⼦挪到c上，最后将b上的n - 1个盘⼦挪到c上就完成了所有步骤；
    在处理n - 1 的时候，问题⼜转化成了相同的⼦问题，此时就可以⽤递归帮助我们解决。
  • 当n = 1 时：直接放到⽬标柱⼦上。
    设计递归函数（从重复⼦问题⼊⼿）：
• 重复⼦问题：将x 个盘⼦，从begin 柱⼦转移到end 柱⼦上，其中通过tmp 柱⼦作为中转；
• 具体操作：
  a. 先将beign 上⾯x - 1 个盘⼦借助end 转移到tmp 上；
  b. 再把begin 最下⾯⼀个盘⼦放在end 上；
  c. 最后把tmp 上⾯x - 1 个盘⼦借助begin 转移到end 上。

#include <bits/stdc++.h>
using namespace std;int n;
char a, b, c;//把x柱子上的n个盘子，借助y的帮助，全部放到z上
void dfs(int n, char x, char y, char z)
{if(n == 0) return; dfs(n-1, x, z, y);printf("%c->%d->%c\n", x, n, z);dfs(n-1, y, x, z);
}int main()
{ios::sync_with_stdio(false);cin.tie(0);cin >> n >> a >> b >> c;dfs(n, a, c, b);return 0;
}

⼀个简单的模拟题。这道题⽤循环也是可以模拟出来的，但是可以锻炼⼀
下递归解法。
整个模拟过程：

1. 抽出第13 堆最上⾯的牌x ：
2. 把第x 堆的最后⼀张拿出来；
3. 拿到这张牌之后，重复2 过程，直到拿到13
   上述三步整个⼀循环，⼀直循环4 次，直到把13 堆上⾯的牌拿完。
   重复⼦问题：

• 拿到⼀张牌x 之后，把第x 堆最后⼀张拿出来

#include <bits/stdc++.h>
using namespace std;const int N = 15;int n = 13, m = 4;
int a[14][5];
int cnt[N];void dfs(int x)
{if (x == 13) return;int t = a[x][cnt[x]];cnt[x]--;dfs(t);
}int main()
{ios::sync_with_stdio(false);cin.tie(0);for (int i = 1; i <= n; i++){cnt[i] = 4;for (int j = 1; j <= m; j++){char ch; cin >> ch;if (ch >= '2' && ch <= '9') a[i][j] = ch - '0';else if (ch == 'A') a[i][j] = 1;else if (ch == 'J') a[i][j] = 11;else if (ch == 'Q') a[i][j] = 12;else if (ch == 'K') a[i][j] = 13;else a[i][j] = 10;}}for (int i = 1; i <= m; i++){dfs(a[n][i]);        }int ret = 0;for (int i = 1; i <= n; i++){if (cnt[i] == 0) ret++;        }cout << ret << endl;return 0;
}

重复⼦问题：处理每⼀棵⼦树：

1. 确定出该⼦树的类型；
2. 然后从中间分开，先处理左⼦树，再处理右⼦树；
3. 然后打印该⼦树的类型
   如何快速判断出该⼦树的类型？因为我们要求的是⼀段区间内1的个数，我们可以利⽤「前缀和」数组求出这段区间和，然后在查询某段区间时，判断⼀下此时的区间和：

• 如果等于区间⻓度，说明是I 类型；
• 如果等于0 ，说明是B 类型；
• 否则就是F 类型。

#include <bits/stdc++.h>
using namespace std;const int N = 11;
int n;
int f[1 << N]; // 2^Nvoid dfs(int left, int right)
{if (left > right) return;char ret;int sum = f[right] - f[left-1];if (sum == 0) ret = 'B';else if (sum == right - left + 1) ret = 'I';else ret = 'F';if (left == right){cout << ret;return;}int mid = (left + right) / 2;dfs(left, mid); dfs(mid+1, right);cout << ret;
}int main()
{ios::sync_with_stdio(false);cin.tie(0);cin >> n;n = 1 << n;for (int i = 1; i <= n; i++){char ch; cin >> ch;int t = 0;if (ch == '1') t = 1;f[i] = f[i-1] + t;}dfs(1, n);return 0;
}