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

1、特点特点 算法简单，容易了解，但运算量大。通常可算法简单，容易了解，但运算量大。通常可以处理以处理“有几种组合、有几种组合、“能否存在、求解不定方能否存在、求解不定方程等类型的问题。用循环构造实现。程等类型的问题。用循环构造实现。循环变量初值循环变量初值循环条件循环条件循环体循环体循环变量的增量循环变量的增量进入循环之前执行，只做一次进入循环之前执行，只做一次多次判别多次判别反复执行的语句反复执行的语句多次执行，控制循环终了多次执行，控制循环终了while ( )do while ( );for (if-goto 适宜用在循环次数知适宜用在循环次数知的场所的场所for ( i=999 ; i

2、= 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=1

3、00;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; * 终了循环终了循环 *

4、printf(“%d,a); 题题4.49 4.49 一辆卡车违反交通规那么，撞人逃跑了。现场三人目一辆卡车违反交通规那么，撞人逃跑了。现场三人目击，记下了车号特征：前两位数字一样，后两位数字一样，四位击，记下了车号特征：前两位数字一样，后两位数字一样，四位数恰好是一个整数的平方。求该车号。数恰好是一个整数的平方。求该车号。 1 1 将车号假定为将车号假定为aabbaabb，是个四位数，是个四位数，a,ba,b的变化范围是的变化范围是1-91-9 2 2 四位数的范围是四位数的范围是1000-99991000-9999，某整数的平方是四位数，某整数的平方是四位数 3 3 预估整数的范围：预估整

5、数的范围：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.50 4.50 口袋里放口袋里放1212个球，个球，3 3个红球，个红球，3 3个白球

6、和个白球和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+) *

7、 黑球能够的范围黑球能够的范围 * if(x+y+z=8) printf(“x=%d,y=%d,z=%dn,x,y,z); k+; 题题4.51 1004.51 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+) * 大马数目的范围大马数目的范

8、围 * 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;b=50;b+) * 2分钱能够的个数分钱能够

9、的个数 * 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 4.53 显示显示200200以内的完全平方数和它们的个数以内的完全平方数和它们的个数 A2+B2 = A2+B2 = C2C21 了解题意：了解题意：A2 、B2 和和C2的值均不超越的

10、值均不超越2002 统计个数的方法：统计个数的方法： 计数器计数器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,108,6,1012,5,13题题4.54 4.54 设设n n

11、 是一个四位数，它的是一个四位数，它的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 正确表示各个位上数字的范围：正确表示各个位上数字的范围：

12、 从从 1-9 从从 0-9 从从 0-9 从从 1-9n的最高位不能的最高位不能是是0，反序数的，反序数的最高位也不能够最高位也不能够是是0main( ) 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

13、;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 编写程序，求下式中各字母所代表的数字编写程序，求下式中各字母所代表的数字 P E

14、 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;r+) * r的范围的范围 * if( p*1000+e*100+a*10+

15、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作为各个位上的数字作为各个位上的数字 2 留意七进制中的数字符号为留意七进制中的数字符号为 0- 6，因此，

16、因此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); * 显示这个三位数显示这个三位数 * 结果：结果：七进制七进制

17、：503九进制：九进制：305 十进制：十进制：248题题4.59 4.59 编写程序求编写程序求10001000以内一切的阿姆斯特朗数。以内一切的阿姆斯特朗数。407=43+03+73407=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

18、%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*b+c*c*c) printf(“%dn,n); 结果：结果：153370371407题题4.60 4.60 恣意输入一个偶数，将它分解成两个素数之和恣意输入

19、一个偶数，将它分解成两个素数之和 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.61 4.61 假设整数假设整数A A的因子之和是的因子之和是B B，而且，而且B B的因子之和是的因子之和是A A，那么，那么A A与与B B是亲密数。找出是亲密数。找出30003000以内的全部亲密数以内的全部亲密数 1 定义一个变量定义一个变量 a 在在1-3

20、000以内循环以内循环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+=i; /* a的因子和为的因子和为m */ for(n=0,i=1;i=m/2;i+) if(m%i=0) n+=I /* m的因子和为的因子和为n */ if(a=n

21、&am) /* a与与n相等相等 */ printf(“%4d-%4d,a,m); 题题4.69 4.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.82 4.82 求一个三位数，该三位数等于每位数字的阶乘之和求一个三位数，该三位数等于每位数字的阶乘之和 1 1 定义三个变量定义三个变量a, b, ca, b, c作为各个位上的数字作为各个位上的数字 2 2 调用一个阶乘函数调用一个阶