百雞百錢問題實驗報告

PAGEPAGE4百雞百錢問題摘要:本次報告主要討論百雞百錢問題，通常使用蠻力法策略，用枚舉法來表現(xiàn)，列舉出滿足問題條件的解，排除一些明顯不合理情況，分別驗證解的可行性，得到最優(yōu)算法。關(guān)鍵詞：蠻力法；枚舉法；百雞百錢；HundredchickensmoneyAbstract:Thispaperreportshundredchickensmoney,usuallyusingabruteforcemethodstrategy,useenumerationmethodtotheperformance,meettheconditionslistedproblemsolution,excludesomeobviousunreasonablesituation,respectively,toverifythefeasibilityofthesolution,optimalalgorithm.Keywords:thebruteforcemethod;enumeration;hundredchickensmoney;1引言在求解一個較小規(guī)模的問題時，可以根據(jù)問題中的約束條件把可能的情況一一列舉出來，然后注意嘗試從中找到滿足約束條件的解，若該問題規(guī)模較大，符合條件的情況很多，則需要進一步考慮，排除一些明顯不合理的情況，盡可能減少問題可能解的列舉數(shù)目。2問題概述公元前5世紀(jì)，我國古代數(shù)學(xué)家張丘建在他的《算經(jīng)》中提出了著名的百雞百錢問題“雞翁一，值錢五；雞母一，值錢三；雞雛一，值錢一；百錢買百雞，雞翁，母，雛各幾何？”算法設(shè)計根據(jù)問題中的約束條件將可能的情況一一列舉出來，但如果情況很多，排除一些明顯的不會理的情況，盡可能減少問題可能解的列舉數(shù)目，然后找出滿足問題條件的解。完成百雞百錢問題的常規(guī)算法（懶惰枚舉）的實現(xiàn)和改進算法（非懶惰枚舉）的實現(xiàn)，以實驗方法證明對于同一問題可以有不同的枚舉范圍，不同的枚舉對象，解決問題的效益差別會很大。算法設(shè)計一懶惰枚舉法：首先問題有三種不同的雞，那么我們可以設(shè)雞翁為x只，雞母為y只，雞雛為z只。由題意給出一共要用100錢買一百只雞，如果我們?nèi)抠I雞翁最多可以買100/5=20只，顯然x的取值范圍是1~20之間；如果全部買雞母最多可以買100/3=33只，顯然y的取值范圍在1~33之間；如果全部買雞雛最多可以買100*3=300只，可是題目規(guī)定是買100只，所以z的取值范圍是1~100.那么約束條件為：x+y+z=100且5*x+3*y+z/3=100。流程圖如下所示：懶惰算法算法語言描述main(){intx,y,z;//定義雞翁，雞母，雞雛 intcount=0;//統(tǒng)計時間復(fù)雜度的變量 for(x=1;x<=20;x++)//雞翁的取值范圍for(y=1;y<=34;y++)//雞母的取值范圍for(z=1;z<=100;z++)//雞雛的取值范圍100==x+y+zand100==5*x+3*y+z/3;//約束條件 Cout<<x<<y<<z;//輸出雞翁，雞母，雞雛的可能取值count++;//統(tǒng)計此算法的時間復(fù)雜度} 程序運行結(jié)果截圖：圖1——懶惰算法程序運行截圖算法設(shè)計二非懶惰枚舉法：假如我設(shè)了雞翁和雞母的個數(shù)為x和y了，那么雞翁和雞母的數(shù)量就是確定的，那么雞雛的數(shù)量就是固定的為100-x-y,那么此時就不再需要進行枚舉了，約束條件就只有一個了：5*x+3*y+z/3=100.非懶惰算法算法語言描述main(){intx,y,z;intcount;for(x=1;x<=20;x++)for(y=1;y<=33;y++){z=100-x-y;if(zmod3=0and5*x+3*y+z/3=100)cout<<x<<y<<z;//輸出雞翁，雞母，雞雛的可能取值count++;//統(tǒng)計此算法的時間復(fù)雜度} }流程圖如下所示：程序運行結(jié)果截圖：圖2——懶惰算法程序運行截圖4算法分析懶惰枚舉法需要嘗試20*34*100=68000次，算法的效率顯然很低。非懶惰枚舉法只須嘗試20*33=660次。實現(xiàn)時約束條件又限定z能被3整除時，才會判斷“”。這樣省去了不整除3時的算術(shù)計算和條件判斷，進一步提高了算法的效率。5結(jié)束語由上述實例可以看出，枚舉法是蠻力策略的一種變現(xiàn)形式，也是一種使用非常普遍的思維方法。然而對于同一個問題，可以選擇不同的枚舉范圍，不同的枚舉對象，這樣解決問題的效率差別可能會很大。所以選擇合適的方法會讓解決問題的效率大大提高。經(jīng)過這次的實驗，我們充分的認(rèn)識到團隊合作的重要性，正所謂“聚做一團火，散成滿天星”，我們要繼續(xù)加油，在算法的道路中，走的更遠(yuǎn)。6參考文獻鄭莉董淵.北京:清華大學(xué)出版社,2009.8嚴(yán)蔚