分析：本题只要求得到一个字符串x，使得x的某两个排列分别是两个给定字符串的子串，并没有要求x的某一个排列同时是两个给定字符串的子串。理解清楚这一点非常重要——如果题目要求是后者，则问题就演变成了求两个字符串的最长（非连续的）公共子序列（LCS）的问题，难度陡升。more笔者开始就是没有看清这一点，得出了错误的答案——不过，从另一个角度讲，如果是后者应该怎样解答呢？笔者的答案在
继续阅读 »
分析：n1 * m1 + n2 * m2 = n (a)
以上不定方程的“非负整数”解可以用7.4节提到的解线性同余式的方法求得。再根据
C = m1 * c1 + m2 * c2 (b)
由(a)(b)两式得： more
继续阅读 »
分析：分解质因数，求各位数字之和。如果担心当n等于10亿时，Smith数的计算会使unsigned int溢出，可以先试算一下——其实不小于10亿的最小Smith数是1000000165，不算大。more
```cpp
include
include
include
include
继续阅读 »
分析：试验表明：任何一个不小于8的整数都可以表示为四素数之和，且答案可能不唯一；另外，如果按照“从大到小”的顺序来找四个素数会比较快地找到解。因此有如下解：先用筛选质数法列出10000000以内的素数，然后用回溯法把一个整数n分解为四素数之和——在回溯时从不超过n的最大素数开始向前尝试。more
继续阅读 »
分析：最直接的想法是如下代码：
cpp
bool on = false;
for (int i = 1; i <=n; i++)
if (n % i == 0)
on = !on
但n最大可达数十亿，此法计算效率太低！那么能不能倒过来想：n可以被多少个不大于n的数整除？很容易给n分解质因数：more
继续阅读 »
分析：由于n的值可达20亿，所以把f(n)的值记录在数组里是不现实的，因此通过递推式计算f(n)也是不现实的，何况f(n)的递推式也很难得出。假设s(n)为数列f(n)的前n项和，则由数列性质可知：more
f(s(n)) = n
继续阅读 »
分析：这道题不简单，迄今为止我还没看到一个可以严谨地证明其正确性的程序——尽管答案本身是正确的。more比如
这种通过观察数列差得到的方法，虽然找出了启发性的递推公式，但不能据此给出归纳证明；又比如这种方法，其证明所依赖的“数列差d(n)所形成的数列是非递减数列”也是没有得到证明的。笔者找到了一篇关于4柱汉诺塔的论文——对这个问题进行了深入研究并给出了解的封闭形式。笔者自己最终没能给出一个AC的答案，以下解通过简单地比较找出k值，由于计算量过大而超时。但读者仍能利用此程序观察k或者差值的变化——来验证一些假设吧。
继续阅读 »
分析：6.4节《其他计数序列》里提到关于整数拆分的算法，比如，3有三种拆分法：1+1+1，1+2，3。设f(n, k)表示把n拆成一系列不大于k的整数的方法数，则
f(n, k) = f(n, k - 1) + f(n - k, k) (a)
继续阅读 »
分析：《具体数学》第一章有个类似的问题：n条直线最多可以把一个平面分成多少块？如果n条直线把平面分成了m块，那么再加一条直线最多新增n个交点，这n个交点把新的直线分成了n+1段，每一段都把原来的一块区域分成了2块，也就是说新增了n+1块区域。由此有递推公式：
继续阅读 »
分析：6.4节《其他计数序列》里给出了Fibonacci数列的封闭形式，提示里也说“能否借助封闭形式来避免高精度算数”，但高精度算数还是无法避免。理由如下：more
F(n) = (a ^ n - b ^ n) / c
其中a，b，c为常数：
继续阅读 »