穷举法基本思想是首先根据问题的部分条件预估答案的范围

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,穷举法,基本思想是首先根据问题的部分条件预估答案的，然后在此范围内对,所有可能的情况,进行逐一验证，直到全部情况通过了验证为止。若某个情况使验证符合题目的全部条件，则该情况为本题的一个答案；若全部情况验证结果均不符合题目的全部条件，则说明该题无答案。,穷举法及其应用,特点,算法简单，容易理解，但运算量大。通常可以解决“有几种组合”、“是否存在”、求解不定方程等类型的问题。,用,循环结构,实现。,首页,下页,节,末页,结束,1,关于循环,循环变量初值,循环条件,循环体,循环变量的增量,进入循环之前执行，只做一次,多次判断,重复执行的语句,多次执行，控制循环结束,while ( ),do while ( );,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,2,题1,每只公鸡5个钱，每只母鸡3个钱，每3只小鸡1个钱，用100个钱，买100只鸡，问公鸡、母鸡和小鸡各买几只？,定义变量,x , y, z , 表示公鸡、母鸡和小鸡的只数,for( x=1; x=100 ;x+),for( y=1; y=100 ; y+),for( 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进行循环。,3,main( ), int x,y,z;,for (x=1;x20;x+),for(y=1;y=100 ; a - -),*正确地表示三位数的范围 *,if ( 555555%a=0),* 如果555555能被a整除 *,break;,* 结束循环 *,printf(“%d”,a);,5,题4.49,一辆卡车违反交通规则，撞人逃跑了。现场三人目击，记下了车号特征：前两位数字相同，后两位数字相同，四位数恰好是一个整数的平方。求该车号。,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);,结果：7744,88的平方,6,题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 )&z%2=0),printf(“%d,%d,%dn”,x,y,z);,共有100担货,首页,上页,下页,节,末页,结束,8,题 4.52,将一元钱换成一分，二分和五分的硬币，共有多少种换法？,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个,首页,上页,下页,节,末页,结束,9,题4.53,显示200以内的完全平方数和它们的个数,A,2,+B,2,= C,2,1 理解题意：,A,2,、B,2,和C,2,的值均不超过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,10,题4.54,设n 是一个四位数，它的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,首页,上页,下页,节,末页,结束,11,main( ),int a,b,c,d ;,for (a=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=1;i- - ),k=i; n=0;,While(k0),an+=k%2; k=k/2;,if(,fun,(a,n-1),break;,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,13,题4.56,编写程序，求下式中各字母所代表的数字,P E A R,A R A,P E A,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 的范围 *,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,1 0 9 8,9 8 9,1 0 9,14,题4.57,一个自然数的七进制是一个三位数，其九进制也是一个三位数，且这两个三位数数码顺序正好相反，求这个三位数,1 定义三个变量,a, b, c作为各个位上的数字,2 注意七进制中的数字符号为,0- 6,，因此a,b,c均不超过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,15,题4.59,编写程序求1000以内所有的阿姆斯特朗数。,407=4,3,+0,3,+7,3,定义三个变量,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);,* 显示这个三位数 *,首页,上页,下页,节,末页,结束,16,main( ),int n,a,b,c;,for (,n=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,17,题4.60,任意输入一个偶数，将它分解成两个素数之和,main( ), int j,k,n,m;,scanf(“%d”,for( j=2;jn;j+),for( k=2;k=j),m=n- j;,for(k=2;km),printf(“%4d=%4d+%4dn”,n,j,m);,break;,如何判断一个数是素数,18,题4.61,如果整数A的因子之和是B，而且B的因子之和是A，则A与B是亲密数。找出3000以内的全部亲密数,1 定义一个变量 a 在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,&am),/* a与n相等 */,printf(“%4d-%4d”,a,m);,19,题4.69,编写程序，输出1000以内的所有完数及其因子。,例如：6=1+2+3,1 定义变量i，从1-1000循环,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&I=s+m), ak+=m;,for(j=0;jk;j+),printf(“%4d”,aj); printf(“=%4dn”,I); ,20,题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(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,21,教材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,22,请大家注意：,1 正确找出穷举的范围,2 如何描述问题,3 如何找一个数的因子,4 如何判断素数,5 累加器的使用,23,