C語(yǔ)言程序設(shè)計(jì)---窮舉法對(duì)象：08計(jì)1課程開(kāi)始的思考題

思考：某個(gè)暑假小明攜帶密碼行李箱外出旅游，旅行途中發(fā)現(xiàn)自己忘記了開(kāi)鎖的密碼，怎么辦？窮舉法的思路 窮舉算法是程序設(shè)計(jì)中使用得最為普遍、大家必須熟練掌握和正確運(yùn)用的一種算法。它利用計(jì)算機(jī)運(yùn)算速度快、精確度高的特點(diǎn)，對(duì)要解決問(wèn)題的所有可能情況，一個(gè)不漏地進(jìn)行檢查，從中找出符合要求的答案。

例

1

：

我國(guó)古代數(shù)學(xué)家張丘建在《算經(jīng)》中出了這樣一道題目：雞翁一，值五錢(qián)，雞母一，值三錢(qián)，雞雛三，值一錢(qián)，百錢(qián)買(mǎi)百雞，問(wèn)雞翁、雞母、雞雛各幾何？分析：這就是窮舉法當(dāng)中的典型例題百錢(qián)百雞問(wèn)題。題目要我們找出符合條件的雞翁、雞母、雞雛的個(gè)數(shù)。答案顯然是一組數(shù)據(jù)。首先分析一下問(wèn)題所涉及的情況。百錢(qián)如果全買(mǎi)公雞，可以買(mǎi)0~20只；百錢(qián)如果全買(mǎi)母雞，可以買(mǎi)0~33只；百錢(qián)如果全買(mǎi)小雞，可以買(mǎi)0~300只，但百雞限定最多99只，小雞數(shù)必須是3的倍數(shù)； 綜上，我們發(fā)現(xiàn)公雞21種買(mǎi)法，母雞34種，小雞33種，所以總共面臨著21×34×34=24276種買(mǎi)法。

分析進(jìn)入第二步

現(xiàn)在我們已經(jīng)了解了所有可能的情況，按照窮舉法解題的思路，我們需要設(shè)計(jì)一下正確買(mǎi)法所需滿(mǎn)足的條件，假設(shè)公雞數(shù)為i，母雞數(shù)為j，小雞數(shù)為k，則得到如下方程：i*5+j*3+k/3==100I+j+k==100百錢(qián)百雞編寫(xiě)程序#include<stdio.h>main(){ inti,j,k; /*準(zhǔn)備輸出格式*/ printf(“\t公雞\t母雞\t小雞\n”); for(i=0;i<=20;i++) for(j=0;j<=33;j++) for(k=0;k<=99;k+=3) if(i+j+k==100&&i*5+j*3+k/3==100) printf(“\t%d\t%d\t%d\n”,i,j,k);}我們運(yùn)行演示一下小結(jié)思考

剛才的百錢(qián)百雞程序在循環(huán)次數(shù)上有24276次之多，那么有什么辦法可以減少循環(huán)次數(shù)，而又不會(huì)遺漏答案呢？分析 分析后我們發(fā)現(xiàn)第一種思路沒(méi)前途，因?yàn)槿≈登闆r的分析很合理，即便可以減少也只是一點(diǎn)點(diǎn)，對(duì)總數(shù)2萬(wàn)多來(lái)說(shuō)，減少的幅度很不明顯。 所以我們考慮第二種思路，減少循環(huán)的重?cái)?shù)，我們觀察方程后發(fā)現(xiàn)，其實(shí)，三重循環(huán)可以變成兩重循環(huán)。改進(jìn)后的程序#include<stdio.h>main(){ inti,j,k; /*準(zhǔn)備輸出格式*/ printf("\t公雞\t母雞\t小雞\n"); for(i=0;i<=20;i++) for(j=0;j<=33;j++) { k=100-i-j; if(i*5+j*3+k/3==100) printf("\t%d\t%d\t%d\n",i,j,k); }}我們運(yùn)行演示一下完善后的改進(jìn)程序#include<stdio.h>main(){ inti,j,k; /*準(zhǔn)備輸出格式*/ printf("\t公雞\t母雞\t小雞\n"); for(i=0;i<=20;i++) for(j=0;j<=33;j++) { k=100-i-j; if(k%3==0&&i*5+j*3+k/3==100) printf("\t%d\t%d\t%d\n",i,j,k); }}密碼箱問(wèn)題的演示程序#include<stdio.h>main(){ inti,key; printf("請(qǐng)?jiān)O(shè)定旅行箱的密碼(000-999)："); scanf("%d",&key); printf("\n你的旅行箱密碼是："); for(i=0;i<=999;i++) if(i==key) if(i<10)printf("00%d\n",i); elseif(i<100)printf("0%d\n",i); elseprintf("%d\n",i);}模仿練習(xí)例

2

：

36

塊磚，

36

人搬。男搬

4

，女搬

3

，兩個(gè)小兒抬一磚。要求一次全搬完。問(wèn)需男、女、小兒各若干（必須都有）？

請(qǐng)同學(xué)們先分析第一步：?jiǎn)栴}所涉及的情況分析

： 題目要我們找出符合條件的男生、女生和小孩的人數(shù)。答案顯然是一組數(shù)據(jù)。首先分析一下問(wèn)題所涉及的情況。對(duì)于男生來(lái)說(shuō)，至少要有一人；每個(gè)男生可以搬

4

塊磚，那么

36

塊磚最多

9

個(gè)男生足夠，共有

9

種不同取值。同樣，女生有

12

種不同取值。兩個(gè)小孩抬一塊磚，至少要有兩個(gè)小孩，最多

36

個(gè)，并且小孩的人數(shù)必須是個(gè)偶數(shù)，所以小孩的人數(shù)可以取

18

種不同的值。最壞情況下，男生、女生和小孩的人數(shù)可以是

9

×

12

×

18

＝

1944

種不同組合。

分析第二步：答案滿(mǎn)足所需的條件方程k=36-i-ji*4+j*3+k/2==36注意：k必須是2的倍數(shù)本節(jié)內(nèi)容總結(jié) 窮舉法問(wèn)題在解題中要特別注意以下幾個(gè)方面：對(duì)情況的分析要準(zhǔn)確，即在答案范圍的分析時(shí)不能漏掉答案對(duì)方程的整理后注意某些值的限定，如小雞必須為3的倍數(shù)，在編寫(xiě)程序中要反映出來(lái)課后作業(yè)換零