百雞百錢問題及其算法分析.docx

百錢百雞問題的最佳解決方案（陜西師范大學(xué)計算機(jī)科學(xué)學(xué)院10級計科一班 西安 710062）摘要：本文主要討論百雞百錢問題，通常用蠻力法策略，用枚舉法表現(xiàn)，排除明顯不合理情況，列舉出符合問題的解，分別驗(yàn)證解的可行性，得到最優(yōu)算法。關(guān)鍵詞：蠻力法；枚舉；百雞百錢；The money the chicken question the best solutionduan xi-juan, zhongmei, zhao shan-shan, zhao ya-wen(School of Computer Science, ,Shanxi Normol University, Xian 710062)Abstact :In this article, we mainly discuss the chicken and the money problem. Usually use brute force method strategy, with enumeration method performance, eliminate obviously unreasonable situation, Enumerate conform to the problem solution, which verified the feasibility of the solution, and get the optimal algorithm. Keywords: The brute force method;Enumeration;Hundred chickens money1引言在求解一個較小規(guī)模的問題時，可以根據(jù)問題中的約束條件把可能的情況一一列舉出來，然后注意嘗試從中找到滿足約束條件的解，若該問題規(guī)模較大，符合條件的情況很多，則需要進(jìn)一步考慮，排除一些明顯不合理的情況，盡可能減少問題可能解的列舉數(shù)目。2問題描述百錢百雞問題。中國古代數(shù)學(xué)家張丘建在他的算經(jīng)中提出了他的著名的“百錢百雞問題”：雞翁一，值錢五；雞母一，值錢三；雞雛三，值錢一；百錢買百雞，翁、母、雛各幾何？3算法設(shè)計根據(jù)問題中的約束條件將可能的情況一一列舉出來，但如果情況很多，排除一些明顯的不會理的情況，盡可能減少問題可能解的列舉數(shù)目，然后找出滿足問題條件的解。1）算法設(shè)計一首先問題有三種不同的雞，那么我們可以設(shè)雞翁為x只，雞母為y只，雞雛為z只。由題意給出一共要用100錢買一百只雞，如果我們?nèi)抠I雞翁最多可以買1005=20只，顯然x的取值范圍是120之間；如果全部買雞母最多可以買100333只，顯然y的取值范圍在133之間；如果全部買雞雛最多可以買1003300只，可是題目規(guī)定是買100只，所以z的取值范圍是1100.那么約束條件為：xyz100且5x3y+1003100.開始定義x.y,zx=20?y=33?z=99?百雞百錢？結(jié)束N輸出結(jié)果NNNYYYY流程圖如下： 算法1程序運(yùn)行結(jié)果截圖：2）算法設(shè)計二假如我設(shè)了雞翁和雞母的個數(shù)為x和y了，那么雞翁和雞母的數(shù)量就是確定的，那么雞雛的數(shù)量就是固定的為100xy,那么此時就不再需要進(jìn)行枚舉了，約束條件就只有一個了：5x3yz3100.流程圖如下所示：結(jié)束圖5-9 程序執(zhí)行流程圖算法2程序運(yùn)行結(jié)果截圖：4算法分析算法設(shè)計一需要枚舉嘗試次，算法的效率顯然很低。算法設(shè)計二只須枚舉嘗試次。實(shí)現(xiàn)時約束條件又限定z能被3整除時，才會判斷“”。這樣省去了不整除3時的算術(shù)計算和條件判斷，進(jìn)一步提高了算法的效率。5結(jié)束語有此例可以看出，枚舉法是蠻力策略的一種變現(xiàn)形式，也是一種使用非常普遍的思維方法。然而對于同一個問題，可以有不同的枚舉范圍，不同的枚舉對象，解決問題的效率差別就會很大，選擇合適的方法會讓解決問題的效率大大提高。6參考文獻(xiàn)1呂國英