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

1、 基本思想是首先根据问题的部分条件预基本思想是首先根据问题的部分条件预估答案的估答案的范围范围，然后在此范围内对，然后在此范围内对所有可能的情况所有可能的情况进行逐一验证，直到全部情况通过了验证为止。若进行逐一验证，直到全部情况通过了验证为止。若某个情况使验证符合题目的全部条件，则该情况为某个情况使验证符合题目的全部条件，则该情况为本题的一个答案；若全部情况验证结果均不符合题本题的一个答案；若全部情况验证结果均不符合题目的全部条件，则说明该题无答案。目的全部条件，则说明该题无答案。特点特点 算法简单，容易理解，但运算量大。通常可算法简单，容易理解，但运算量大。通常可以解决以解决“有几种组合有几

2、种组合”、“是否存在是否存在”、求解不定、求解不定方程等类型的问题。方程等类型的问题。首页上页下页节末页结束循环变量初值循环变量初值循环条件循环条件循环体循环体循环变量的增量循环变量的增量进入循环之前执行，只做一次进入循环之前执行，只做一次多次判断多次判断重复执行的语句重复执行的语句多次执行，控制循环结束多次执行，控制循环结束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

3、时时 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;z+) if( 5*x+ 3*y+ z/3=100 & x+y+z=100) 程

4、序运算程序运算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; * 结束循环结束循环 * printf(“%d”,a); 题题4.49 4.49 一辆卡车违反交通

5、规则，撞人逃跑了。现场三人目击，一辆卡车违反交通规则，撞人逃跑了。现场三人目击，记下了车号特征：前两位数字相同，后两位数字相同，四位数恰记下了车号特征：前两位数字相同，后两位数字相同，四位数恰好是一个整数的平方。求该车号。好是一个整数的平方。求该车号。 1 1 将车号假定为将车号假定为aabbaabb，是个四位数，是个四位数，a,ba,b的变化范围是的变化范围是1-91-9 2 2 四位数的范围是四位数的范围是1000-99991000-9999，某整数的平方是四位数，某整数的平方是四位数 3 3 预估整数的范围：预估整数的范围：3232的平方是的平方是10241024，9494的平方是的平方

6、是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个白球和个白球和6 6个黑球个黑球, ,每次从每次从中任取中任取8 8个，求共

7、有多少总颜色搭配。个，求共有多少总颜色搭配。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

8、(“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+) * 大马数目的范围大马数目的范围 * for(y=1;y=50;y+) * 中

9、马数目的范围中马数目的范围 * 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;b=50;b+) * 2分钱可能的个数分钱可能的个数 * for(c=

10、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 = c= c2 21 理解题意：理解题意：a a2 2 、b b2

11、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 * 首页上页下页节末页结束结果：结果：3,4,54,3,55,12,136,8,

12、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/10%10百位：百位：n/100%10 千位：千位：n/10003

13、正确表示各个位上数字的范围：正确表示各个位上数字的范围： 从从 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+c*10+d)=d*1000+c*100+b*10+a) pri

14、ntf(“%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 1975=1110110111 题题4.56 4.56

15、 编写程序，求下式中各字母所代表的数字编写程序，求下式中各字母所代表的数字 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;a=9;a+) * a 的范围的范围 * for(r=0;r=9

16、;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 一个自然数的七进制是一个三位数，其九进制也是一一个自然数的七进制是一个三位数，其九进制也是一个三位数，且这两个三位数数码顺序正好相反，求这个三位数个三位数，且这两个三位数数码顺序正好相反，求这个三位数 1 定义三个变量定义三个变量a, b, c作为各

17、个位上的数字作为各个位上的数字 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); * 显示这三个数字显示这三个数字 * print

18、f(“%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=9;b+) * b的范围的范围 * for(c=0;c=9;c+

19、) * 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/100; *n 的百位的百位 * if(n=a*a*a+b*b*

20、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 如果整数如果整数a a的因子之和是的因子之和是b b，而且，而且b

21、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 =1;i=a/2;i+) if(a%i=0) m+

22、=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 将因子存进一个整形数组，求数组中各元素之和将因子存进一个整形数组，求数组中各元素之和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作为各个位上的数