《穷举法本思想是首先根据问题的部分条件预估答案的范围》由会员分享，可在线阅读，更多相关《穷举法本思想是首先根据问题的部分条件预估答案的范围（23页珍藏版）》请在金锄头文库上搜索。
1、 穷举法穷举法穷举法穷举法 基本思想是首先根据问题的部分条件预估基本思想是首先根据问题的部分条件预估答案的答案的范围范围，然后在此范围内对，然后在此范围内对所有可能的情况所有可能的情况进行进行逐一验证，直到全部情况通过了验证为止。若某个情逐一验证，直到全部情况通过了验证为止。若某个情况使验证符合题目的全部条件，则该情况为本题的一况使验证符合题目的全部条件，则该情况为本题的一个答案；若全部情况验证结果均不符合题目的全部条个答案；若全部情况验证结果均不符合题目的全部条件，则说明该题无答案。件，则说明该题无答案。特点特点 算法简单，容易理解，但运算量大。通常可算法简单，容易理解，但运算量大。通常可以
2、解决以解决“有几种组合有几种组合”、“是否存在是否存在”、求解不定、求解不定方程等类型的问题。方程等类型的问题。用用用用循环结构循环结构循环结构循环结构实现。实现。实现。实现。首页上页下页节末页结束循环变量初值循环变量初值循环条件循环条件循环体循环体循环变量的增量循环变量的增量进入循环之前执行，只做一次进入循环之前执行，只做一次多次判断多次判断重复执行的语句重复执行的语句多次执行，控制循环结束多次执行，控制循环结束while ( )do while ( );for (）if-goto 适合用在循环次数已适合用在循环次数已知的场合知的场合首页上页下页节末页结束for ( i=999 ; i =
3、100 ; i- )for(i=1;i=9;i+) for(j=1;j=9;j+) i=1时时 j=1j=2.j=9 i=2时时. 要素要素 语句语句 嵌套嵌套 题题1 1 每只公鸡每只公鸡5 5个钱，每只母鸡个钱，每只母鸡3 3个钱，每个钱，每3 3只小鸡只小鸡1 1个钱，个钱，用用100100个钱，买个钱，买100100只鸡，问公鸡、母鸡和小鸡各买几只？只鸡，问公鸡、母鸡和小鸡各买几只？定义变量定义变量 x , y, z , 表示公鸡、母鸡和小鸡的只数表示公鸡、母鸡和小鸡的只数for( x=1; x=100 ;x+) for( y=1; y=100 ; y+) for( z=1;z=100
4、;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=100 ; a - -) *正确地表示三位数的范围正确地表示三位数的范围 * if ( 555555%a=0) * 如果如果555555能被能被a整除整除 * break; * 结束循环结束循环
5、 * printf(“%d”,a); 题题4.49 4.49 一辆卡车违反交通规则，撞人逃跑了。现场三人目击，一辆卡车违反交通规则，撞人逃跑了。现场三人目击，记下了车号特征：前两位数字相同，后两位数字相同，四位数恰记下了车号特征：前两位数字相同，后两位数字相同，四位数恰好是一个整数的平方。求该车号。好是一个整数的平方。求该车号。 1 1 将车号假定为将车号假定为aabbaabb，是个四位数，是个四位数，a,ba,b的变化范围是的变化范围是1-91-9 2 2 四位数的范围是四位数的范围是1000-99991000-9999，某整数的平方是四位数，某整数的平方是四位数 3 3 预估整数的范围：预
6、估整数的范围：3232的平方是的平方是10241024，9494的平方是的平方是88368836main( ) 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的的平方平方题题4.504.50 口袋里放口袋里放1212个球，个球，3 3个红球，个红球，3 3
7、个白球和个白球和6 6个黑球个黑球, ,每次从每次从中任取中任取8 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+
8、) * 黑球可能的范围黑球可能的范围 * if(x+y+z=8) printf(“x=%d,y=%d,z=%dn”,x,y,z); k+; 首页上页下页节末页结束题题4.514.51 100 100匹马驮匹马驮100100担货，大马一匹驮担货，大马一匹驮3 3担，中马一匹驮担，中马一匹驮2 2担，担，小马两匹驮小马两匹驮1 1担，求大、中、小马的数目。担，求大、中、小马的数目。1 定义三种数目为定义三种数目为 x, y, z , 分析方法同分析方法同100元钱买元钱买100只鸡只鸡2 注意注意 z 能够被能够被2 整除整除main( ) int x,y,z; for (x=1;x34;x+)
9、* 大马大马数目的范围数目的范围 * 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担货担货首页上页下页节末页结束题题 4.52 将一元钱换成一分，二分和五分的硬币，共有多少将一元钱换成一分，二分和五分的硬币，共有多少种换法？种换法？ main( ) int a,b,c,k=0; for(a=0 ; a=100 ; a+) * 1分钱可能的个数分钱可能的个数 * for(b=0;
10、b=50;b+) * 2分分钱可能的个数钱可能的个数 * for(c=0;c=20;c+) * 5分钱可能的个数分钱可能的个数 * if (a+2*b+5*c=100) * 总面值为总面值为1元元 * k+; printf( “%dn”, k) ; 1定义变量定义变量 a, b, c 作为三种硬币的个数作为三种硬币的个数 2定义变量定义变量 k 作为作为计数器计数器3总的面值是总的面值是100分，但总的硬币个数不是分，但总的硬币个数不是100个个首页上页下页节末页结束题题4.53 4.53 显示显示200200以内的完全平方数和它们的个数以内的完全平方数和它们的个数 A A2 2+B+B2 2
11、 = C= C2 21 理解题意：理解题意：A A2 2 、B B2 2 和和C C2 2的值均不的值均不超过超过2002002 统计个数的方法：统计个数的方法： 计数器计数器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 * 首页上
12、页下页节末页结束结果结果：3,4,54,3,55,12,136,8,108,6,1012,5,13题题4.54 4.54 设设n n 是一个四位数，它的是一个四位数，它的9 9倍恰好是它的反序数，求倍恰好是它的反序数，求n n的值的值如何表示四位数如何表示四位数1 定义四个变量定义四个变量 a,b,c,d 作为该数各个位上的数字作为该数各个位上的数字 则则a*1000+b*100+c*10+d 为该数的大小为该数的大小例如：例如：2134表示为表示为2*1000+1*100+3*10+42 定义一个变量定义一个变量 n ，则各个位分别为：则各个位分别为：个位：个位：n%10 十位：十位：n/1
13、0%10百位：百位：n/100%10 千位：千位：n/10003 正确表示各个位上数字的范围：正确表示各个位上数字的范围： 从从 1-9 从从 0-9 从从 0-9 从从 1-9n的最高位不能的最高位不能是是0，反序数的，反序数的最高位也不可能最高位也不可能是是0首页上页下页节末页结束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
14、+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=11101
15、10111 1975=1110110111 题题4.56 4.56 编写程序，求下式中各字母所代表的数字编写程序，求下式中各字母所代表的数字 P E A R P E A R A R A A R A P E 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
16、;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 1 0 9 8 9 8 9 9 8 9 1 0 9 1 0 9 题题4.57 4.57 一个自然数的七进制是一个三位数，其九进制也是一一个自然数的七进制是一个三位数，其九进制也是一个三位数，且这两个三位数数码顺序正好相反，求这个三位数个三位数，且这两个三位数数码顺序正好相
17、反，求这个三位数 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”
18、,a,b,c); * 显示这三个数字显示这三个数字 * printf(“%d”,a*7*7+b*7+c); * 显示显示这个三位数这个三位数 * 首页上页下页节末页结束结果：结果：七进制七进制 ：503九进制：九进制：305 十进制：十进制：248题题4.594.59 编写程序求编写程序求10001000以内所有的阿姆斯特朗数。以内所有的阿姆斯特朗数。407=4407=43 3+0+03 3+7+73 3 定义三个变量定义三个变量a, b, c作为各个位上的数字作为各个位上的数字main( ) int a,b,c; for (a=1;a=9;a+) * a 的范围的范围 * for(b=0;b
19、=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=100;n=999;n+) *n在在所有的三位数中循环所有的三位数中循环 * a=n%10; * n的个位的个位 * b=n/10%10; *n 的十位的十位 * c=n
20、/100; *n 的百位的百位 * if(n=a*a*a+b*b*b+c*c*c) printf(“%dn”,n); 首页上页下页节末页结束结果：结果：153370371407题题4.604.60 任意输入一个偶数，将它分解成两个素数之和任意输入一个偶数，将它分解成两个素数之和 main( ) int j,k,n,m; scanf(“%d”,&n); 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; 如何判断一个数是素数如何判断一个数是素数题题4.614.61 如果整数如
21、果整数A A的因子之和是的因子之和是B B，而且而且B B的因子之和是的因子之和是A A，则则A A与与B B是亲密数。找出是亲密数。找出30003000以内的全部亲密数以内的全部亲密数 1 定义一个变量定义一个变量 a 在在1-3000以内循环以内循环2 若有：若有：a%i =0,则则 i为为a的一个因子，找出的一个因子，找出a的的全部因子全部因子3 将将a的的因子求和，并赋值给因子求和，并赋值给m，重复重复2步骤，求步骤，求m的的因子之和因子之和n4 判断判断a与与n是否相等是否相等main( ) int a ,i , m , n; for(a=1;a3000;a+) for(m=0, i
22、 =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); 题题4.694.69 编写程序，输出编写程序，输出10001000以内的所有完数及其因子。以内的所有完数及其因子。例如：例如：6=1+2+36=1+2+3 1 1 定义变量定义变量i i，从从1-10001-1000循环循环 2 2 将因子存进一个整形数组，求数组中各元素之和将因子存进一个整
23、形数组，求数组中各元素之和s s 3 3 判断判断 s s 与与i 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); 题题4.824.82 求一个三位数，该三位数等于每位数字的阶乘之和求一个三位数，该三位数等于每位数字的阶乘之和 1 1 定义三个变量定义三个变量a, b, ca, b, c作为各个位上的数字作为各个位上的数字 2 2 调用一个阶乘函数调用一个阶乘
24、函数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教材教材6-266-26 用用4040元钱买苹果，西瓜和梨共元钱买苹果，
25、西瓜和梨共100100个，个，3 3种水果。苹种水果。苹果果0.40.4元一个，西瓜元一个，西瓜4 4元一个，梨元一个，梨0.20.2元一个，输出全部购买方案。元一个，输出全部购买方案。 1 1 避免浮点数的恒等比较，因此不用几元钱做单位。避免浮点数的恒等比较，因此不用几元钱做单位。 2 2 定义苹果定义苹果x, x, 梨梨y,y,西瓜西瓜z zmain( ) 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,524,72,443,54,362,36,281,18,1 1 1 正确找出穷举的范围正确找出穷举的范围 2 2 如何描述问题如何描述问题 3 3 如何找一个数的因子如何找一个数的因子 4 4 如何判断素数如何判断素数5 5 累加器的使用累加器的使用
