C语言名题精选百则——数字问题
?
?
C语言名题精选百则——数字问题
尊重他人的劳动，支持原创
这篇博文，D.S.Qiu将对《C语言名题精选百则》第二章进行整理推出，本章一共16个问题，不光只是书上的名题，还会依据互联网的资源进行不断补充，加强（由于匆忙，暂时还只是罗列的过程，不过很快就有深度的发掘）。如果你有建议、批评或补充，请你不吝提出（email:gd.s.qiu@gmail.com，或者直接在本文末评论）。你的支持和鼓励，我将渐行渐远！
这篇博文整理的太艰难了，其中一度想放弃，个人觉得难度有点大，如果没有需求驱动的话，很难读下去，但最终为了保持文章的完整性，还是硬着头皮去截图整理。这16个问题主要经常的是对质数的求解，因式分解，整数自乘（快速求解），Fibonacci数（快速求解），二项式求解（快速求解），阶乘（快速求解），这些都是数论或者组合数学的基本内容，但要通过计算机基本求解的算法赴复杂度过高，文中给出了相应的快速算法，对有需求的读者来说，还是可以喜出望外的（也只是大概的理解了下），应该还有更多精彩的求解方法（日后定当补充）。终于写完了，没有你的支持和鼓励，很难继续下去，下一篇是《排列，组合与集合》。
问题2.1 Armstrong 数（ARMS1.C，ARMS2.C )
在三位的正整数中，例如abc,有一些可以满足a3+b3+c3?= abc的条件，也就是说， 各个位数的立方和正好是该数的本身，这些数称为Armstrong数。试编写一个程序来求出
所有的三位Armstrong数。
?
【说明】
这是个常见的问题，许多课本、习题集都有。解决的基本方法就在于有没有办法从一 个三位数中把它的3个位数取出（例如，把379分解成3、7与9),或者在已知3个位数 时把该三位数算出来（例如，已知百位为5,十位为1,个位为9，则三位数为519)。
另一个变形是给出一个数，证明它是否为一个Armstromg数。这两者类似，由自己产 生的数可以永远控制在三位，但是后者却一定要去测试它是不是三位数。
如何测试一个数是否为三位数呢？有的书中介绍这样一种方法（见程序UGLY.C), 使用对数log()以及指数exp()函数，不仅如此，还要用四舍五入（在C语言中只好加上 0.5再转型成整数）。为什么？原来只是在取出输入数据的某一个位数而已。一个简单的 程序写得如此复杂，大多数初学者恐怕都很难看明白。在此给出一个提示，千万不要重蹈覆辙。
(1)如果要确认x是个五位数，就看x/100000是否为零。如果为零，那么x的位数 不会超过五位。接着再检查x是否真的是五位，这就要看：
(x % 100000)/10000
是否为零，如果不为零，这个值就是x中从右向左数第五位数的值；如果是零，x就最多只能有四位而已。为什么？因为x%100000是把x用100000去除的余数，值在0?99999 之间，正是x的右边五位，再用10000去除，那就是第五位的值了；如果x是五位数，那么这个位数就一定大于1,如程序2-1所示。
?
【程序】
程序2-1（UGLY.C）
?
试编写一个程序进行破解（看下面的规则说明）。
?
【说明】
数字谜的规则是这样的：
(1)不同的英文字母表示不同的数字。因此，题目中最右边一行的T、Q、E就是不同的数。
(2)每一个数最左边一位不是0。所以上面的谜题中，V、C、T都不是0。
(3)上面的题目是加，那就表示VINGT这个五位数与CINQ这个四位数的两倍相加 后，会得到TRENTE这个六位数，并且数字的安排如谜语所示。
在解这些数字谜时，很多人都会不知不觉地用最笨拙的方法，因此可能执行好几分钟, 甚至好几小时都得不到结果。就以上题为例，它一共有9个不同的字母，因此耗用10个数 字符号中的9个，很多人就会写出下面的形式，如程序2-2所示。
【程序】
程序2-2
for(v=1;v<=9;v++)
for(I=0;I<=9;I++)
……
for(E=0;E<=9;E++)
{
VINGT=……;
CINQ=……;
TRENTE=……;
if(TRENTE == VINGT + CINQ +CINQ)
{
……
}
}
如果用这个程序，那么也许一两个小时也不一定能够算出结果，因为在最内层循环中 的if 一共要执行将近10^9,近一亿次，所以这是最笨的方法。通常，用一点小学算术知识就可以节省大量的计算时间。换言之，可以用四则运算来 找出某个字母值的范围（如偶数、奇数、5?9、3或4等，而不是0?9),范围越小，程序的工作就越少，执行起来就越快。
?
不妨从这一点出发，就本题而给出一些提示：
(1)因为3个位数相加，最大就是9+9+9=27,如果从这一个位数的右边一位会有进 位，那么这个进位就最多是2，所以3个位数再加上进位的最大值是29，所以该位数和是 9，而进位是2。
(2)现在看V那位，加上进位之后得到TR,因为V最大是9，进位最大是2，所以 TR的最大值是11。因为T是结果的第一位，所以不能是0，因此只好是1;但结果前两位 是TR, TR最大是11，现在T是1,于是R只能是0。注意，如果R是2?9中任意一个， 那就表示没有从R到T的进位，因而T就是0 了。所以从一点看来，两个值就固定了，即T=1， R=0。
(3)再来看V，V—定大于8。为什么？千位数的进位最大是2,要一个数加上2而 有两位数，那么这个数不就至少是8吗？
(4)看个位数的E。它是由T加上两个Q得来的，已知T是1,而2Q—定是偶数, 所以E是个奇数。
就用这4点提示，T与R的循环就不必了； E的循环有3、5、7、9 (注意，T是1, E 就不能用1); V的循环只能用8与9。还没有决定的就剩下I、N、G、C与Q5个，所以循 环就有7层，I、N、G与Q为0?9; C为2?9 (因为C是第一位，不能是0，也不能是1， 因为T是1)，E是3、5、7、9； V是8与9，所以最内层的if就执行了 10^4x7x4x2次而已，于是用这个方法写成的程序所花的时间大约是前面所提到的：
10^4x7x4x2/10^9=0.056%
因此可以看到节省了多少时间。
思考一下，另外是否还有其他可以节省时间的方法呢?
?
问题实现
?
?个乘法吗？
问题实现
?【问题实现】
可以用这个观点来编写程序。
问题实现?
?问题实现
?对于每一个c(n，r)而言，如果它左上角与右上角的两个元素都算出来了，那么就可以 算出C(n，r)。所以，在图11-10中可以从左上到右下一列一列地算，或者是从右上到左下一行一行地算；换句话说，可以算出C(2，1),C(3，2),C(4，3),再算C(3，1)，C(4，2)，C(5，3)，…；但也可以先算 C(2，1)，C(3，1),C(4，1),C(5，1)，C(6，1),再算 C(3，2)，C(4，2)，…，C(7，2)等。此处打算用一列一列的方式。在开始时准备一个数组c[],其容量至少有r,它的内容全是1，代表图11-10中的C(0，0)，C(1，1),…,C(r,r)。接下来，对每一个c[i]而言，1≤r≤r, 令 c[i]为 c[i】+c[i-1],即为：C(2，1) = C(1，0) + C(1，1), C(3,2) = C(2,l) + C(2,2)。注意，在算C(2，l)时，它要用到C(1,0),这个值是1,目前在c[0];也要用到C(1，1),现在在c[1]，因此把c[0]与c[1]相加再放回c[1],于是c[1]中的值就变成C(1,1)了。程序CNR_ADD.C就是用这个观点写成的，在一开始把一个足够大的数组c[]定成1，然后，就把计算的工作循环做n-r次，正好是图11-10中的第一列，第二列,…，第列的计算；对每一列而言，自第一个元素起把它与前一个元素相加。因此计算完后，c[r]中就是 C(n,r)的值。?问题实现?如果使用的语言或编译程序（如Ada)有可以计算任意位整数加、减、乘、除的能力 的话，能够从这个式子找出一个只需要与化成正比的乘法次数求所有C(n，i)，i=0，l，…，n的办法吗？下面假设C语言具有此能力，来编写程序。
【说明】假设给了一个n,能否找出一种方法，用上式把所有C(n，i)，i=0，1，…，n都算出来，这是主题。为了方便起见，不妨假设所有运算都可以处理任意位数的整数，而不会造成溢位； 其实有一些语言，如Ada,或是一些链接库都提供了这个能力，所以不必认为如此的假设 不切实际。应用也还不少，包含有把71计算到一百万位，测定任何整数是不是质数以及做 分解因式的程序，还有就是处理多项式；后者在计算几何学、机器人等应用上都有相当重 要的地位。提示：式子中有一个p，它的值是多少？这是要事先决定的。此外，能在大约
?
?
?
?【问题实现】
??问题2.14快速阶乘运算（FACTLOG2.C )在问题2.13中己经看过用与
【说明】
要做到只用
【程序】
程序2-5
unsigned long fact(int m, int n)if (m==n)return melsereturn fact(m,(m+n)/2)*fact((m+n)/2+1,n);}请问这个程序快了没？没有，不但如此，反而慢了。）2?成正比的程序。另外，我们知道计算所有C(n，i)也不过 用了?
?
?问题实现
??
问题2.15更快的阶乘算法（FACTLOGC )请仔细研究问题2.14,编写出一个只用与
【说明】
问题2.14的解法是有进一步改良的余地的。用递归方法，通过下式计算:
?一样，它也有一些被重复计算的地方，如果能够把它找出来，程序自然就可以做到乘 法个数与lon2n成正比的地步。仔细做一做问题2.14的习题（1)与习题（2),必会有所收获。?
?
?问题实现
??问题2.16连续整数的固定和(GIVENSUM.C )编写一个程序，读入一个正整数，把所有那些连续的和为给定的正整数的正整数找出 来。例如，如果输入27,发现2?7、8?10、13与14的和是27，这就是解答；如果输入 的是10000,应该有18?142、297?1328、388?412、1998?2002这4组。注意，不见得 一定会有答案，譬如说4、16就无解；另外，排除只有一个数的情况，否则每一个输入就 都至少有一个答案，就是它自己。
【说明】任何人看到这个题目都会马上想到一个办法，把所有的和算出来，与输入比较。曾经看到过如下的一个解法，如程序2-6所示。
【程序】
程序 2-6 (NOT_GOOD.C)#include <stdio.h>#include <stdlib.h>void main(void){char line[100]; long sum, i, j, n;gets(line); n = atol(line);for (i = 1; i <= n/2; i++){for (sum = i, j = i + 1; j <= n/2+1; j++){sum += j;if (sum == n)printf {" \n%ld - %ld", i, j);}}}它的做法是先固定一个i、sum变量，接着令j从i+1起变化，每次都把j的值加到sum 中，因此sum中的值就是这些连续整数的和。因此令i从1变到n/2 (n是给定的 值)，而j从i+1变到n/2+l，如果有一个和与n相同，就显示i与j，表示n的值是i到j 这一串连续的正整数的和。为什么i要从1到n/2?很简单，如果i是n/2,下一个数就是 n/2+l,于是这两个（连续的）数的和n/2+(n/2+l)=n+l就大于n，所以i最多只能到n/2; 同理可以说明j不可以大过n/2+1。这个程序当然是对的，但运行太慢了！用1_作为输入，它一共执行了 311.71秒， 也就是5分钟多；但事实上，这个题目可以在不到一秒之内得出答案，而且当输入1000000 (100万）时，也不过用178.12秒（3分钟）左右而己，相比之下NOTLCOOD.C的效率实 在太低了。问题出在什么地方？加法次数太多了。在上面的程序中，i与j的关系永远满足?1≤i≤n ,??i + 1≤j≤n + 1, i<j;每一组i与j都会做一次加法，所以就一共做了大约n2/8个加法（这是个近似值)；当n=10000时，就大约是1250万个。不过，一个好程序员应该研究是否有更好的方法存在，事实上就有一个，大约需要2n个加法就足够了，能想得出来吗？下面是几点有用的提示：(1)如果在求和时是用 i+ (i + 1)+…+j表示，那么i≤n/2;这是上面提过的。(2)如果某个和i+(i+1)+…+比给定的值大，那么把和变小，但仍然维持是一串连 续整数的和时，拿掉j变成i + (i + 1)+…十(j-1),不如拿掉i变成(i + l) +…+j。为什么？因为j比i大，拿掉j，和就下降太快了，不如拿掉i,再慢慢降低（能用数学来证明吗？）(3)如果和 i+ (i +1) +…+j比给定值小，加上j +1变成的i+…+j十(j-1);道理同前。有了这几点，编程应该不会是件难事了。
问题实现"\n\nSorry,?there?is?NO?solution?at?all.");??
?
成正比的乘法次数求所有C(n，i)，i=0，l，…，n的办法吗？下面假设C语言具有此能力，来编写程序。
）2?成正比的程序。另外，我们知道计算所有C(n，i)也不过 用了?
