4_b_循环例题.pptVIP

共 26 页 第 * 页 共 49页 第 * 页 §6-5 循环应用 例6-15：任取1～9中的4个互不相同的数，使它们的和为12。用穷举法输出所有满足该条件的4个数的排列。 如：{1,2,3,6}，{1,2,6,3}，{1,3,2,6}，…… 用枚举法(穷举法)解 若i，j，k，l分别代表4个数，列出它们所有的排列，从中找出符合条件的i、j、k和l（i+j+k+l=12，且这4个数互不相同）。由于穷举法对所有可能的情况都进行有哪些信誉好的足球投注网站，所以计算工作量巨大，离开高速计算机，穷举法只能是理论上可行而实际上不可行的计算方法。 循环进行了94=6561次 共 49页 第 * 页 main ( ) { int i, j, k, l, n=0; for ( i=1; i10; i++ ) /* 列举4个1到9之间的数*/ for ( j=1; j10; j++ ) for ( k=1; k10; k++ ) for ( l=1; l10; l++ ) {if ( i==j||i==k||i==l||j==k||j==l||k==l ) continue; if ( i+j+k+l!=12 ) continue; /* 不满足条件舍弃 */ n++; /* 满足条件的排列计数 */ printf(”{%d,%d,%d,%d} ”,i,j,k,l); if ( n%6==0 ) printf(”\n”); /* 每行输出6个排列 */ } } 整理，得到程序如下： 共 49页 第 * 页 §6-5 循环应用 运行程序，输出结果是： {1,2,3,6} {1,2,4,5} {1,2,5,4} {1,2,6,3} {1,3,2,6} {1,3,6,2} {1,4,2,5} {1,4,5,2} {1,5,2,4} {1,5,4,2} {1,6,2,3} {1,6,3,2} {2,1,3,6} {2,1,4,5} {2,1,5,4} {2,1,6,3} {2,3,1,6} {2,3,6,1} …… 共 49页 第 * 页 §6-5 循环应用 讨论: ⑴ 注意到:互不相同的4个数均小于或等于6。 ⑵ 把所有判断均放到最内层循环中是不合理的，应放到与之相关的循环中。 i==j的判断，只和i、j有关，放在j循环中只判断92=81次，而放在最内层循环中判断94=6561次。 ⑶ 因为i、j、k和l的和为12，所以有l=12-i-j-k，这样就减少一重循环。不过，要注意l0且 l7,因为i+j+k最少是1、2、3的组合，即6。 共 49页 第 * 页 §6-5 循环应用 求1413数的最后三位数。 1. 问题分析 将14累乘13次后截取最后三位数？ 因为14的13次方已经超出了计算机所能表示的整数范围 乘法规律：乘积的最后三位的值只与乘数和被乘数的后三位有关 C语言中最长的整数是： 无符号长整型数：0--4294967295 10位 1410=289254654976 12位 共 49页 第 * 页 §6-5 循环应用 2. 解题方法 设计求xy末尾三位数的通用程序。设一累乘器A，使A与X相乘后取末尾三位数，即：a=a*x%1000，如此循环y次。 问题被简化为求三位数乘法。 3. 程序流程图 共 49页 第 * 页 §6-5 循环应用 2. 解题方法 设计求xy末尾三位数的通用程序。设一累乘器A，使A与X相乘后取末尾三位数，即：a=a*x%1000，如此循环y次。 问题被简化为求三位数乘法。 3. 程序流程图 共 49页 第 * 页 §6-5 循环应用 开始 初始化i,x,y,a 输入x,y N 输出结果 结束 main() {int i=1,x,y,a=1; printf(Input X and Y:); scanf(%d**%d,x,y); while (i=y) {a=a*x%1000; i++; } printf(3 digits is:); printf(%d\n,a%1000); } Input X and Y:14**13 3 digits is:144 Input X and Y:15**12 3 digits is:625 i=y a=a*x%1000 Y i加1 共 26 页 第 * 页