《穷举法基本思想是首先根据问题的部分条件预估答案的范围,然后在.ppt》由会员分享，可在线阅读，更多相关《穷举法基本思想是首先根据问题的部分条件预估答案的范围,然后在.ppt（23页珍藏版）》请在三一文库上搜索。
1、穷举法 基本思想是首先根据问题的部分条件预估答案的范围，然后在此范围内对所有可能的情况进行逐一验证，直到全部情况通过了验证为止。若某个情况使验证符合题目的全部条件，则该情况为本题的一个答案；若全部情况验证结果均不符合题目的全部条件，则说明该题无答案。,穷举法及其应用,特点 算法简单，容易理解，但运算量大。通常可以解决“有几种组合”、“是否存在”、求解不定方程等类型的问题。用循环结构实现。,首页,上页,下页,节,末页,结束,关于循环,循环变量初值 循环条件 循环体 循环变量的增量,进入循环之前执行，只做一次 多次判断 重复执行的语句 多次执行，控制循环结束,while ( ) do while
2、( ); for (） if-goto,适合用在循环次数已知的场合,首页,上页,下页,节,末页,结束,for ( i=999 ; i = 100 ; i- ),for(i=1;i=9;i+) for(j=1;j=9;j+) ,i=1时,j=1 j=2 . . j=9,i=2时 . .,要素,语句,嵌套,break continue,题1 每只公鸡5个钱，每只母鸡3个钱，每3只小鸡1个钱，用100个钱，买100只鸡，问公鸡、母鸡和小鸡各买几只？,定义变量 x , y, z , 表示公鸡、母鸡和小鸡的只数,for( x=1; x=100 ;x+) for( y=1; y=100 ; y+) for
3、( z=1;z=100;z+) if( 5*x+ 3*y+ z/3=100 & x+y+z=100),程序运算100万次,首页,上页,下页,节,末页,结束,买100只鸡,100元钱,x 最多为20，y 最多为34，当 x, y 已确定时， z的值为100-x-y，不必对z进行循环。,main( ) int x,y,z; for (x=1;x20;x+) for(y=1;y=34-x;y+) z=100-x-y; if ( 5*x+3*y+z/3=100 ) printf(“%d,%d,%dn”,x,y,z); ,if ( (5*x+3*y+z/3=100) ,首页,上页,下页,节,末页,结束,
4、特点 算法简单，容易理解，但运算量大。,首页,上页,下页,节,末页,结束,题4.33 编写程序求出 555555 的约数中最大的三位数是多少,1 理解约数：n% k=0 则 k是n 的约数 2 最大数：从大到小循环，找到一个约数就退出循环,main( ) int a; for ( a= 999 ; a=100 ; a - -) *正确地表示三位数的范围 * if ( 555555%a=0) * 如果555555能被a整除 * break; * 结束循环 * printf(“%d”,a); ,题4.49 一辆卡车违反交通规则，撞人逃跑了。现场三人目击，记下了车号特征：前两位数字相同，后两位数字相
5、同，四位数恰好是一个整数的平方。求该车号。,1 将车号假定为aabb，是个四位数，a,b的变化范围是1-9 2 四位数的范围是1000-9999，某整数的平方是四位数 3 预估整数的范围：32的平方是1024，94的平方是8836,main( ) int n,a,b ； for (n=32;n=94;n+) * n*n是个四位数 * for(a=1;a=9;a+) * a 的范围 * for(b=1;b=9;b+) * b 的范围 * if(n*n = a*1000+a*100+b*10+b) printf(“%d%d%d%d”,a,a,b,b); printf(“%dn”,n); ,结果：7
6、744 88的平方,题4.50 口袋里放12个球，3个红球，3个白球和6个黑球,每次从中任取8个，求共有多少总颜色搭配。,1 找出各类球可能出现的范围 红球 x 从1-3 白球 y 从1-3 黑球 z 个数不可能是1，因为总数必须是8 ，所以z 从2-6 ， 2 定义一个整型变量做计数器,main( ) int x,y,z,k=0; for(x=1;x=3;x+) * 红球可能的范围 * for(y=1;y=3;y+) * 白球可能的范围 * for(z=2;z=6;z+) * 黑球可能的范围 * if(x+y+z=8) printf(“x=%d,y=%d,z=%dn”,x,y,z); k+;
7、 ,首页,上页,下页,节,末页,结束,题4.51 100匹马驮100担货，大马一匹驮3担，中马一匹驮2担，小马两匹驮1担，求大、中、小马的数目。,1 定义三种数目为 x, y, z , 分析方法同100元钱买100只鸡 2 注意 z 能够被2 整除,main( ) int x,y,z; for (x=1;x34;x+) * 大马数目的范围 * for(y=1;y=50;y+) * 中马数目的范围 * z=100-x-y; *总数为100，z不循环* if( ( 3*x+2*y+z/2=100 ) ,共有100担货,首页,上页,下页,节,末页,结束,题 4.52 将一元钱换成一分，二分和五分的硬
8、币，共有多少种换法？,main( ) int a,b,c,k=0; for(a=0 ; a=100 ; a+) * 1分钱可能的个数 * for(b=0;b=50;b+) * 2分钱可能的个数 * for(c=0;c=20;c+) * 5分钱可能的个数 * if (a+2*b+5*c=100) * 总面值为1元 * k+; printf( “%dn”, k) ; ,定义变量 a, b, c 作为三种硬币的个数 定义变量 k 作为计数器 总的面值是100分，但总的硬币个数不是100个,首页,上页,下页,节,末页,结束,题4.53 显示200以内的完全平方数和它们的个数 A2+B2 = C2,1
9、理解题意：A2 、B2 和C2的值均不超过200 2 统计个数的方法： 计数器,main( ) int a,b,c,k=0; for (a=1;a*a=200;a+) * a 的范围 * for(b=1;b*b=200;b+) * b 的范围 * for(c=1;c*c=200;c+) * c 的范围 * if( a*a+b*b=c*c) * 完全平方数的特点 * printf(“%d,%d,%dn”,a,b,c) ; k+; * 计数器 加 1 * ,首页,上页,下页,节,末页,结束,结果： 3,4,5 4,3,5 5,12,13 6,8,10 8,6,10 12,5,13,题4.54 设n
10、 是一个四位数，它的9倍恰好是它的反序数，求n的值,如何表示四位数 1 定义四个变量 a,b,c,d 作为该数各个位上的数字 则a*1000+b*100+c*10+d 为该数的大小 例如：2134表示为2*1000+1*100+3*10+4 2 定义一个变量 n ，则各个位分别为： 个位：n%10 十位：n/10%10 百位：n/100%10 千位：n/1000 3 正确表示各个位上数字的范围：,从 1-9 从 0-9 从 0-9 从 1-9,为什么不是0,n的最高位不能是0，反序数的最高位也不可能是0,首页,上页,下页,节,末页,结束,main( ) int a,b,c,d ; for (a
11、=1;a=9;a+) * a 的范围 * for(b=0;b=9;b+) * b 的范围 * for(c=0;c=9;c+) * c 的范围 * for(d=1;d=9;d+) * d的范围 * if( 9*(a*1000+b*100+c*10+d)=d*1000+c*100+b*10+a) printf(“%d%d%d%dn”,a,b,c,d) ; ,main( ) int n; for(n=1000;n=9999;n+) *n是一个四位数* if(9*(n/1000*1000+n/100%10*100+n/10%10*10+n%10)= n%10*1000+n/10%10*100+n/10
12、0%10*10+n/1000) Printf(“%d”,n); ,比较两个程序,首页,上页,下页,节,末页,结束,结果：1089,题4.55 一个数的等于它的反序数，则为对称数，求1993以内的最大二进制的对称数,1 将十进制数转换成二进制，存入一个数组a16 中 2 编一个函数，判断是否为对称数，返回为 1 或 0 3 求最大数，从大到小循环，找到一个就结束, 用break,main( ) int i , n,k,j, a16=0; for(i=1993; i =1;i- - ) k=i; n=0; While(k0) an+=k%2; k=k/2; if(fun(a,n-1) break;
13、 printf(“%d=“,i); for(j=0;jn-1;j+) printf(“%3d”,a j ); ,fun(int b ,int n) int j,k=1; for(j=0;jn;j+) if(b j !=bn-j-1) k=0; break; return k; ,结果： 1975=1110110111,题4.56 编写程序，求下式中各字母所代表的数字,1 定义四个变量 P,E,A,R 作为各个位上的数字 则P*1000+E*100+A*10+R 为该数的大小 2 注意各个变量变化的范围,main( ) int p,e,a,r ; for (p=1;p=9;p+) * p 的范围
14、 * for(e=0;e=9;e+) * e 的范围 * for(a=1;a=9;a+) * a 的范围 * for(r=0;r=9;r+) * r的范围 * if( p*1000+e*100+a*10+r a*100- r*10 - a=p*100+e*10+a) printf(“%d%d%d%dn”,p,e,a,r) ; ,首页,上页,下页,节,末页,结束,结果：1098,题4.57 一个自然数的七进制是一个三位数，其九进制也是一个三位数，且这两个三位数数码顺序正好相反，求这个三位数,1 定义三个变量a, b, c作为各个位上的数字 2 注意七进制中的数字符号为 0- 6，因此a,b,c均
15、不超过6 3 非十进制数据的按权展开求和即为对应的十进制数,main( ) int a,b,c; for (a=1;a=6;a+) * a 的范围 * for(b=0;b=6;b+) * b的范围 * for(c=1;c=6;c+) * c 的范围 * if ( a*7*7+b*7+c = c*9*9+b*9+a) printf(“%d%d%d”,a,b,c); * 显示这三个数字 * printf(“%d”,a*7*7+b*7+c); * 显示这个三位数 * ,首页,上页,下页,节,末页,结束,结果： 七进制 ：503 九进制：305 十进制：248,题4.59 编写程序求1000以内所有的
16、阿姆斯特朗数。 407=43+03+73,定义三个变量a, b, c作为各个位上的数字,main( ) int a,b,c; for (a=1;a=9;a+) * a 的范围 * for(b=0;b=9;b+) * b的范围 * for(c=0;c=9;c+) * c 的范围 * if ( a*100+b*10+c = a*a*a+b*b*b+c*c*c) printf(“%d%d%d”,a,b,c); * 显示这三个数字 * printf(“%d”,a*100+b*10+c); * 显示这个三位数 * ,首页,上页,下页,节,末页,结束,main( ) int n,a,b,c; for (n
17、=100;n=999;n+) *n在所有的三位数中循环 * a=n%10; * n的个位 * b=n/10%10; *n 的十位 * c=n/100; *n 的百位 * if(n=a*a*a+b*b*b+c*c*c) printf(“%dn”,n); ,首页,上页,下页,节,末页,结束,结果： 153 370 371 407,题4.60 任意输入一个偶数，将它分解成两个素数之和,main( ) int j,k,n,m; scanf(“%d”, ,如何判断一个数是素数,题4.61 如果整数A的因子之和是B，而且B的因子之和是A，则A与B是亲密数。找出3000以内的全部亲密数,1 定义一个变量 a
18、 在1-3000以内循环 2 若有：a%i =0,则 i为a的一个因子，找出a的全部因子 3 将a的因子求和，并赋值给m，重复2步骤，求m的因子之和n 4 判断a与n是否相等,main( ) int a ,i , m , n; for(a=1;a3000;a+) for(m=0, i =1;i=a/2;i+) if(a%i=0) m+=i; /* a的因子和为m */ for(n=0,i=1;i=m/2;i+) if(m%i=0) n+=I /* m的因子和为n */ if(a=n ,题4.69 编写程序，输出1000以内的所有完数及其因子。 例如：6=1+2+3,1 定义变量i，从1-100
19、0循环 2 将因子存进一个整形数组，求数组中各元素之和s 3 判断 s 与i 是否相等,main( ) int i,j,m,s,k,a20; for(i=0;i0) for(j=1;j=m) break; If(s!=0 ,题4.82 求一个三位数，该三位数等于每位数字的阶乘之和,1 定义三个变量a, b, c作为各个位上的数字 2 调用一个阶乘函数,main( ) int a,b,c; for (a=1;a=9;a+) * a 的范围 * for(b=0;b=9;b+) * b的范围 * for(c=0;c=9;c+) * c 的范围 * if ( a*100+b*10+c = f(a)+f
20、(b)+f(c) ) printf(“%d”,a*100+b*10+c); * 显示这个三位数 * f(int a) int k=0, t=1; while(+k=a ) t*=k; return(t); ,首页,上页,下页,节,末页,结束,结果： 145,教材6-26 用40元钱买苹果，西瓜和梨共100个，3种水果。苹果0.4元一个，西瓜4元一个，梨0.2元一个，输出全部购买方案。,1 避免浮点数的恒等比较，因此不用几元钱做单位。 2 定义苹果x, 梨y,西瓜z,main( ) int x,y,z; for (x=1;x100;x+) for(y=1;y200;y+) z=100-x-y; if ( 4*x+2*y+40*z=400 ) printf(“%d,%d,%dn”,x,y,z); ,结果： x y z 5, 90,5 24,72,4 43,54,3 62,36,2 81,18,1,请大家注意：,1 正确找出穷举的范围,2 如何描述问题,3 如何找一个数的因子,4 如何判断素数,5 累加器的使用,