《用穷举法设计程序》习题精讲

《用穷举法设计程序》

习题精讲问题1：从1～10中找出所有是3倍数的数。用流程图描述解决此数学问题的算法。输出i开始i←1i≤10i←i+1结束NYi是3的倍数YN#include<cstdio>usingnamespacestd;intmain(){inti=1;

while(i<=10)

{if(i%3==0)printf(“%d\n”,i);i=i+1;

}}问题2：从1～100中找出所有能被7或9整除的数。用流程图描述解决此数学问题的算法。输出i开始i←1i≤100i←i+1结束NYi能被7或9整除YN#include<cstdio>usingnamespacestd;intmain(){inti;for(i=1;i<=100;i=i+1)

{if(i%7==0||i%9==0)printf(“%d\n”,i);}}问题3：打印输出由1、2……8、9这九个数字组成的所有可能的二位数n。用流程图描述。分析：个位数上的数字可以是那几种数字？用变量i来表示。十位数上的数字可以是那几种数字？用变量j来表示。找出二位数n与i、j之间的关系。提示：548=5×100+4×10+8输出n开始j←1j≤9i←i+1结束NNi←1Yi≤9n←j*10+iYj←j+1执行过程：j=1in34567891021111213141516171819j=2#include<cstdio>usingnamespacestd;intmain(){intj,i,n;

j=1;While(j<=9)

{i=1;

While(i<=9)

{

n=j*10+i;printf(“%d”,n);i=i+1;

}j=j+1;

}

}问题4：打印输出由1、2……8、9这九个数字组成的所有可能的二位数n。#include<cstdio>usingnamespacestd;intmain(){inti,j;for(i=1;i<=9;i++){for(j=1;j<=9;j++){printf("%d\n",i*10+j);}}return0;}

标准输入输出速度比较快。流输入输出在数据比较多，比如1000000个数据的时候会很慢。问题5:(四大湖问题)上地理课时，四个学生回答我国四个淡水湖大小时说：

A学生：洞庭湖最大，洪泽湖最小，鄱阳湖第3

B学生：洪泽湖最大，洞庭湖最小，鄱阳湖第2，太湖第3

C学生：洪泽湖最小，洞庭湖第3

D学生：鄱阳湖最大，太湖最小，洪泽湖第2，洞庭第3

对于湖的大小，每个学生仅答对一个，请编程判断四个湖的大小1.分析与算法设计(1)定义变量：

a—洞庭湖，a可能的取值{1,2,3,4}

b—洪泽湖，b可能的取值{1,2,3,4}

c—鄱阳湖，c可能的取值{1,2,3,4}

d—太湖，d可能的取值{1,2,3,4}

a,b,c,d四个变量的取值互不相同，1表示最大，4表示最小(2)用变量表示条件

A学生的叙述可表示为：a==1,b==4,c==3这是三个关系表达式，由于每个学生的叙述只有一个正确，所以这三个关系表达式的值的和应等于1。

A学生的叙述可表示成：

((a==1)+(b==4)+(c==3）)==1

同理，B学生的叙述表示成：

((b==1)+(a==4)+(c==2)+(d==3))==1

(2)用变量表示条件

A学生的叙述可表示为：a==1,b==4,c==3这是三个关系表达式，由于每个学生的叙述只有一个正确，所以这三个关系表达式的值的和应等于1。C学生的叙述可表示成：

((b==4)+(a==3))==1D学生的叙述可表示成：

((c==1)+(d==4)+(b==2)+(a==3))==1

for(a=1;a<=4;a++)for(b=1;b<=4;b++)for(c=1;c<=4;c++)for(d=1;d<=4;d++){ca=((a==1）+（b==4）+(c==3）)==1; cb=((b==1)+(a==4)+(c==2)+(d==3))==1;cc=((b==4)+(a==3))==1;cd=((c==1)+(d==4)+(b==2)+(a==3))==1;

if(ca&&cb&&cc&&cd){printf("TongTing=%d\n",a);

printf("Hongzhe=%d\n",b); printf("Poyang=%d\n",c);

printf("Taihu=%d\n",d);}}//endfor(3)穷举:穷举a,b,c,d四个变量的所有可能取值,进行测试，满足前述四个条件的取值就是我们所要的结果问题6：输入绳子的长度n，将该绳子分成三段，每段的长度为正整数，输出由该三段绳子组成的三角形个数。

算法分析：

没有公式直接求出三角形的个数,所以程序只能采用穷举法,一一验证范围内的数是否能构成三角形,若是则累计。