百雞百錢問(wèn)題及其算法分析.docx

百錢百雞問(wèn)題的最佳解決方案（陜西師范大學(xué)計(jì)算機(jī)科學(xué)學(xué)院10級(jí)計(jì)科一班 西安 710062）摘要：本文主要討論百雞百錢問(wèn)題，通常用蠻力法策略，用枚舉法表現(xiàn)，排除明顯不合理情況，列舉出符合問(wè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引言在求解一個(gè)較小規(guī)模的問(wèn)題時(shí)，可以根據(jù)問(wèn)題中的約束條件把可能的情況一一列舉出來(lái)，然后注意嘗試從中找到滿足約束條件的解，若該問(wèn)題規(guī)模較大，符合條件的情況很多，則需要進(jìn)一步考慮，排除一些明顯不合理的情況，盡可能減少問(wèn)題可能解的列舉數(shù)目。2問(wèn)題描述百錢百雞問(wèn)題。中國(guó)古代數(shù)學(xué)家張丘建在他的算經(jīng)中提出了他的著名的“百錢百雞問(wèn)題”：雞翁一，值錢五；雞母一，值錢三；雞雛三，值錢一；百錢買百雞，翁、母、雛各幾何？3算法設(shè)計(jì)根據(jù)問(wèn)題中的約束條件將可能的情況一一列舉出來(lái)，但如果情況很多，排除一些明顯的不會(huì)理的情況，盡可能減少問(wèn)題可能解的列舉數(shù)目，然后找出滿足問(wèn)題條件的解。1）算法設(shè)計(jì)一首先問(wèn)題有三種不同的雞，那么我們可以設(shè)雞翁為x只，雞母為y只，雞雛為z只。由題意給出一共要用100錢買一百只雞，如果我們?nèi)抠I雞翁最多可以買1005=20只，顯然x的取值范圍是120之間；如果全部買雞母最多可以買100333只，顯然y的取值范圍在133之間；如果全部買雞雛最多可以買1003300只，可是題目規(guī)定是買100只，所以z的取值范圍是1100.那么約束條件為：xyz100且5x3y+1003100.開(kāi)始定義x.y,zx=20?y=33?z=99?百雞百錢？結(jié)束N輸出結(jié)果NNNYYYY流程圖如下： 算法1程序運(yùn)行結(jié)果截圖：2）算法設(shè)計(jì)二假如我設(shè)了雞翁和雞母的個(gè)數(shù)為x和y了，那么雞翁和雞母的數(shù)量就是確定的，那么雞雛的數(shù)量就是固定的為100xy,那么此時(shí)就不再需要進(jìn)行枚舉了，約束條件就只有一個(gè)了：5x3yz3100.流程圖如下所示：結(jié)束圖5-9 程序執(zhí)行流程圖算法2程序運(yùn)行結(jié)果截圖：4算法分析算法設(shè)計(jì)一需要枚舉嘗試次，算法的效率顯然很低。算法設(shè)計(jì)二只須枚舉嘗試次。實(shí)現(xiàn)時(shí)約束條件又限定z能被3整除時(shí)，才會(huì)判斷“”。這樣省去了不整除3時(shí)的算術(shù)計(jì)算和條件判斷，進(jìn)一步提高了算法的效率。5結(jié)束語(yǔ)有此例可以看出，枚舉法是蠻力策略的一種變現(xiàn)形式，也是一種使用非常普遍的思維方法。然而對(duì)于同一個(gè)問(wèn)題，可以有不同的枚舉范圍，不同的枚舉對(duì)象，解決問(wèn)題的效率差別就會(huì)很大，選擇合適的方法會(huì)讓解決問(wèn)題的效率大大提高。6參考文獻(xiàn)1呂國(guó)英