第三章

5. 汉诺塔问题

解：

// 从a经过b移动n个盘子到c
void hanoi(int n, int a, int b, int c) {
    hanoi(n-1, a, c, b);
    print(f"从{a}移1个到{c}");
    hanoi(n-1, b, a, c);
}

6. 整数分划问题

求一个函数P(n)，返回n的不同分划数。
例子：P(6)=6，因为有如下分划：
6
5+1
4+2
3+3
2+2+2
1+1+1+1+1+1
解：
设函数Q(a,b)，表示a的所有加数不大于b的分划数。P(n)=Q(n,n)。
则：
(1) Q(a,a)=Q(a,a-1)+1
如，6的分划有6=6和其他不含6的分划。
(2) Q(a,b)=Q(a,b-1)+Q(a-b,b)
a的不大于b分划包括含b的和不含b的，第一项表示不含b的，第二项表示含b的。

7. 输出每一位（低到高）

解：

void print_digits(int n){
    if(n<10) print(n);
    else
    {
        print(n % 10);
        print_digits(n / 10);
    }
}

8. 输出每一位（高到低）

解：

void print_digits(int n){
    if(n<10) print(n);
    else
    {
        print_digits(n / 10);
        print(n % 10);
    }
}

10. 输出组合（m选k）

例如，m=5, k=3,输出结果为
5 4 3
5 4 2
5 4 1
5 3 2
5 3 1
5 2 1
4 3 2
4 3 1
4 2 1
3 2 1
解：

int K = 0;
int a[100];

// comb(m,k)负责固定a[k]，递归下一层comb(m-1,k-1)固定a[k-1]，
// 回来后a[k]取下一个值。
// 如果k等于1，就不需要递归，直接输出每个值即可。
void comb(int m, int k) {
    // mm 是下一层递归的m 
    for(int i = m; i >=k ; i--) {
        a[k] = i;
        if(k > 1)
            comb(i-1,k-1);
        else {
            for(int j = K; j > 0; j--)
                std::cout << a[j] << " ";
            std::cout << "\n";
        }
    } 
}

void C(int m, int k)
{
    K = k;
    memset(a, 0, sizeof(a));
    comb(m,k);
}

20. 趣味矩阵

a[i][j]表示第i行第j列。

35. 称重问题

有10箱子产品，每箱1000件，正品每件100克，其中有几箱为次品，每件次品比正品轻10克，问是否能只称1次，就找出哪些是次品。
解：
第一箱取1个，第二箱取2个，第三箱取4个，第四箱取8个...

比如轻了70g，就是第1、2、3箱是次品。

36. 狼找兔子问题/循环移数问题

循环移数的问题：有n个数，循环后移k个位置。只有1个辅助空间。如何移动？

解：
可以分成gcd(n,k)组，每组内的数进行循环移动。如n=12,k=8时，分组如下：

1 2 3 4 1 2 3 4 1 2 3 4

据此编码即可。

狼找兔子问题：有一个狼要找兔子吃，狼每隔k个洞找一下，有n个洞，找到头就返回去，请问兔子躲哪里永远不会被找到？

同理，还是分组，只要兔子不在狼那一组就没事。如果gcd(n,k)=1即n,k互质，则兔子必死。

39. 中国余数问题

\[x \equiv r_1(\mod t_1) \]

\[x \equiv r_2(\mod t_2) \]

\[x \equiv r_3(\mod t_3) \]

求\(n\)。
解：

\[n=t_2t_3k_1r_1+ t_1t_2k_2r_2+ t_1t_2k_3r_3 \]

其中：\(k_i, i=1,2,3\)应该满足以下条件

\[t_2t_3k_1 \equiv 1(\mod t_1) \]

\[t_1t_2k_2 \equiv 1(\mod t_2) \]

\[t_1t_2k_3 \equiv 1(\mod t_3) \]

找到这三个系数带入即可得\(n\)。最后结果模一个\(t_1t_2t_3\)。

40. 上台阶问题

有n阶台阶，一次能上1级或2级，求有几种上法。
解：
倒过来想：
\(f(n) = f(n-1) + f(n-2)\)

第四章

倒推法

5. 穿越沙漠问题

车子穿越1000m的沙漠，总装油量500升，耗油量1L/km，请问如何建立油站最省油（求油站的位置和油量）？

解：

• 汽车是一点一点“挪”过去的，即在起点和第一站之间往返建立好第一站后，就只用第一站的油在第一站和第二站之间往返（再也不回起点了），建立好第二站后，就只用第二站的油在第二站和第三站之间往返（再也不回第一站了）......

• 建立好下一站后，上一站的油刚好用完，车内恰好没油，一切从0开始。

• 每次向终点出发时汽车应该满载，没有为什么，贪婪的思想。

• 倒着推，从终点到倒数第一站，一定是500m才能让第一站的油刚好用完。倒数第一站到倒数第二站之间的路程要走三次，其中两次是向终点出发，应该满载，所以倒数第二站存1000L

• 接下来看距离，因为倒数第一站的油(500L)全部来自倒数第二站，所以倒数第二站还剩下1000-500=500L，这500L全部用于往返倒数一二站，这段路走了3次，所以距离为500/3km。

蛮力法vs聪明法

12. 狱吏问题

让狱吏n次通过一排锁着的n间牢房，第k次通过，转动第k,2k,3k,...间牢房的钥匙（切换开/关状态，即开变关、关变开）。问经过n次后，哪些牢房的锁是开的?

解：(不用蛮力的方法)
利用因子个数，比如4号门，它的因子有1、2、4，说明它在第1、2、4轮会切换状态。切换了3次，最终应该是开的（假设n>=4）。

那么求一个门最终开不开，就是求它的不同因子的个数，奇数就开，偶数就不开。

然后我们发现，只有完全平方数拥有奇数个不同因子，因为因子都是成对出现的，“不同因子的个数”为奇数，说明有一对因子是一样的。

最后发现，解决这个问题，只需找到不大于n的完全平方数即可。

分治法

14. 残缺棋盘

解：
分治算法，简单说就是三个小块把空当凑到中间，正好再填一个。

15. 求数列的最大子列和

解：
分治算法，将数列等分成2段，则最大子列的位置分为3中情况。

• 全部在左段
• 全部在右段
• 跨左右段

前两种情况递归解决，第三种情况从中间向两侧各找最大子列，然后合并即是整体的最大子列。

17. 找数组中第二小的数

解：
分治算法，分成两段，各求最小2个数。然后再4个数中选出最小的2个。

18. 找数组中第k小的数

解：
用快速排序的第一步“切分“。先得到一个锚点p，p左边的数都比p小，右边的都比p大。
然后数p左边有几个，记作l。

如果l=k-1那么p就是答案
如果l>k-1，那么就递归在左半边找第k个数
如果l<k-1，那么就递归在右半边找第k-p个数

贪心法

通过取局部最优达到全局最优的策略。

19. 删数字

解：
若各位数字递增，则删除最后一个数字，否则删除第一个递减区间的首字符。然后回到串首，按上述规则再删除下一个数字。重复以上过程s次即可。

23. 取数游戏

2个人轮流取2n个数中的n个数（全程明牌），取数之和大者为胜。请问先手如何永远胜利？
解：
先手先看奇位置上的数的和大还是偶位置上的数的和大，哪个大就确保自己只取这些数，对面取不到这些数即可。换言之，不让对手取两个连续的数就行。

动态规划

递归+保存结果 的

25. 投资问题

将n元分配给m个项目，\(g_i(x)\)为第i个项目分配得x元所得到的利润。求最大利润的分配方案。
解：
设\(f_i(x)\)为将资源\(x\)分配给前\(i\)个项目所得到的最大利润，则：

\[f_1(x)=g_1(x) \]

\[f_i(x)=max\{g_i(k)+f_{i-1}(x-k)\}_{k=0}^{x} \]

26. 矩阵连乘问题

解：

构造数组\(r_i\)。表示第\(i+1\)个矩阵的行数和第\(i\)个矩阵的列数。

矩阵\(Mi...Mj\)的最小乘法次数

\[\begin{equation} f(i,j)= \begin{cases} 0 & {i=j} \\ r_ir_{i+1}r_{i+2} & {i=j-1} \\ min(f(i,k)+f(k+1,j)+r_ir_{k+1}r_{j+1})& {i\le k < j} \\ \end{cases} \end{equation} \]

27. 最长子序列

第五章

子集树：

第1层 1号元素选还是不选
第2层 2号元素选还是不选
...

共\(2^n\)个叶子结点

排列树：

第1层 1号元素放哪（n个选择）
第2层 2号元素放哪（n-1个选择）
...
共\(n!\)个叶子结点

活结点：还可以展开的结点
E结点：正在展开的结点
死结点：无法再展开的结点

8皇后问题