百雞百錢問(wèn)題實(shí)驗(yàn)報(bào)告

PAGEPAGE4蠻力法之百雞百錢問(wèn)題摘要:本次報(bào)告主要討論百雞百錢問(wèn)題，通常使用蠻力法策略，用枚舉法來(lái)表現(xiàn)，列舉出滿足問(wèn)題條件的解，排除一些明顯不合理情況，分別驗(yàn)證解的可行性，得到最優(yōu)算法。關(guān)鍵詞：蠻力法；枚舉法；百雞百錢；HundredchickensmoneyAbstract:Thispaperreportshundredchickensmoney,usuallyusingabruteforcemethodstrategy,useenumerationmethodtotheperformance,meettheconditionslistedproblemsolution,excludesomeobviousunreasonablesituation,respectively,toverifythefeasibilityofthesolution,optimalalgorithm.Keywords:thebruteforcemethod;enumeration;hundredchickensmoney;1引言在求解一個(gè)較小規(guī)模的問(wèn)題時(shí)，可以根據(jù)問(wèn)題中的約束條件把可能的情況一一列舉出來(lái)，然后注意嘗試從中找到滿足約束條件的解，若該問(wèn)題規(guī)模較大，符合條件的情況很多，則需要進(jìn)一步考慮，排除一些明顯不合理的情況，盡可能減少問(wèn)題可能解的列舉數(shù)目。2問(wèn)題概述中國(guó)古代數(shù)學(xué)家張丘建在他的《算經(jīng)》中提出了著名的“百錢百雞問(wèn)題”：雞翁一，值錢五；雞母一，值錢三；雞雛三，值錢一；百錢買百雞，翁，母，雛各幾何？譯為;現(xiàn)一只公雞5元錢，一只母雞3元錢，三只小雞1元錢；給你一百元錢去買公雞、母雞、小雞共一百只，問(wèn)你應(yīng)當(dāng)買多少只公雞？多少只母雞？多少只小雞？通過(guò)對(duì)問(wèn)題的理解，可列出兩個(gè)三元一次方程，去解這個(gè)不定解方程，找出存在的解。我們要用到“懶惰”的蠻力法其實(shí)就和這類似，不同的是我們只需要加以條件，讓電腦幫助我們計(jì)算，解出結(jié)果。算法設(shè)計(jì)在公雞（x），母雞（y）數(shù)量確定后，根據(jù)總數(shù)100只，小雞的數(shù)量z也就確定為：z=100-x-y，無(wú)需再對(duì)小雞的數(shù)量進(jìn)行枚舉，此時(shí)的約束條件：5x+3y+z/3=100且小雞的數(shù)量是3的倍數(shù)，這樣只需枚舉20*34=660次。 intmain(){intx,y,z;for(x=0;x<20;x++) for(y=0;y<33;y++) { z=100-x-y; if(z%3==0&&5*x+3*y+z/3==100){printf("公雞=%d母雞=%d小雞=%d\n",x,y,z);}}return0;});流程圖如下所示：圖1——蠻力算法流程圖圖2——蠻力算法程序運(yùn)行截圖4算法分析首先設(shè)x,y,z分別為公雞，母雞，小雞的數(shù)量。由于題中條件的限制，我們可以估算出公雞，母雞，小雞的數(shù)量范圍。即： 若全買公雞，最多買100/5=20只，顯然：0<x<20;同理：0<y<330<z<100;約束條件：x+y+z=100且5x+3y+z/3=100且小雞數(shù)量是3的倍數(shù)；算法如下： intmain(){intx,y,z;for(x=0;x<20;x++)for(y=0;y<33;y++) for(z=0;z<100;z++) { if(x+y+z==100&&z%3==0&&5*x+3*y+z/3==100) { printf("公雞=%d母雞=%d小雞=%d\n",x,y,z); } }return0;}若用上面算法，需要枚舉嘗試20*33*100=66000次，算法的效率太低。因此我們將算法加以改進(jìn)：即：在公雞（x），母雞（y）數(shù)量確定后，根據(jù)總數(shù)100只，小雞的數(shù)量z也就確定為：z=100-x-y，無(wú)需再對(duì)小雞的數(shù)量進(jìn)行枚舉，此時(shí)的約束條件：5x+3y+z/3=100且小雞的數(shù)量是3的倍數(shù)，這樣只需枚舉20*34=660次。修改后的算法為： intmain(){intx,y,z;for(x=0;x<20;x++) for(y=0;y<33;y++) { z=100-x-y; if(z%3==0&&5*x+3*y+z/3==100){printf("公雞=%d母雞=%d小雞=%d\n",x,y,z);}}return0;});5結(jié)束語(yǔ)由上述實(shí)例可以看出，枚舉法是蠻力策略的一種變現(xiàn)形式，也是一種使用非常普遍的思維方法。然而對(duì)于同一個(gè)問(wèn)題，可以選擇不同的枚舉范圍，不同的枚舉對(duì)象，這樣解決問(wèn)題的效率差別可能會(huì)很大。所以選擇合適的方法會(huì)讓解決問(wèn)題的效率大大提高。經(jīng)過(guò)這次的實(shí)驗(yàn)，我們充分的認(rèn)識(shí)到團(tuán)隊(duì)合作的重要性，通過(guò)這次練習(xí)，讓我們小組更加深刻的認(rèn)識(shí)到蠻力法的優(yōu)越性以及優(yōu)