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

《穷举法基本思想是首先根据问题的部分条件预估答案的范围》由会员分享，可在线阅读，更多相关《穷举法基本思想是首先根据问题的部分条件预估答案的范围（23页珍藏版）》请在装配图网上搜索。

1、穷举法基本思想是首先根据问题的部分条件预估答案的范围 Still waters run deep.流静水深流静水深,人静心深人静心深 Where there is life,there is hope。有生命必有希望。有生命必有希望循环变量初值循环变量初值循环条件循环条件循环体循环体循环变量的增量循环变量的增量进入循环之前执行，只做一次进入循环之前执行，只做一次多次判断多次判断重复执行的语句重复执行的语句多次执行，控制循环结束多次执行，控制循环结束while()do while();for(）if-goto 适合用在循环次数已适合用在循环次数已知的场合知的场合首页上页下页节末页结束for(i=

2、999;i=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;z+)if(5*x+3*y+

3、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;*结束循环结束循环 *printf(“%d”,a);题题4.49 4.49 一辆卡车违反交通规则，撞人逃

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

5、36main()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个，求共有多少总颜色搭配。个，求共有多少总颜色搭配。1 找出各类球

6、可能出现的范围找出各类球可能出现的范围 红球红球 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+;首页上页下页节末页结束题题4.5

7、14.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+)*中马数目的范围中马数目的范围*z=100-x-y;*总数为总数为100，z不循环不循环*if(3*x+2*y+z/2=10

8、0)&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=0;c=20;c+)*5分钱可能的个数分钱可能的个数*if(a+2*b+5*c=100)*总面值为总面值为1元元 *k+;printf(“%dn”,k);1定义变量定义变量 a,b

9、,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 2 和和C C2 2的值均不超过的值均不超过2002002 统计个数的方法：统计个数的方法：计数器计数器main()int a,b,c,k=0;for(a=1;a*a=200;a+)*a 的范围的范围*for(b=1

10、;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 是一个四位数，它的是一个四位数，它的9 9倍恰好是它的反序数，求倍恰好是它的反序数，求n n的值的值如何表示四位数如何表示四位数1 定义四个变量定义四个变量 a,b,c,d 作为该数各个位上的数字作为该

11、数各个位上的数字 则则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 正确表示各个位上数字的范围：正确表示各个位上数字的范围：从从 1-9 从从 0-9 从从 0-9 从从 1-9n的最高位不能的最高位不能是是0，反序数的，反序数的最高位也不可能最高位也不可能是是0首页上页下页节末页结束main()int a,b,c,d;for(a=1;

12、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);

13、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 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 注意各个变量变化的范围注意各个变量变化的

14、范围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 1 0 9 8 9 8 9 9 8 9 1 0 9 1 0 9 题题4.57 4.57 一个自然数的七进制是一个三位数，其九进制也是一一个自

15、然数的七进制是一个三位数，其九进制也是一个三位数，且这两个三位数数码顺序正好相反，求这个三位数个三位数，且这两个三位数数码顺序正好相反，求这个三位数 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 的范围的范

16、围 *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.594.59 编写程序求编写程序求10001000以内所有的阿姆斯特朗数。以内所有的阿姆斯特朗数。407=4407=43 3+0+03 3+7+73 3 定义三个变量定义三个变量a,b,c作为各个位上的数字作为各个位上的数字main()int a,b,c;for(a=1

17、;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=100;n=999;n+)*n在所有的三位数中循环在所有的三位数中循环*a=n%10;*n的个位的个位 *b=n/10%10;*n 的十位的十位 *c=n/1

18、00;*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 如果整数如果整数A A的因子之和是的因子之和是B

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

20、*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 是否相等是否

21、相等 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 调用一个阶乘函数调用一个阶乘函数main()int a,b,c;for(a=1;a=9;a+)*a 的范围的范围 *for(b=0;b=9;

22、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元钱买苹果，西瓜和梨共元钱买苹果，西瓜和梨共100100个，个，3 3种水果。苹种水果。苹果果0.40.4元一个，西瓜元一个，西瓜4 4元一个，梨元一个，梨0.20.2元一个，输出全部购买方案。元一个，输出全

23、部购买方案。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 累加器的使用累加器的使用