《用窮舉法設(shè)計程序》習題精講

《用窮舉法設(shè)計程序》

習題精講問題1：從1～10中找出所有是3倍數(shù)的數(shù)。用流程圖描述解決此數(shù)學問題的算法。輸出i開始i←1i≤10i←i+1結(jié)束NYi是3的倍數(shù)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整除的數(shù)。用流程圖描述解決此數(shù)學問題的算法。輸出i開始i←1i≤100i←i+1結(jié)束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這九個數(shù)字組成的所有可能的二位數(shù)n。用流程圖描述。分析：個位數(shù)上的數(shù)字可以是那幾種數(shù)字？用變量i來表示。十位數(shù)上的數(shù)字可以是那幾種數(shù)字？用變量j來表示。找出二位數(shù)n與i、j之間的關(guān)系。提示：548=5×100+4×10+8輸出n開始j←1j≤9i←i+1結(jié)束NNi←1Yi≤9n←j*10+iYj←j+1執(zhí)行過程：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這九個數(shù)字組成的所有可能的二位數(shù)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;}

標準輸入輸出速度比較快。流輸入輸出在數(shù)據(jù)比較多，比如1000000個數(shù)據(jù)的時候會很慢。問題5:(四大湖問題)上地理課時，四個學生回答我國四個淡水湖大小時說：

A學生：洞庭湖最大，洪澤湖最小，鄱陽湖第3

B學生：洪澤湖最大，洞庭湖最小，鄱陽湖第2，太湖第3

C學生：洪澤湖最小，洞庭湖第3

D學生：鄱陽湖最大，太湖最小，洪澤湖第2，洞庭第3

對于湖的大小，每個學生僅答對一個，請編程判斷四個湖的大小1.分析與算法設(shè)計(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這是三個關(guān)系表達式，由于每個學生的敘述只有一個正確，所以這三個關(guān)系表達式的值的和應等于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這是三個關(guān)系表達式，由于每個學生的敘述只有一個正確，所以這三個關(guān)系表達式的值的和應等于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四個變量的所有可能取值,進行測試，滿足前述四個條件的取值就是我們所要的結(jié)果問題6：輸入繩子的長度n，將該繩子分成三段，每段的長度為正整數(shù)，輸出由該三段繩子組成的三角形個數(shù)。

算法分析：

沒有公式直接求出三角形的個數(shù),所以程序只能采用窮舉法,一一驗證范圍內(nèi)的數(shù)是否能構(gòu)成三角形,若是則累計。