0467.cC
海量文库 文档专家
相关文档
当前位置:首页 >> >>

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

穷举法 基本思想是首先根据问题的部分条件预 估答案的范围,然后在此范围内对所有可能的情况 进行逐一验证,直到全部情况通过了验证为止。若 某个情况使验证符合题目的全部条件,则该情况为 本题的一个答案;若全部情况验证结果均不符合题 目的全部条件,则说明该题无答案。
特点 算法简单,容易理解,但运算量大。通常可 以解决“有几种组合”、“是否存在”、求解不定 方程等类型的问题。用循环结构实现。
结束 首页 上页 下页 末页 节

要素

循环变量初值 循环条件 循环体 循环变量的增量

进入循环之前执行,只做一次 多次判断 重复执行的语句 多次执行,控制循环结束

语句 嵌套

while ( ) do –while ( ); for (……) if---goto

for ( i=999 ; i >= 100 ; i-- )
适合用在循环次数已 知的场合
j=1

i=1时 j=2

for(i=1;i<=9;i++)

.

for(j=1;j<=9;j++) {……}

i=2时 .

.

j=9

.

结束 首页 上页 下页 末页 节

题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++)

程序运算100万次

if( 5*x+ 3*y+ z/3==100 && x+y+z==100)

100元钱

买100只鸡

x 最多为20,y 最多为34,当 x, y 已确定时, z的值为 100-x-y,不必对z进行循环。

结束 首页 上页 下页 末页 节

main( )

所求的z不能被3

{ int x,y,z; 整除如何解决?

for (x=1;x<20;x++)

for(y=1;y<=34-x;y++)

{ z=100-x-y;

if ( 5*x+3*y+z/3==100 )

printf(“%d,%d,%d\n”,x,y,z); } }

3 20 77 4 18 78 7 13 80 8 11 81 11 6 83 12 4 84

if ( (5*x+3*y+z/3==100) && z%3== 0) printf(“%d,%d,%d\n”,x , y , z);

特点 算法简单,容易理解,但运算量大。

结束 首页 上页 下页 末页 节

题4.33 编写程序求出 555555 的约数中最大的三位数是多少

1 理解约数:n% k==0 则 k是n 的约数 2 最大数:从大到小循环,找到一个约数就退出循环

main( )

{ int a;

for ( a= 999 ; a>=100 ; a - -) \*正确地表示三位数的范围 *\

if ( 555555%a==0)

\* 如果555555能被a整除 *\

break;

\* 结束循环

*\

printf(“%d”,a);

}

结束 首页 上页 下页 末页 节

题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++) for(a=1;a<=9;a++) for(b=1;b<=9;b++)

\* n*n是个四位数 *\ \ * a 的范围 *\ \* b 的范围 *\

if(n*n == a*1000+a*100+b*10+b) printf(“%d%d%d%d”,a,a,b,b); printf(“%d\n”,n);
}

结果:7744 88的平方

题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=%d\n”,x,y,z);

k++; }

}

结束 首页 上页 下页 末页 节

题4.51 100匹马驮100担货,大马一匹驮3担,中马一匹驮2担,
小马两匹驮1担,求大、中、小马的数目。

1 定义三种数目为 x, y, z , 分析方法同100元钱买100只鸡 2 注意 z 能够被2 整除

main( )

{ int x,y,z;

for (x=1;x<34;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,%d\n”,x,y,z); }

共有100担货

}

结束 首页 上页 下页 末页 节

题 4.52 将一元钱换成一分,二分和五分的硬币,共有多少
种换法?
1 定义变量 a, b, c 作为三种硬币的个数 2 定义变量 k 作为计数器 3 总的面值是100分,但总的硬币个数不是100个
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( “%d\n”, k) ;
}
结束 首页 上页 下页 末页 节

题4.53 显示200以内的完全平方数和它们的个数 A2+B2 = C2

1 理解题意:A2 、B2 和C2的值均不超过200 2 统计个数的方法: 计数器

main( ) { int a,b,c,k=0; for (a=1;a*a<=200;a++) for(b=1;b*b<=200;b++) for(c=1;c*c<=200;c++)

\* a 的范围 *\ \* b 的范围 *\ \* c 的范围 *\

结果: 3,4,5 4,3,5 5,12,13 6,8,10 8,6,10 12,5,13

if( a*a+b*b==c*c)

\* 完全平方数的特点 *\

{ printf(“%d,%d,%d\n”,a,b,c) ;

k++;

\* 计数器 加 1 *\

}

}

结束 首页 上页 下页 末页 节

题4.54
n的值

设n 是一个四位数,它的9倍恰好是它的反序数,求

如何表示四位数

1 定义四个变量 a,b,c,d 作为该数各个位上的数字

则a*1000+b*100+c*10+d 为该数的大小

例如:2134表示为2*1000+1*100+3*10+4

2 定义一个变量 n ,则各个位分别为:

个位:n%10

从 1---9

十位:n/10%10

从 0---9

百位:n/100%10 千位:n/1000

从 0---9 从 1---9

3 正确表示各个位上数字的范围:

n的最高位不能 是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)

printf(“%d%d%d%d\n”,a,b,c,d) ;

}

结果:1089

main( ) { int n;

for(n=1000;n<=9999;n++)

\*n是一个四位数*\

if(9*(n/1000*1000+n/100%10*100+n/10%10*10+n%10)==

n%10*1000+n/10%10*100+n/100%10*10+n/1000)

Printf(“%d”,n); }
结束 首页 上页 下页 末页 节

题4.55 一个数的等于它的反序数,则为对称数,求1993以内
的最大二进制的对称数

1 将十进制数转换成二进制,存入一个数组a[16 ]中

2 编一个函数,判断是否为对称数,返回为 1 或 0

3 求最大数,从大到小循环,找到一个就结束, 用break

main( ) { int i , n,k,j, a[16]={0}; for(i=1993; i >=1;i- - ) { k=i; n=0; While(k>0) { a[n++]=k%2; k=k/2; } if(fun(a,n-1)) break; }
printf(“%d=“,i); for(j=0;j<n-1;j++) printf(“%3d”,a [ j ]); }

fun(int b[ ],int n) { int j,k=1; for(j=0;j<n;j++) if(b[ j ]!=b[n-j-1]) { k=0; break; } return k; }
结果: 1975=1110110111

题4.56 编写程序,求下式中各字母所代表的数字

PEAR ARA

1 定义四个变量 P,E,A,R 作为各个位上的数字 则P*1000+E*100+A*10+R 为该数的大小

PEA
main( )

2 注意各个变量变化的范围

1098 989

{ int p,e,a,r ; for (p=1;p<=9;p++)

109
\* 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%d\n”,p,e,a,r) ;

结果:1098

}

结束 首页 上页 下页 末页 节

题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++) for(b=0;b<=6;b++)

\* a 的范围 *\ \* b的范围 *\

七进制 :503 九进制:305 十进制:248

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); \* 显示这个三位数 *\

}

结束 首页 上页 下页 末页 节

题4.59 编写程序求1000以内所有的阿姆斯特朗数。
407=43+03+73

定义三个变量a, b, c作为各个位上的数字

main( )

{ int a,b,c;

for (a=1;a<=9;a++) for(b=0;b<=9;b++)

\* a 的范围 *\ \* 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++) { a=n%10; b=n/10%10; c=n/100;

\*n在所有的三位数中循环 *\ \* n的个位 *\ \*n 的十位 *\ \*n 的百位 *\

if(n==a*a*a+b*b*b+c*c*c)

printf(“%d\n”,n);

}

}

结果:

153

370

371

结束 首页 上页 下页 末页 节

407

题4.60 任意输入一个偶数,将它分解成两个素数之和
如何判断一个数是素数

main( ) {

int j,k,n,m;

scanf(“%d”,&n);

for( j=2;j<n;j++)

{ for( k=2;k<j;k++)

if(j%k==0) break;

if(k>=j)

{ m=n- j;

for(k=2;k<m;k++)

if(m%k==0) break;

if(k>m)

{ printf(“%4d=%4d+%4d\n”,n,j,m);

break; }

}

}

}

题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;a<3000;a++)

{ for(m=0, i =1;i<=a/2;i++)

if(a%i==0) m+=i;

for(n=0,i=1;i<=m/2;i++)

if(m%i==0) n+=I

if(a==n&&a<m)

printf(“%4d---%4d”,a,m);

}

}

/* a的因子和为m */
/* m的因子和为n */ /* a与n相等 */

题4.69 编写程序,输出1000以内的所有完数及其因子。
例如:6=1+2+3
1 定义变量i,从1---1000循环 2 将因子存进一个整形数组,求数组中各元素之和s 3 判断 s 与i 是否相等 main( ) { int i,j,m,s,k,a[20]; for(i=0;i<=1000;i++) { m=i;s=0;k=0; while(m>0) { for(j=1;j<m;j++) if(m%j==0) { s=s+j; m=m/j; a[k++]=j;} if(j>=m) break; } If(s!=0&&I==s+m) { a[k++]=m; for(j=0;j<k;j++) printf(“%4d”,a[j]); printf(“==%4d\n”,I); } } }

题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

教材6-26 用40元钱买苹果,西瓜和梨共100个,3种水果。
苹果0.4元一个,西瓜4元一个,梨0.2元一个,输出全部购买方 案。
1 避免浮点数的恒等比较,因此不用几元钱做单位。
2 定义苹果x, 梨y,西瓜z

main( ) { int x,y,z; for (x=1;x<100;x++)
for(y=1;y<200;y++) { z=100-x-y;
if ( 4*x+2*y+40*z==400 ) printf(“%d,%d,%d\n”,x,y,z); } }

结果: xy z 5, 90,5 24,72,4 43,54,3 62,36,2 81,18,1

1 正确找出穷举的范围 2 如何描述问题 3 如何找一个数的因子 4 如何判断素数 5 累加器的使用


网站首页 | 网站地图
All rights reserved Powered by 0467资源网 0467.cc
copyright ©right 2014-2019。
文档资料库内容来自网络,如有侵犯请联系客服。liunxqq@126.com