C/C++语言经典、实用、趣味程序设计编程百例精解（7）
61.1~9组成三个3位的平方数
将1、2、3、4、5、6、7、8、9九个数字分成三组，每个数字只能用一次，即每组三个数不允许有重复数字，也不许同其它组的三个数字重复，要求每组中的三位数都组成一个平方数。
*问题分析与算法设计
本问题的思路很多，这里介绍一种简单快速的算法。
首先求出三位数中不包含0且是某个整数平方的三位数，这样的三位数是不多的。然后将满足条件的三位数进行组合，使得所选出的3个三位数的9个数字没有重复。
程序中可以将寻找足条件的三位数的过程和对该三位数进行数字分解的过程结合起来。
*程序说明与注释
1. #include <stdio.h> 2. int main() { 3. int a[20], num[20][3], b[10]; /*a:存放满足条件的三位数*/ 4. /*若不是10 的倍数，则分解三位数*/ 5. /*分解该三位数中的每一个数字*/ 6. int i, j, k, m, n, t, flag; 7. printf("The 3 squares with 3 different digits each are:\n"); 8. for (j = 0, i = 11; i <= 31; i++) /*求出是平方数的三位数*/ 9. if (i % 10 != 0) /*若不是10的倍数，则分解三位数*/ 10. { 11. k = i * i; /*分解该三位数中的每一个数字*/ 12. num[j + 1][0] = k / 100; /*百位*/ 13. num[j + 1][1] = k / 10 % 10; /*十位*/ 14. num[j + 1][2] = k % 10; /*个位*/ 15. if (!(num[j + 1][0] == num[j + 1][1] || num[j + 1][0] == num[j + 1][2] || 16. num[j + 1][1] == num[j + 1][2])) /*若分解的三位数字均不相等*/ 17. a[++j] = k; /*j:计数器，统计已找到的满足要求的三位数*/ 18. } 19. for (i = 1; i <= j - 2; ++i) /*从满足条件的三位数中选出三个进行组合*/ 20. { 21. b[1] = num[i][0]; 22. b[2] = num[i][1]; 23. b[3] = num[i][2]; 24. for (t = i + 1; t <= j - 1; ++t) { 25. b[4] = num[t][0]; /*取第t个数的三位数字*/ 26. b[5] = num[t][1]; 27. b[6] = num[t][2]; 28. for (flag = 0, m = 1; !flag && m <= 3; m++) /*flag:出现数字重复的标记*/ 29. for (n = 4; !flag && n <= 6; n++) /*判断两个数的数字是否有重复*/ 30. if (b[m] == b[n]) 31. flag = 1; /*flag=1:数字有重复*/ 32. if (!flag) 33. for (k = t + 1; k <= j; k++) { 34. b[7] = num[k][0]; /*取第k个数的三位数字*/ 35. b[8] = num[k][1]; 36. b[9] = num[k][2]; 37. for (flag = 0, m = 1; !flag && m <= 6; m++) /*判断前两个数字是否*/ 38. for (n = 7; !flag && n <= 9; n++) /*与第三个数的数字重复*/ 39. if (b[m] == b[n]) 40. flag = 1; 41. if (!flag) /*若均不重复则打印结果*/ 42. printf("%d,%d,%d\n", a[i], a[t], a[k]); 43. } 44. } 45. } 46. }
*运行结果
The 3 squares with 3 different digits each are:
361,529,784
*思考题
将1、2、3、4、5、6、7、8、9九个数字分成二组，每个数字只能用一次，一组形成一个5位数，另一组形成一个4位数，使得前者为后者的n倍。求所有满足条件的5位数和4位数。(注意：N的最大值等于68,68以内的某些N也是不可能的。不可能的N值包括：1、10、11、20、21、25、30、31等共32个。)
62.由8个整数形成奇特的立方体
任意给出8个整数，将这8个整数分别放在一个立方体的八个顶点上，要求每个面上的四个数之和相等。
*问题分析与算法设计
简化问题：将8个顶点对应数组中的8个元素，将“每个面上的四个数之和皆相等”转换为数组无素之间和的相等关系。这里的关键在于正确地将立方体的8个顶点与数组的8个元素对应。
可以利用简单的穷举方法建立8个数的全部排列。
*程序说明与注释
1. #include <stdio.h> 2. #include <stdlib.h> 3. int main() { 4. int a[9], ii = 0, i, a1, a2, a3, a4, b1, b2, b3, b4, flag; 5. for (i = 1; i <= 8; i++) /*输入个数*/ 6. { 7. printf("Please enter [%d]number:", i); 8. scanf("%d", &a[i]); 9. ii += a[i]; 10. } 11. printf("******************************************\n"); 12. if (ii % 2) /*和为奇数则输入的8个数不可用*/ 13. { 14. printf("Sorry they can't be constructed required cube!\n"); 15. exit(0); 16. } 17. for (flag = 0, a1 = 1; a1 <= 8; a1++) /*flag:完成标记.flag=1;表示完成*/ 18. for (a2 = 1; a2 <= 8; a2++) /*采用八重循环建立八个整数的全排列*/ 19. if (a2 != a1) /*前两个数不能相同*/ 20. for (a3 = 1; a3 <= 8; a3++) 21. if (a3 != a2 && a3 != a1) /*前三个数不能相同*/ 22. for (a4 = 1; a4 <= 8; a4++) if (a4 != a3 && a4 != a2 && 23. a4 != a1) /*前四个数不能相同*/ 24. for (b1 = 1; b1 <= 8; b1++) if (b1 != a4 && b1 != a3 && 25. b1 != a2 && b1 != a1) /*不能相同*/ 26. for (b2 = 1; b2 <= 8; 27. b2++) if (b2 != b1 && b2 != a4 && b2 != a3 && b2 != a2 && 28. b2 != a1) for (b3 = 1; b3 <= 8; 29. b3++) if (b3 != b2 && b3 != b1 && 30. b3 != a4 && b3 != a3 && 31. b3 != a2 && b3 != a1) 32. /*不能取相同的数*/ 33. for (b4 = 1; b4 <= 8; 34. b4++) if (b4 != b2 && b4 != b1 && b4 != b3 && b4 != a4 && 35. b4 != a3 && b4 != a2 && 36. b4 != a1) if (a[b1] + a[b2] + a[b3] + a[b4] == 37. ii / 2 && 38. a[a1] + a[a2] + a[b1] + a[b2] == 39. ii / 2 && 40. a[a1] + a[a4] + a[b1] + a[b4] == 41. ii / 2) { 42. flag = 1; 43. goto out; /*满足条件则将flag置1后退出*/ 44. } 45. out: 46. if (flag) { 47. printf("They can be constructed required cube as follow:\n"); 48. printf(" /%2d…………/%2d\n", a[a4], a[a3]); 49. printf(" %2d/…………%2d/|\n", a[a1], a[a2]); 50. printf(" | | | |\n"); 51. printf(" | | | |\n"); 52. printf(" | %2d| | |%2d\n", a[b4], a[b3]); 53. printf(" /……………./\n"); 54. printf(" %2d/………….%2d/\n", a[b1], a[b2]); 55. } else 56. printf("Sorry they can't be constructed required cube!\n"); 57. }
*运行结果
Please enter [1] number:20
Please enter [2] number:45
Please enter [3] number:39
Please enter [4] number:25
Please enter [5] number:29
Please enter [6] number:7
Please enter [7] number:3
Please enter [8] number:2
Sorry they can't be constructed required cube!
*思考题
程序中建立全排列的方法效率太低，算法虽然简单但程序过于冗余。请读者自行设计新的算法完成同样的工作。
63.减式还原
编写程序求解下式中各字母所代表的数字，不同的字母代表不同的数字。
PEAR
- ARA
——–
PEA
*问题分析与算法设计
类似的问题从计算机算法的角度来说是比较简单的，可以采用最常见的穷举方法解决。程序中采用循环穷举每个字母所可能代表的数字，然后将字母代表的数字转换为相应的整数，代入算式后验证算式是否成立即可解决问题。
*程序说明与注释
1. #include <stdio.h> 2. int main() { 3. int p, e, a, r; 4. for (p = 1; p <= 9; p++) /*从1到9穷举字母p的全部可能取值*/ 5. for (e = 0; e <= 9; e++) /*从0到穷举字母e的全部可能取值*/ 6. if (p != e) /*p不等于e*/ 7. for (a = 1; a <= 9; a++) /*从0到9穷举字母a的全部可能取值*/ 8. if (a != p && a != e) 9. for (r = 0; r <= 9; r++) /*从0到9穷举字母r的全部可能取值*/ 10. if (r != p && r != e && r != a && 11. p * 1000 + e * 100 + a * 10 + r - (a * 100 + r * 10 + a) == 12. p * 100 + e * 10 + a) { 13. printf(" PEAR %d%d%d%d\n", p, e, a, r); 14. printf(" -ARA - %d%d%d\n", a, r, a); 15. printf("…………………….\n"); 16. printf(" PEA %d%d%d\n", p, e, a); 17. } 18. }
*运行结果
PEAR 1098
- ARA - 989
———- ——
PEA 109
*思考题
请复原下面的和式。不同的字母代表不同的数字。
SEVEN 82524 82526
THREE 19722 19722
+ TWO 答案： + 106 + 104
———- ———– ———–
TWELVE 102352 102352
64.乘式还原
A代表数字0到9中的前五个数字，Z代表后五个数字，请还原下列乘式。
A Z A
× A A Z
————
A A A A
A A Z Z
Z A A
————
Z A Z A A
*问题分析与算法设计
问题本身并不复杂，可以对乘式中的每一位使用穷举法，最终可以得到结果。本题的关键在于怎样有效的判断每个部分积的每一位是否满足题意，这一问题处理不好，编写的程序会很长。程序实现中采用了一个判断函数，通过传入函数的标志字符串对所有的数进行统一的判断处理。
*程序说明与注释
1. #include <stdio.h> 2. void print(long a, long b, long s1, long s2, long s3); 3. int jud(long q, char *pflag); 4. int main() { 5. long i, j, k, l, m, n, term, t1, t2, t3; 6. int flag; 7. for (i = 0; i <= 4; ++i) /*被乘数的第一位*/ 8. for (j = 5; j <= 9; ++j) /*被乘数的第二位*/ 9. for (k = 0; k <= 4; ++k) /*被乘数的第三位*/ 10. { 11. term = 100 * i + 10 * j + k; /*被乘数*/ 12. for (flag = 0, n = 0; n < 4 && !flag;) /*乘数的第一位*/ 13. flag = jud((t3 = ++n * 100 * term) / 100, "001"); /*判断第三个部分积*/ 14. if (flag) { 15. for (flag = 0, m = 0; m < 4 && !flag;) /*乘数的第二位*/ 16. flag = 17. jud((t2 = ++m * 10 * term) / 10, "1100"); /*判断第二个部分积*/ 18. if (flag) { 19. for (flag = 0, l = 5; l < 9 && !flag;) /*乘数的第三位*/ 20. flag = jud(t1 = ++l * term, "0000"); /*判断第一个部分积*/ 21. if (flag && jud(t1 + t2 + t3, "00101")) /*判断乘式的积*/ 22. print(term, n * 100 + m * 10 + l, t1, t2, t3); 23. } 24. } 25. } 26. } 27. void print(long a, long b, long s1, long s2, long s3) /*打印结果*/ 28. { 29. printf("\n %ld\n", a); 30. printf("*) %ld\n", b); 31. printf("………………….\n"); 32. printf(" %ld\n %ld\n %ld\n", s1, s2 / 10, s3 / 100); 33. printf("………………….\n"); 34. printf(" %ld\n", a * b); 35. } 36. int jud(long q, char *pflag) /*判断一个数的每一位是否满足要求的判断函数*/ 37. /*q:需要判断的数。pflag:标志字符串，A用1表示，Z用0表示。标志串排列顺序：个十百…*/ 38. { 39. while (q != 0 && *pflag != NULL) /*循环判断对应位的取值范围是否正确*/ 40. if (*pflag - '0' != (q % 10 >= 5 ? 1 : 0)) /*标志位与对应的位不符，返回0*/ 41. return 0; 42. else { 43. q /= 10; 44. ++pflag; /*若相符则取下一位进行判断*/ 45. } 46. if (q == 0 && *pflag == NULL) /*q的位数与标志字符串的长度相同时，返回1*/ 47. return 1; 48. else 49. return 0; 50. }
*运行结果
3 7 2
× 2 4 6
———-
2 2 3 2
1 4 8 8
7 4 4
————
9 1 5 1 2
*思考题
E代表数字0到9中的偶数数字，O代表奇数数字，请还原下列乘式。
E E O 2 8 5
× O O 答案 × 3 9
———– ———–
E O E O 2 5 6 5
E O O 8 5 5
———– ———–
O O O O O 1 1 1 1 5
65.乘式还原(2)
有乘法算式如下：
○○○
× ○○
————
○○○○
○○○○
————
○○○○○
18个○的位置上全部是素数(1、3、5或7)，请还原此算式。
*问题分析与算法设计
问题中虽然有18数位，但只要确定乘数和被乘数后经过计算就可确定其它的数位。
乘数和被乘数共有5个数位，要求每个数都是质数。完全可以采用穷举的方法对乘数和被乘数进行穷举，经过判断后找出答案。但是这种方法给人的感觉是“太笨了”，因为组成的数字只是质数(4个)，完全没有必要在那么大的范围内进行穷举，只需要试探每一位数字为质数时的情况即可。
采用五重循环的方法实现对于5个数字的穷举，前面的许多例题中都已见过。循环实现简单易行，但嵌套的层次太多，需要穷举的变量的数量直接影响到循环嵌套的层数，这种简单的实现方法缺少技巧性。本例的程序中给出了另外一种同样功能的算法，该算法的实现思想请阅读程序。
程序中并没有直接对质数进行穷举，而是将每个质数与1到4顺序一一对应，在穷举时为处理简单仅对1到4进行穷举处理，待要判断产生的乘积是否满足条件时再利用一个数组完成向对应质数的转换。请体会程序中的处理方法。程序中使用的算法实际上是回朔法。
*程序说明与注释
1. #include <stdio.h> 2. #define NUM 5 /*需要穷举的变量数目*/ 3. #define C_NUM 4 /*每个变量的值的变化范围*/ 4. int a[NUM + 1]; /*为需要穷举的变量开辟的数组*/ 5. /*a[1]:被乘数的百位，a[2]：十位,aa[3]:个位 a[4]:被乘数的十位 a[5]:个位*/ 6. int b[] = {0, 2, 3, 5, 7}; /*存放质数数字的数组，不使用第0号元素*/ 7. int f(long sum); 8. int main() { 9. int i, not_finish = 1; 10. i = 2; /*i:将要进行处理的元素的指针下标。设置初始值*/ 11. a[1] = 1; /*为第1号元素设置初始值*/ 12. while (not_finish) /*not_finish:程序运行没结束标记*/ 13. { 14. while (not_finish && i <= NUM) 15. /*处理包括第i个元素在内的后续元素，找出当前条件下的一种各个变量的一种可能的取值方法*/ 16. if (a[i] >= C_NUM) /*当要处理的元素取超过规定的C_NUM时*/ 17. if (i == 1 && a[1] == C_NUM) 18. not_finish = 0; /*若1号元素已经到C_NUM，则处理全部结束*/ 19. else 20. a[i--] = 0; /*将要处理的元素置0，下标-1(回退一个元素)*/ 21. else 22. a[i++]++; /*当前元素值加1后下标指针加1*/ 23. if (not_finish) { 24. long int sum1, sum2, sum3, sum4; /*定义临时变量*/ 25. sum1 = b[a[1]] * 100 + b[a[2]] * 10 + b[a[3]]; /*计算被乘数*/ 26. /*利用数组的下标与质数的对应关系完成序号1到4向质数的转换*/ 27. sum2 = sum1 * b[a[5]]; /*计算乘数个位与被乘数的部分积*/ 28. sum3 = sum1 * b[a[4]]; /*计算乘数十位与被乘数的部分积*/ 29. if (sum2 >= 2222 && sum2 <= 7777 && f(sum2) && sum3 >= 2222 && 30. sum3 <= 7777 && f(sum3)) 31. /*判断两部分积是否满足题目条件*/ 32. if ((sum4 = sum2 + sum3 * 10) >= 22222 && sum4 <= 77777 && f(sum4)) 33. /*判断乘式的积是否满足题目条件*/ 34. { 35. printf(" %ld\n", sum1); /*若满足题意，则打印结果*/ 36. printf("* %d%d\n", b[a[4]], b[a[5]]); 37. printf("……………………\n"); 38. printf(" %ld\n", sum2); 39. printf(" %ld\n", sum3); 40. printf("……………………\n"); 41. printf(" %ld\n", sum4); 42. } 43. i = NUM; /*为穷举下一个可能取值作准备*/ 44. } 45. } 46. } 47. int f(long sum) /*判断sum的每一位数字是否是质数，若不是返回0，若是返回1*/ 48. { 49. int i, k, flag; /*flag=1:数字是质数的标记*/ 50. while (sum > 0) { 51. i = sum % 10; /*取个位的数字*/ 52. for (flag = 0, k = 1; !flag && k <= C_NUM; k++) 53. if (b[k] == i) { 54. flag = 1; 55. break; 56. } 57. if (!flag) 58. return 0; 59. else 60. sum = sum / 10; 61. } 62. return 1; 63. }
*运行结果
7 7 5
× 3 3
———-
2 3 2 5
2 3 2 5
———–
2 5 5 7 5
*思考题
以下乘式中，A、B、C代表一确定的数字，○代表任意数字，请复原。
A B C 2 8 6
× B A C × 8 2 6
————- 答案： ————
○○○○ 1 7 1 6
○○A 5 7 2
○○○B 2 2 8 8
————- —————-
○○○○○○ 2 3 6 2 3 6
66.除式还原(1)
给定下列除式，其中包含5个7，其它打×的是任意数字，请加以还原。
× 7 × ————–商
————–
除数——××| ×××××————-被除数
×7 7
————–
× 7 ×
× 7 ×
———-
× ×
× ×
———-
○
*问题分析与算法设计
首先分析题目，由除式本身尽可能多地推出已知条件。由除式本身书已知：
1、被除数的范围是10000到99999，除数的范围是10到99，且可以整除；
2、商为100到999之间，且十位数字为7；
3、商的第一位与除数的积为三位数，且后两位为77；
4、被除数的第三位一定为4；
5、 7乘以除数的积为一个三位数，且第二位为7；
6、商的最后一位不能为0，且与除数的积为一个二位数。
由已知条件就可以采用穷举的方法找出结果。
*程序说明与注释
1. #include <stdio.h> 2. int main() { 3. long int i; 4. int j, l; 5. for (i = 10000; i <= 99999; i++) /*1. i:被除数*/ 6. if (i % 1000 - i % 100 == 400) /*4. 被除数的第三位一定为4*/ 7. for (j = 10; j <= 99; j++) /*1. j: 余数*/ 8. if (i % j == 0 && (l = i / j) % 100 >= 70 && l % 100 < 80 && 9. l % 10 != 0 && l > 100 && l <= 999) 10. /*1. 可以整除&& 2.商l在100到999之间且十位数字为7&&6.商的个数不能为0*/ 11. if ((j * (l % 10)) < 100 && 12. j * (l % 10) > 10) /*6. 商的个数与除数的积为二位数*/ 13. if (j * 7 % 100 >= 70 && 14. j * 7 % 100 < 80) /*5. 7乘以除数的积的第二位为7*/ 15. if (j * (l / 100) % 100 == 77 && j * (l / 100) > 100) 16. /*商的第一位与除数的积的后两位为77*/ 17. printf("%ld/%d=%d\n", i, j, l); 18. }
*运行结果
51463/53=971。
可以看作为下列算式：
9 7 1
————-
5 3| 5 1 4 6 3
4 7 7
————-
3 7 6
3 7 1
———–
5 3
5 3
———–
○
*问题的进一步讨论
在推出的已知条件中，几所有的条件都是十分明显的，换句话说，推出的已知条件就是对题目的平铺直叙。这种推已知条件的方法十分简单，并且行之有效。
*思考题
下列除式中仅给定了一个8，其它打×的位置上是任意数字，请还原。
× 8 × —————-商
—————-
除数——-×××| ××××××—————被除数
××××
—————
×××
×××
—————
××××
××××
—————
○
67.除式还原(2)
下列除式中仅在商中给定了一个7，其它打×的位置全部是任意数字，请还原。
×7××× ————-商
——————
除数 ——————-×××| ×××××××× ————-被除数
×××× ————-1)
—————
××× ————-2)
××× ————-3)
—————
×××× ————-4)
××× ————-5)
—————–
×××× ————-6)
×××× ————-7)
—————–
0
*问题分析与算法设计
这道题是不可能用单纯的穷举法求解的，一则计算时间太长，二则难于求出除式中各部分的值。
对除式进行分析，改可能多地推出限制条件：
由3)可以看出，商的第二位7乘除数得一个三位数，所以除数<=142。
由除数乘商的第一位为一个四位数可知，商的第一位只能为8或9且除数>=112。同时商的第五位也为8或9数的前四位一定<=142*9+99且>=1000+10。
由4)、5)、6)可以看出，4)的前两位一定为“10”；5)的第一位一定为“9”；6)的前两位一定在10到99之间；商的第四位一定为为0。
由 5)的第一位一定是“9”和“112”<=除数<=142可知：商的第三位可能为7或8。
由除式本身可知：商的第四位为0。
由 1)可知：除数X商的第一位应当为一个四位数。
由 5)可知：除数X商的第三位应当为一个三位数。
编程时为了方便，将被除数分解：前四位用a[0]表示，第五位用a[1]，第六位用a[2]，第七八两位用a[3];除数用变量b表示；分解商：第一位用c[0]，第五位用c[2];其它的部分商分别表示为：2)的前两位为d[0]，4)的前三位为d[1]，6)的前二位为d[2]。将上述分析用数学的方法综合起来可以表示为：
被除数： 1010<=a[0]<=1377 0<=a[1]<=9
0<=a[2]<=9 0<=a[3]<=99
除数： 112<=b <=142
商： 8<=c[0]<=9 7<=c[1]<=8 8<=c[2]<=9
2)的前两位： 10<=d[0]<=99
4)的前三位： 100<=d[1]<b
6)的前两位： 10<=d[2]<=99
1)式部分积： b*c[0]>1000
5)式部分积： 100<b*c[1]<1000
*程序说明与注释
1. #include <stdio.h> 2. int main() { 3. int a[4], b, c[3], d[4], i = 1; 4. for (a[0] = 1010; a[0] <= 1377; a[0]++) 5. for (b = 112; b <= 142; b++) 6. for (c[0] = 8; c[0] <= 9; c[0]++) 7. if (b * c[0] > 1000 && (d[0] = a[0] - b * c[0]) >= 10 && d[0] < 100) 8. for (a[1] = 0; a[1] <= 9; a[1]++) 9. if ((d[1] = d[0] * 10 + a[1] - b * 7) >= 100 && d[1] < b) 10. for (a[2] = 0; a[2] <= 9; a[2]++) 11. for (c[1] = 7; c[1] <= 8; c[1]++) 12. if (b * c[1] < 1000 && 13. (d[2] = d[1] * 10 + a[2] - b * c[1]) >= 10 && d[2] < 100) 14. for (a[3] = 0; a[3] <= 99; a[3]++) 15. for (c[2] = 8; c[2] <= 9; c[2]++) 16. if (d[2] * 100 + a[3] - b * c[2] == 0) { 17. printf("No%2d:", i++); 18. printf("%d%d%d%d%d/", a[0], a[1], a[2], a[3] / 10, 19. a[3] % 10); 20. printf("%d=", b); 21. printf("%d%d%d%d%d\n", c[0], 7, c[1], 0, c[2]); 22. } 23. }
*运行结果：
No 1:12128316/124=97809
*思考题
下列除式中“×”所在的位置全部是任意数字，请还原。
×××××
——————-
××× | ××××××××
××××
——————
××××
×××
—————
×××
×××
———–
××××
××××
———–
0
68.九位累进可除数
求九位累进可除数。所谓九位累进可除数就是这样一个数：这个数用到1到9这九个数字组成，每个数字刚好只出现一次。这九个位数的前两位能被2整除，前三位能被3整除……前N位能被N整除，整个九位数能被9整除。
*问题分析与算法设计
问题本身可以简化为一个穷举问题：只要穷举每位数字的各种可能取值，按照题目的要求对穷举的结果进行判断就一定可以得到正确的结果。
问题中给出了“累进可除”这一条件，就使得我们可以在穷举法中加入条件判断。在穷举的过程中，当确定部分位的值后，马上就判断产生的该部分是否符合“累进可除”条件，若符合，则继续穷举下一位数字；否则刚刚产生的那一位数字就是错误的。这样将条件判断引入到穷举法之中，可以尽可能早的发现矛盾，尽早地放弃不必要穷举的值，从而提高程序的执行效率。
为了达到早期发现矛盾的目的，不能采用多重循环的方法实行穷举，那样编出的程序质量较差。程序中使用的算法不再是穷举法，而是回朔法。
*程序说明与注释
1. #include <stdio.h> 2. #define NUM 9 3. int a[NUM + 1]; 4. int main() { 5. int i, k, flag, not_finish = 1; 6. long sum; 7. i = 1; 8. /*i:正在处理的数组元素，表示前i-1个元素已经满足要求，正处理的是第i个元素*/ 9. a[1] = 1; /*为元素a[1]设置初值*/ 10. while (not_finish) /*not_finish=1:处理没有结束*/ 11. { 12. while (not_finish && i <= NUM) { 13. for (flag = 1, k = 1; flag && k < i; k++) 14. if (a[k] == a[i]) 15. flag = 0; /*判断第i个元素是否与前i-1个元素重复*/ 16. for (sum = 0, k = 1; flag && k <= i; k++) { 17. sum = 10 * sum + a[k]; 18. if (sum % k) 19. flag = 0; /*判断前k位组成的整数是否能被k整除*/ 20. } 21. if (!flag) /*flag=0:表示第i位不满足要求，需要重新设置*/ 22. { 23. if (a[i] == a[i - 1]) /*若a[i]的值已经经过一圈追上a[i-1]*/ 24. { 25. i--; /*i值减1，退回处理前一个元素*/ 26. if (i > 1 && a[i] == NUM) 27. a[i] = 1; /*当第i位的值达到NUM时，第i位的值取1*/ 28. else if (i == 1 && a[i] == NUM) /*当第1位的值达到NUM时结束*/ 29. not_finish = 0; /*置程序结束标记*/ 30. else a[i]++; /*第i位的值取下一个,加1*/ 31. } 32. else if (a[i] == NUM) a[i] = 1; 33. else a[i]++; 34. } 35. else{/*第i位已经满足要求，处理第i+1位*/ 36. if (++i <= NUM){ /*i+1处理下一元素，当i没有处理完毕时*/ 37. if (a[i - 1] == NUM) a[i] = 1; /*若i-1的值已为NUM，则a[i]的值为1*/ 38. else a[i] = a[i - 1] + 1; /*否则，a[i]的初值为a[i-1]值的"下一个"值*/ 39. } 40. } 41. } 42. if (not_finish) { 43. printf("\nThe progressire divisiable number is:"); 44. for (k = 1; k <= NUM; k++) /*输出计算结果*/ 45. printf("%d", a[k]); 46. if (a[NUM - 1] < NUM) 47. a[NUM - 1]++; 48. else 49. a[NUM - 1] = 1; 50. not_finish = 0; 51. printf("\n"); 52. } 53. } 54. }
*运行结果
The progressire divisible number is: 381654729
*思考题
求N位累进可除数。用1到9这九个数字组成一个N(3<=N<=9)位数，位数字的组成不限，使得该N位数的前两位能被2整除，前3位能被3整除，……，前N位能被N整除。求满足条件的N位数。
69.魔术师的猜牌术(1)
魔术师利用一副牌中的13张黑桃，预先将它们排好后迭在一起，牌面朝下。对观众说：我不看牌，只数数就可以猜到每张牌是什么，我大声数数，你们听，不信？你们就看。魔术师将最上面的那张牌数为1，把它翻过来正好是黑桃A，将黑桃A放在桌子上，然后按顺序从上到下数手上的余牌，第二次数1、2，将第一张牌放在这迭牌的下面，将第二张牌翻过来，正好是黑桃2，也将它放在桌子上，第三次数1、2、3，将前面两张依次放在这迭牌的下面，再翻第三张牌正好是黑桃3。这样依次进行将13张牌全翻出来，准确无误。问魔术师手中的牌原始顺序是怎样安排的？
*问题分析与算法设计
题目已经将魔术师出牌的过程描述清楚，我们可以利用倒推的方法，很容易地推出原来牌的顺序。
人工倒推的方法是：在桌子上放13空盒子排成一圈，从1开始顺序编号，将黑桃A放入1号盒子中，从下一个空盒子开始对空的盒子计数，当数到第二个空盒子时，将黑桃2放入空盒子中，然后再从下一个空盒子开始对空盒子计数，顺序放入3、4、5…，直到放入全部3张牌。注意在计数时要跳过非空的盒子，只对空盒子计数。最后牌在盒子中的顺序，就是魔术师手中原来牌的顺序。
这种人工的方法是行之有效的，计算机可以模拟求解。
*程序说明与注释
1. #include <stdio.h> 2. int a[14]; 3. int main() { 4. int i, n, j = 1; /*j:数组(盒子)下标，初始时为1号元素*/ 5. printf("The original order of cards is:"); 6. for (i = 1; i <= 13; i++) /*i:要放入盒子中的牌的序号*/ 7. { 8. n = 1; 9. do { 10. if (j > 13) 11. j = 1; /*由于盒子构成一个圈，j超过最后一个元素则指向1号元素*/ 12. if (a[j]) 13. j++; /*跳过非空的盒子，不进行计数*/ 14. else { 15. if (n == i) 16. a[j] = i; /*若数到第i个空盒子，则将牌放入空盒中*/ 17. j++; 18. n++; /*对空盒计数，数组下标指向下一个盒子*/ 19. } 20. } while (n <= i); /*控制空盒计数为i*/ 21. } 22. for (i = 1; i <= 13; i++) /*输出牌的排列顺序*/ 23. printf("%d ", a[i]); 24. printf("\n"); 25. }
*运行结果
The original order of cards is:1 8 2 5 10 3 12 11 9 4 7 6 13
70.魔术师的猜牌术(2)
魔术师再次表演，他将红桃和黑桃全部迭在一起，牌面朝下放在手中，对观众说：最上面一张是黑桃A，翻开后放在桌上。以后，从上至下每数两张全依次放在最底下，第三张给观众看，便是黑桃2，放在桌上后再数两张依次放在最底下，第三张给观众看，是黑桃3。如此下去，观众看到放在桌子上牌的顺序是：
黑桃 A 2 3 4 5 6 7 8 9 10 J Q K
红桃 A 2 3 4 5 6 7 8 9 10 J Q K
问魔术师手中牌的原始顺序是什么？
*问题分析与算法设计
本题可在上题的基础上进行编程，不同的在于计数的方法和牌的张数，这些并不影响我们求解题目的思路，仍可按照倒推的方法，得到原来魔术师手中的牌的顺序。
*程序说明与注释
1. #include <stdio.h> 2. int a[27]; 3. int main() { 4. int i, n, j = 1; 5. a[1] = 1; /*初始化第一张牌*/ 6. printf("The original order of cards is:(r:rad b:block):\n"); 7. for (i = 2; i <= 26; i++) { 8. n = 1; 9. do { 10. if (j > 26) 11. j = 1; /*超过最后一个元素则指向1号元素*/ 12. if (a[j]) 13. j++; /*跳过非空的盒子，不进行计数*/ 14. else { 15. if (n == 3) 16. a[j] = i; /*若数到第3个空盒子，则将牌放入空盒中*/ 17. j++; 18. n++; /*对空盒计数，数组下标指向下一个盒子*/ 19. } 20. } while (n <= 3); /*控制空盒计数为3*/ 21. } 22. for (i = 1; i <= 26; i++) /*输出牌的排列顺序*/ 23. { 24. printf("%c", a[i] > 13 ? 'r' : 'b'); 25. printf("%d ", a[i] > 13 ? a[i] - 13 : a[i]); 26. if (i == 13) 27. printf("\n"); 28. } 29. printf("\n"); 30. }
*运行结果
The original order of cards is:(r:rad b:black):
b1 r6 b10 b2 r12 r3 b3 b11 r9 b4 r7 b12 b5
r4 r13 b6 b13 r11 b7 r5 r1 b8 r8 r10 b9 r2
