C語言程序設(shè)計---窮舉法.ppt

《C語言程序設(shè)計---窮舉法.ppt》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、C語言程序設(shè)計---窮舉法主講：張建青對象：08計1課程開始的思考題思考：某個暑假小明攜帶密碼行李箱外出旅游，旅行途中發(fā)現(xiàn)自己忘記了開鎖的密碼，怎么辦？窮舉法的思路窮舉算法是程序設(shè)計中使用得最為普遍、大家必須熟練掌握和正確運用的一種算法。它利用計算機運算速度快、精確度高的特點，對要解決問題的所有可能情況，一個不漏地進行檢查，從中找出符合要求的答案。用窮舉算法解決問題，通?？梢詮膬蓚€方面進行分析：一、問題所涉及的情況：問題所涉及的情況有哪些，情況的種數(shù)可不可以確定。把它描述出來。?二、答案需要滿足的條件：分析出來的這些情況，需要滿足什么條件，才成為問題的答

2、案。把這些條件描述出來。?只要把這兩個方面分析好了，問題自然會迎刃而解。例?1?：?我國古代數(shù)學家張丘建在《算經(jīng)》中出了這樣一道題目：雞翁一，值五錢，雞母一，值三錢，雞雛三，值一錢，百錢買百雞，問雞翁、雞母、雞雛各幾何？分析：這就是窮舉法當中的典型例題百錢百雞問題。題目要我們找出符合條件的雞翁、雞母、雞雛的個數(shù)。答案顯然是一組數(shù)據(jù)。首先分析一下問題所涉及的情況。百錢如果全買公雞，可以買0~20只；百錢如果全買母雞，可以買0~33只；百錢如果全買小雞，可以買0~300只，但百雞限定最多99只，小雞數(shù)必須是3的倍數(shù)；綜上，我們發(fā)現(xiàn)公雞21種買法，母雞34種，

3、小雞33種，所以總共面臨著21×34×34=24276種買法。分析進入第二步現(xiàn)在我們已經(jīng)了解了所有可能的情況，按照窮舉法解題的思路，我們需要設(shè)計一下正確買法所需滿足的條件，假設(shè)公雞數(shù)為i，母雞數(shù)為j，小雞數(shù)為k，則得到如下方程：i*5+j*3+k/3==100I+j+k==100百錢百雞編寫程序#includemain(){inti,j,k;/*準備輸出格式*/printf(“t公雞t母雞t小雞”);for(i=0;i<=20;i++)for(j=0;j<=33;j++)for(k=0;k<=99;k+=3)if(i+j+k==1

4、00&&i*5+j*3+k/3==100)printf(“t%dt%dt%d”,i,j,k);}我們運行演示一下小結(jié)思考剛才的百錢百雞程序在循環(huán)次數(shù)上有24276次之多，那么有什么辦法可以減少循環(huán)次數(shù)，而又不會遺漏答案呢？提示程序利用的是三重循環(huán)，想要減少循環(huán)次數(shù)，那么很顯然，可以從以下兩個方面思考：減少i，j，k三個循環(huán)中的某一個或者幾個的循環(huán)次數(shù)減少循環(huán)結(jié)構(gòu)的重數(shù)，三重變兩重或者一重分析分析后我們發(fā)現(xiàn)第一種思路沒前途，因為取值情況的分析很合理，即便可以減少也只是一點點，對總數(shù)2萬多來說，減少的幅度很不明顯。所以我們考慮第二種思路，減少循環(huán)的重數(shù)

5、，我們觀察方程后發(fā)現(xiàn)，其實，三重循環(huán)可以變成兩重循環(huán)。k=100-i-ji*5+j*3+k/3==100我們將條件方程改變一下：如此，便不再需要k循環(huán)了改進后的程序#includemain(){inti,j,k;/*準備輸出格式*/printf("t公雞t母雞t小雞");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%dt%dt%d",i,j,k);}}我們運行演示一下發(fā)現(xiàn)問題運行的結(jié)果出人意料，答案變多了，很明顯多

6、出的答案是不合理的(小雞的數(shù)量)原因何在？分析：在我們減少k循環(huán)之后，k的值由表達式100-i-j提供，很顯然，它不能保證出來的k是3的倍數(shù)。改善：加入判斷k值為3的倍數(shù)的條件。完善后的改進程序#includemain(){inti,j,k;/*準備輸出格式*/printf("t公雞t母雞t小雞");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%dt%dt%d",i,j,k);}}密碼箱問題的演示程

7、序#includemain(){inti,key;printf("請設(shè)定旅行箱的密碼(000-999)：");scanf("%d",&key);printf("你的旅行箱密碼是：");for(i=0;i<=999;i++)if(i==key)if(i<10)printf("00%d",i);elseif(i<100)printf("0%d",i);elseprintf("%d",i);}模仿練習例?2?：?36?塊磚，?36?人搬。男搬?4?，女搬?3?，兩個小兒抬一磚。要求一次全搬完。問需男、女、小兒各若干（必須都有）？請

8、同學們先分析第一步：問題所涉及的情況分析?：題目要我