C/C++语言经典、实用、趣味程序设计编程百例精解（8）
71.约瑟夫问题
这是17世纪的法国数学家加斯帕在《数目的游戏问题》中讲的一个故事：15个教徒和15 个非教徒在深海上遇险，必须将一半的人投入海中，其余的人才能幸免于难，于是想了一个办法：30个人围成一圆圈，从第一个人开始依次报数，每数到第九个人就将他扔入大海，如此循环进行直到仅余15个人为止。问怎样排法，才能使每次投入大海的都是非教徒。
*问题分析与算法设计
约瑟夫问题并不难，但求解的方法很多；题目的变化形式也很多。这里给出一种实现方法。
题目中30个人围成一圈，因而启发我们用一个循环的链来表示。可以使用结构数组来构成一个循环链。结构中有两个成员，其一为指向下一个人的指针，以构成环形的链；其二为该 人是否被扔下海的标记，为1表示还在船上。从第一个人开始对还未扔下海的人进行计数，每数到9时，将结构中的标记改为0，表示该人已被扔下海了。这样循环计数直到有15个人被扔下海为止。
*程序说明与注释
1. #include <stdio.h> 2. struct node { 3. int nextp; /*指向下一个人的指针(下一个人的数组下标)*/ 4. int no_out; /*是否被扔下海的标记。1：没有被扔下海。0：已被扔下海*/ 5. } link[31]; /*30个人，0号元素没有使用*/ 6. int main() { 7. int i, j, k; 8. printf("The original circle is(+:pagendom,@:christian):\n"); 9. for (i = 1; i <= 30; i++) /*初始化结构数组*/ 10. { 11. link[i].nextp = i + 1; /*指针指向下一个人(数组元素下标)*/ 12. link[i].no_out = 1; /*标志置为1，表示人都在船上*/ 13. } 14. link[30].nextp = 1; /*第30个人的指针指向第一个人以构成环*/ 15. j = 30; /*j:指向已经处理完毕的数组元素，从link[i]指向的人开始计数*/ 16. for (i = 0; i < 15; i++) /*i:已扔下海的人数计数器*/ 17. { 18. for (k = 0;;) /*k:决定哪个人被扔下海的计数器*/ 19. if (k < 15) { 20. j = link[j].nextp; /*修改指针，取下一个人*/ 21. k += link[j].no_out; /*进行计数。因已扔下海的人计标记为0*/ 22. } else 23. break; /*计数到15则停止计数*/ 24. link[j].no_out = 0; /*将标记置 0，表示该人已被扔下海*/ 25. } 26. for (i = 1; i <= 30; i++) /*输出结果*/ 27. printf("%c", link[i].no_out ? '@' : '+'); /*+:被扔下海， @：在船上*/ 28. printf("\n"); 29. }
*运行结果
The original circle is(+:pagandom, @:christian):
+++@@+@+@@@+@+++@@+@@@+++@+@@+
(+"表示被扔下海海的非教徒 @：留在船上活命的教徒)
*思考题
有N个小孩围 成一圈并依次编号，教师指定从第M个小孩开始报数，报到第S个小孩即令其出列。然后从下一个孩子继续报数，数到第S个小孩又令其出列，如此直到所有的孩子都出列。求小孩出列的先后顺序。
72.邮票组合
某人有四张3分的邮票和三张5分的邮票，用这些邮票中的一张或若干张可以得到多少种不同的邮资？
*问题分析与算法设计
将问题进行数学分析，不同张数和面值的邮票组成的邮资可用下列公式计算：
S=3*i+5*j
其中i为3分邮柰的张数，j为5分的张数
按题目的要求，3分的邮票可以取0、1、2、3、4张，5分的邮票可以取0、1、2、3张。采用穷举方法进行组合，可以求出这些不同面值不同张数的邮标组合后的邮资。
*程序说明与注释
1. #include <stdio.h> 2. int a[27]; 3. int main() { 4. int i, j, k, s, n = 0; 5. for (i = 0; i <= 4; i++) /*i:取三分邮票的张数*/ 6. for (j = 0; j <= 3; j++) /*j:取5分邮票的张数*/ 7. { 8. s = i * 3 + j * 5; /*计算组成的邮票面值*/ 9. for (k = 0; a[k]; k++) /*查找是否有相同的邮资*/ 10. if (s == a[k]) 11. break; 12. if (!a[k] && s) /*没有找到相同的邮资则满足要求存入数组*/ 13. { 14. a[k] = s; 15. n++; 16. } 17. } 18. printf("%d kinds:", n); /*输出结果*/ 19. for (k = 0; a[k]; k++) 20. printf("%d ", a[k]); 21. printf("\n"); 22. }
*运行结果
19 kinds: 5 10 15 3 8 13 18 6 11 16 21 9 14 19 24 12 17 22 27
73.和数能表示1~23的5个正整数
已知五个互不相同的正整数之和为23，且从这五个数中挑选若干个加起来可以表示从1到23之内的全部自然数。问这五个数是什么？
*问题分析与算法设计
从计算机程序设计的角度来说，可以用穷举法分解23，然后判断所分解的五个数是否可以表示1到23 之间的全部整数。
*程序说明与注释
1. #include <stdio.h> 2. int main() { 3. int a, b, c, d, e, i, j, k, l, m, x, 4. count = 0, f = 0; /*f:分解的5个数可以表示出1~23的标记*/ 5. printf("There are following possble result:\n"); 6. for (a = 1; a <= 23; a++) /*将23分解为a,b,c,d,e五个数*/ 7. for (b = 1 + a; b <= 23 - a; b++) 8. for (c = 1 + b; c <= 23 - a - b; c++) 9. for (d = 1 + c; d <= 23 - a - b - c; d++) { 10. f = 1; 11. if ((e = 23 - a - b - c - d) > d) 12. for (f = 0, x = 1; x < 24 && !f; x++) /*判断5个数可否表示1~23*/ 13. for (f = 1, i = 0; i < 2 && f; i++) /*穷举5个数的全部取舍*/ 14. for (j = 0; j < 2 && f; j++) 15. for (k = 0; k < 2 && f; k++) 16. for (l = 0; l < 2 && f; l++) 17. for (m = 0; m < 2 && f; m++) 18. if (x == a * i + b * j + c * k + d * l + e * m) 19. f = 0; 20. if (!f) 21. printf("[%d]: %d %d %d %d %d\n", ++count, a, b, c, d, e); 22. } 23. }
*运行结果
There are following possble result:
[1]: 1 2 3 5 12
[2]: 1 2 3 6 11
[3]: 1 2 3 7 10
[4]: 1 2 4 5 11
[5]: 1 2 4 6 10
[6]: 1 2 4 7 9
74.可称1~40磅的4块砝码
法国数学家梅齐亚克在他著名的《数字组合游戏》(1962)中提出了一个问题：一位商人有一个重40磅的砝码，一天不小心将砝码摔成了四块。后来商人称得每块的重量都是整磅数，而且发现这四块碎片可以在天平上称1至40磅之间的任意重量。请问这四块碎片各重多少？
*问题分析与算法设计
本题是上一题的发展。题目中给出的条件是“在天平上”，这意味着：同一砝码既可以放在天平的左侧，也可以放在天平的右侧。若规定重物只能放在天平的左侧，则当天平平衡时有：
重物重量+左侧砝码重量总和=右侧砝码重量总和
由此可得：
重物重量=右侧砝码重量总和-左侧砝码重量总和
编程时只要根据以上公式，使“右侧砝码重量总和-左侧砝码重量总和”可以表示1到40之间的全部重量即可。编程中要注意的是：怎样采用一种简单的方法来表示一个砝码是在天平的左侧还是在天平的右侧，或是根本没有使用。
以下程序采用1、 -1和0分别表示上述三种情况，请注意理解。
*程序说明与注释
1. #include <math.h> 2. #include <stdio.h> 3. int main() { 4. int weight1, weight2, weight3, weight4, d1, d2, d3, d4, x, 5. flag; /*flag:满足题意的标记*/ 6. printf("The weight is broke up as following 4 pieces:"); 7. for (weight1 = 1; weight1 <= 40; weight1++) /*将40分解成4份*/ 8. for (weight2 = weight1 + 1; weight2 <= 40 - weight1; weight2++) 9. for (weight3 = weight2 + 1; weight3 <= 40 - weight1 - weight2; weight3++) 10. if ((weight4 = 40 - weight1 - weight2 - weight3) >= weight3) { 11. for (flag = 1, x = 1; x < 41 && flag; 12. x++) /*判断可否称出1~40之间的全部重量*/ 13. for (flag = 0, d1 = 1; d1 > -2; d1--) /*将重物放在天平的左边*/ 14. for (d2 = 1; d2 > -2 && !flag; d2--) /*1:砝码在天平右边*/ 15. for (d3 = 1; d3 > -2 && !flag; d3--) /*0：不用该砝码*/ 16. for (d4 = 1; d4 > -2 && !flag; d4--) /*-1:砝码在天平的左边*/ 17. if (x == weight1 * d1 + weight2 * d2 + weight3 * d3 + 18. weight4 * d4) 19. flag = 1; 20. if (flag) 21. printf("%d %d %d %d\n", weight1, weight2, weight3, weight4); 22. flag = 0; 23. } 24. }
*运行结果
The weight is broke up as following 4 pieces: 1 3 9 27
75.10个小孩分糖果
十个小孩围成一圈分糖果，老师分给第一个小孩10块，第二个小孩2块，第三个小孩8块，第四个小孩22块，第五个小孩16块，第六个小孩4块，第七个小孩10块，第八个小孩6块，第九个小孩14块，第十个小孩20块。然后所有的小孩同时将手中的糖分一半给右边的小孩；糖块数为奇数的人可向老师要一块。问经过这样几次后大家手中的糖的块数一样多？每人各有多少块糖？
*问题分析与算法设计
题目描述的分糖过程是一个机械的重复过程，编程算法完全可以按照描述的过程进行模拟。
*程序说明与注释
1. #include <stdio.h> 2. void print(int s[]); 3. int judge(int c[]); 4. int j = 0; 5. int main() { 6. static int sweet[10] = {10, 2, 8, 22, 16, 7. 4, 10, 6, 14, 20}; /*初始化数组数据*/ 8. int i, t[10], l; 9. printf(" child\n"); 10. printf(" round 1 2 3 4 5 6 7 8 9 10\n"); 11. printf("………………………..\n"); 12. print(sweet); /*输出每个人手中糖的块数*/ 13. while (judge(sweet)) /*若不满足要求则继续进行循环*/ 14. { 15. for (i = 0; i < 10; i++) /*将每个人手中的糖分成一半*/ 16. if (sweet[i] % 2 == 0) /*若为偶数则直接分出一半*/ 17. t[i] = sweet[i] = sweet[i] / 2; 18. else /*若为奇数则加1后再分出一半*/ 19. t[i] = sweet[i] = (sweet[i] + 1) / 2; 20. for (l = 0; l < 9; l++) /*将分出的一半糖给右(后)边的孩子*/ 21. sweet[l + 1] = sweet[l + 1] + t[l]; 22. sweet[0] += t[9]; 23. print(sweet); /*输出当前每个孩子中手中的糖数*/ 24. } 25. } 26. int judge(int c[]) { 27. int i; 28. for (i = 0; i < 10; i++) /*判断每个孩子手中的糖是否相同*/ 29. if (c[0] != c[i]) 30. return 1; /*不相同返回 1*/ 31. return 0; 32. } 33. void print(int s[]) /*输出数组中每个元素的值*/ 34. { 35. int k; 36. printf(" %2d ", j++); 37. for (k = 0; k < 10; k++) 38. printf("%4d", s[k]); 39. printf("\n"); 40. }
76.小明买书
小明假期同爸爸一起去书店，他选中了六本书，每本书的单价分别为：3.1，1.7，2，5.3，0.9和7.2。不巧的是，小明的爸爸只带了十几块钱，为了让小明过一个愉快的假期，爸爸扔然同意买书，但提邮购一个要求，要小明从六本书中选出若干本，使得单价相加所得的和同10最接近。你能够帮助小明解决这个问题吗？
*问题分析与算法设计
分析题意，可将题目简化为：从六个数中选出若干个求和，使得和与10的差值最小。
题目中隐含两个问题，其一是怎样从六个数中选出若干个数；其二是求与10的差。
从六个数中选出若干个数实质是从六个数中选出若干个进行组合。每个数在组合过程中只有两种情况：要么是选中参加求和，要么是没选中不参加求和。这样就可以使用六重循环对每个数是否参加求和进行全部可能情况的组合。
关于求与10的差值应当注意的是：差值的含义是指差的绝对值。例如：“9-10=-1"和"11-10=1",但9和11这两者与10的差值都是1。若认为”9“与”10的差值为-1就错了。
*程序说明与注释
1. #include <math.h> 2. #include <stdio.h> 3. int main() { 4. int d[6], m, i, j; 5. long b[63], flag; 6. float c[6], min, x; 7. printf("Please enter the prices of 6 books:"); 8. for (i = 0; i < 6; i++) 9. scanf("%f", &c[i]); /*输入六个浮点数*/ 10. for (i = 0, min = -1, d[0] = 0; d[0] < 2; 11. d[0]++) /*建立六个数的全部组合并处理*/ 12. for (d[1] = 0; d[1] < 2; d[1]++) /*i:差值具有min组合的数量*/ 13. for (d[2] = 0; d[2] < 2; d[2]++) /*min:与10的最小差值*/ 14. for (d[3] = 0; d[3] < 2; d[3]++) /*d[]:组合时是否取该数的标志*/ 15. for (d[4] = 0; d[4] < 2; d[4]++) 16. for (d[5] = 0; d[5] < 2; d[5]++) { 17. for (flag = 0, x = 0, j = 5; j >= 0; j--) 18. /*flag:将六个数的组合用对应的一个十进制位表示 19. x:对应六个数组合的和*/ 20. { 21. x += c[j] * d[j]; 22. flag = flag * 10 + d[j]; 23. } 24. x = ((x - 10 > 0) ? x - 10 : 10 - x); /*x: 组合的和与10的差*/ 25. if (min < 0) { 26. min = x; /*对第一次计算出的差min进行处理*/ 27. b[i++] = flag; /*b[]:有相同的min的flag的数组 i:b[]数组的下标*/ 28. } else if (min - x > 1.e-6) /*对新的min的处理*/ 29. { 30. min = x; 31. b[0] = flag; 32. i = 1; 33. } else if (fabs((double)x - min) < 1.e-6) 34. b[i++] = flag; /*对相等min的处理*/ 35. } 36. for (m = 0; m < i; m++) /*输出全部i个与10的差值均为min的组合*/ 37. { 38. printf("10(+ -)%.2f=", min); 39. for (flag = b[m], j = 0; flag > 0; j++, flag /= 10) 40. if (flag % 10){/*将b[]中存的标记flag还原为各个数的组合*/ 41. if (flag > 1) 42. printf("%.2f+", c[j]); 43. else 44. printf("%.2f\n", c[j]); 45. } 46. } 47. }
*运行结果
Please enter the prices of 6 books:3.1 1.7 2.0 5.3 0.9 7.2
10(+ -)0.10=2.00+0.90+7.20
10(+ -)0.10=1.70+2.00+5.30+0.90
10(+ -)0.10=3.10+1.70+5.30
*思考题
可以看出，程序中求六个数所能产生全部组合的算法并不好，使用六重循环进行处理使程序显得不够简洁。可以设计出更通用、优化的算法产生全部组合。
77.波松瓦酒的分酒趣题
法国著名数学家波瓦松在表年时代研究过一个有趣的数学问题：某人有12品脱的啤酒一瓶，想从中倒出6品脱，但他没有6品脱的容器，仅有一个8品脱和5品脱的容器，怎样倒才能将啤酒分为两个6品脱呢？
*问题分析与算法设计
将12品脱酒 8品脱和5品脱的空瓶平分，可以抽象为解不定方程：
8x-5y=6
其意义是：从12品脱的瓶中向8品脱的瓶中倒x次，并且将5品脱瓶中的酒向12品脱的瓶中倒y次，最后在12品脱的瓶中剩余6品脱的酒。
用a,b,c代表12品脱、8品脱和5品脱的瓶子，求出不定方程的整数解，按照不定方程的意义则倒法为：
a -> b -> c ->a
x y
倒酒的规则如下：
1) 按a -> b -> c ->a的顺序；
2) b倒空后才能从a中取
3) c装满后才能向a中倒
按以上规则可以编写出程序如下：
*程序说明与注释
1. #include <stdio.h> 2. void getti(int a, int y, int z); 3. int i; /*最后需要分出的重量*/ 4. int main() { 5. int a, y, z; 6. printf("input Full a,Empty b,c,Get i:"); /*a 满瓶的容量 y:第一个空瓶的容量 z:第二个空瓶的容量*/ 7. scanf("%d%d%d%d", &a, &y, &z, &i); 8. getti(a, y, z); /*按a -> y -> z -> a的操作步骤*/ 9. getti(a, z, y); /*按a -> z -> y -> a的步骤*/ 10. } 11. void getti(int a, int y,int z) /*a:满瓶的容量 y:第一个空瓶的容量 z:第二个空瓶的容量*/ 12. { 13. int b = 0, c = 0; /* b:第一瓶实际的重量 c:第二瓶实际的重量*/ 14. printf(" a%d b%d c%d\n %4d%4d%4d\n", a, y, z, a, b, c); 15. while (a != i || b != i && c != i) /*当满瓶!=i或另两瓶都!=i*/ 16. { 17. if (!b) { 18. a -= y;b = y; 19. } /*如果第一瓶为空，则将满瓶倒入第一瓶中*/ 20. else if (c == z) { 21. a += z;c = 0; 22. } /*如果第二瓶满，则将第二瓶倒入满瓶中*/ 23. else if (b > z - c) /*如果第一瓶的重量>第二瓶的剩余空间*/ 24. { 25. b -= (z - c);c = z; 26. } /*则将装满第二瓶，第一瓶中保留剩余部分*/ 27. else { 28. c += b;b = 0; 29. } /*否则，将第一瓶全部倒入第二瓶中*/ 30. printf(" %4d %4d %4d\n", a, b, c); 31. } 32. }
*思考题
上面的程序中仅给出了两种分酒的方法，并没有找出全部的方法。请设计新的算法，找出全部的分酒方法，并找出一种倒酒次数最少的方法。
78.求π的近似值
请利用“正多边形逼近”的方法求出π的近似值
*问题分析与算法设计
利用“正多边形逼近”的方法求出π值在很早以前就存在，我们的先人祖冲之就是用这种方法在世界上第一个得到精确度达小数点后第6位的π值的。
利用圆内接正六边形边长等于半径的特点将边数翻番，作出正十二边形，求出边长，重复这一过程，就可获得所需精度的π的近似值。
假设单位圆内接多边形的边长为2b，边数为i，则边数加倍后新的正多边形的边长为：
x=√──────
2-2*√───
1-b*b
──────
2
周长为：
y=2 * i * x i:为加倍前的正多边形的边数
*程序说明与注释
1. #include <math.h> 2. #include <stdio.h> 3. int main() { 4. double e = 0.1, b = 0.5, c, d; 5. long int i; /*i: 正多边形边数*/ 6. for (i = 6;; i *= 2) /*正多边形边数加倍*/ 7. { 8. d = 1.0 - sqrt(1.0 - b * b); /*计算圆内接正多边形的边长*/ 9. b = 0.5 * sqrt(b * b + d * d); 10. if (2 * i * b - i * e < 1e-15) 11. break; /*精度达1e-15则停止计算*/ 12. e = b; /*保存本次正多边形的边长作为下一次精度控制的依据*/ 13. } 14. printf("pai=%.15lf\n", 2 * i * b); /*输出π值和正多边形的边数*/ 15. printf("The number of edges of required polygon:%ld\n", i); 16. }
*运行结果
pai=3.141592653589794
The number of edges of required polygon:100663296
*思考题
请用外切正多边形逼近的方法求π的近似值。
79.求π的近似值(2)
利用随机数法求π的近似值
*问题分析与算法设计
随机数法求π的近似值的思路：在一个单位边长的正方形中，以边长为半径，以一个顶点为圆心，在政权方形上作四分之一圆。随机的向正方形内扔点，若落入四分之一圆内则计数。重复向正方形内扔足够多的点，将落入四分之一圆内的计数除以总的点数，其值就是π值四分之一的近似值。
按此方法可直接进行编程，注意：本方法求出的π值只有统计次数足够多时才可能准确。
*程序说明与注释
1. #include <stdio.h> 2. #include <stdlib.h> 3. #include <time.h> 4. 5. #define N 30000 6. 7. int main() 8. { 9. float x, y; 10. int c = 0, d = 0; 11. srand(time(NULL)); // 初始化随机数种子 12. while (c++ < N) { 13. x = (float)rand() / RAND_MAX; // 生成0到1之间的随机小数，即x坐标 14. y = (float)rand() / RAND_MAX; // 生成0到1之间的随机小数，即y坐标 15. if (x * x + y * y <= 1) { // 判断点是否落在四分之一圆内，圆半径为1，半径的平方即为1 16. d++; 17. } 18. } 19. printf("pi ≈ %f\n", 4. * d / N); // 输出π值的近似值 20. return 0; 21. }
*运行结果
多次运行程序，可能得到多个不同的对口果，这是因为采用的是统计规律求出的近似值，只有当统计的次数足够大时，才可能逼近π值。运行四次，可能的结果是：
3.122267
3.139733
3.133733
80.奇数平方的一个有趣性质
编程验证“大于1000的奇数其平方与1的差是8的倍数”。
*问题分析与算法设计
本题是一个很容易证明的数学定理，我们可以编写程序验证它。
题目中给出的处理过程很清楚，算法不需要特殊设计。可以按照题目的叙述直接进行验证(程序中仅验证到3000)。
*程序说明与注释
1. #include <stdio.h> 2. int main() { 3. long int a; 4. for (a = 1001; a <= 3000; a += 2) { 5. printf("%ld:", a); /*输出奇数本身*/ 6. printf("(%ld*%ld-1)/8", a, a); /*输出(奇数的平方减1)/8*/ 7. printf("=%ld", (a * a - 1) / 8); /*输出被8除后的商*/ 8. printf("+%ld\n", (a * a - 1) % 8); /*输出被8除后的余数*/ 9. } 10. }
