百雞問題佛山市高明區第一中學授課人：何桂紅百雞問題佛山市高明區第一中學授課人：何桂紅

在求解一個較小規模的問題時，可以根據問題中的約束條件把可能的情況一一列舉出來，然后注意嘗試從中找到滿足約束條件的解，若該問題規模較大，符合條件的情況很多，則需要進一步考慮，排除一些明顯不合理的情況，盡可能減少問題可能解的列舉數目。在求解一個較小規模的問題時，可以根據問題中的約束條件把百雞問題的故事:

中國古代數學名著《張邱建算經》中曾記載一道聞名世界的百雞問題，題曰：“公雞一只值錢5，母雞一只值錢3，小雞三只值錢1，今有錢一百，買雞一百只，問公雞、母雞、小雞各幾何？”

這是一道不定方程的問題，它可以在許多不定方程的書中找到，百雞問題既很實際又很有趣，在其流傳的一千多年中，人們為它的來源編織了很多美妙的傳說，下面的故事就是其中的一例：公元前五世紀，有位姓張的貧苦人家的少年，他們全家只靠少年的父親張老頭賣雞來維持生活。這位少年聰明好學，又特別喜愛數學，他在十二三歲時，就已攻讀了《九章算術》等數學名著，當地人稱他為“張神童”，“張神童”的名字傳開后，引起了一些人的興趣。一天，一位官員拿來一百文錢，要求按當時的雞價：公雞每只五文，母雞每只三文，小雞每三只一文，購買恰好一百只雞。“張神童”為一愁莫展的父親解決了難題，他給來人送上4只公雞，18只母雞和78只小雞，共百雞，值錢百文。第二天此人又帶來一百文錢，還要買一百只雞，但不能與上次重復。這次“張神童”讓父親拿出18只公雞，11只母雞和81只小雞，顯而易見雞值百錢，滿足了來人的要求。第三天，這個人帶著一百文錢再次來到張家，還要求百錢買百雞，且不能與上兩次重復，“張神童”又一次為父親解了圍，他讓父親給來人12只公雞，4只母雞和84只小雞，又湊成了百雞值百錢，三次的考驗使這位官員對“張神童”的神機妙算贊嘆不已，從此“張神童”的名氣更大了，這位“張神童”據說就是我國著名的數學家張邱建。百雞問題的故事:具體問題（百雞問題）：

公雞一只值錢5，母雞一只值錢3，小雞三只值錢1，今有錢一百，買雞一百只，問公雞、母雞、小雞各幾何？分析問題：

百雞問題實際上是不定方程問題，用現在的解法比較容易。我們不妨設公雞、母雞、小雞各為x、y、z，則根據題意得：求此方程的正整數解。

將（2）×3代入（1）得7x+4y=100……（3）由此得出x是4的倍數，且x＜14，于是x只能是4，8，12代入（3）可得y的三個對應解是8，11，4，所以此問題有三組正整數解：具體問題（百雞問題）：

公雞一只值錢5，母具體問題（百雞問題）：

公雞一只值錢5，母雞一只值錢3，小雞三只值錢1，今有錢一百，買雞一百只，問公雞、母雞、小雞各幾何？分析問題：

百雞問題實際上是不定方程問題，用現在的解法比較容易。我們不妨設公雞、母雞、小雞各為x、y、z，則根據題意得：求此方程的正整數解。

將（2）×3代入（1）得7x+4y=100……（3）由此得出x是4的倍數，且x＜14，于是x只能是4，8，12代入（3）可得y的三個對應解是8，11，4，所以此問題有三組正整數解：所以y=(100-7x)/4=25-2x+x/4，令x/4=t,（t為整數）所以x=4t，把x=4t代入7x+4y=100得到：y=25-7t，易得z=75+3t，所以：x=4t，y=25-7t，z=75+3t。因為x,y,z大于等于0所以4t大于等于0，25-7t大于等于0，75+3t大于等于0。解得t大于等于0小于等于25/7又因為t為整數，所以t=0,1,2,3（這里不要忘記t有等于0得可能）。當t=0時：x=0,y=25,z=75；當t=1時

x=4；y=18；z=78當t=2時

x=8；y=11；z=81當t=3時

x=12；y=4；z=84

具體問題（百雞問題）：

公雞一只值錢5，母百雞問題:

公雞一只值錢5，母雞一只值錢3，小雞三只值錢1，今有錢一百，買雞一百只，問公雞、母雞、小雞各幾何？算法設計：根據問題中的約束條件將可能的情況一一列舉出來，但如果情況很多，排除一些明顯的不需要理會的情況，盡可能減少問題可能解的列舉數目，然后找出滿足問題條件的解。完成百雞百錢問題的常規算法（懶惰枚舉）的實現和改進算法（非懶惰枚舉）的實現，以證明對于同一問題可以有不同的枚舉范圍，不同的枚舉對象，解決問題的效益差別會很大。百雞問題:

公雞一只值錢5，母雞一只值錢3百雞問題:

公雞一只值錢5，母雞一只值錢3，小雞三只值錢1，今有錢一百，買雞一百只，問公雞、母雞、小雞各幾何？算法設計：此算法的流程圖算法思想一

懶惰枚舉法：首先問題有三種不同的雞，我們可以設公雞為x只，母雞為y只，小雞為z只。由題意給出一共要用100錢買一百只雞，如果我們全部買公雞最多可以買100/5=20只，顯然x的取值范圍是1~20之間；如果全部買母雞最多可以買100/3=33只，顯然y的取值范圍在1~33之間；如果全部買小雞最多可以買100*3=300只，可是題目規定是買100只，所以z的取值范圍是1~100.那么約束條件為：x+y+z=100且5*x+3*y+z/3=100。則x,y,z當前的值就是答案。百雞問題:

公雞一只值錢5，母雞一只值錢3算法思想一的流程圖：開始定義x,y,z,cont變量X<=20y<=33z<=33百雞和百錢？輸出百雞以及統計時間的結果YYYY結束NNNN請同學們根據流程圖，設計程序。算法思想一的流程圖：開始定義x,y,z,cont變量X<=2算法一參考程序代碼：PrivateSubCommand1_Click()Dimx,y,z,contAsLongcont=0Print"公雞母雞小雞"Forx=1To20Fory=1To33Forz=1To100Ifx+y+z=100And5*x+3*y+1/3*z=100ThenPrintx,y,zcont=cont+1NextzNextyNextxPrint"共計算";cont;"次。"EndSub百雞問題:

公雞一只值錢5，母雞一只值錢3，小雞三只值錢1，今有錢一百，買雞一百只，問公雞、母雞、小雞各幾何？算法一參考程序代碼：PrivateSubCommand1百雞問題:

公雞一只值錢5，母雞一只值錢3，小雞三只值錢1，今有錢一百，買雞一百只，問公雞、母雞、小雞各幾何？算法設計：此算法的流程圖算法思想二

非懶惰枚舉法：假如我設了公雞和母雞的個數為x和y了，那么小雞和母雞的數量就是確定的，那么小雞的數量就是固定的為100-x-y,此時就不再需要進行枚舉了，約束條件就只有一個了：5*x+3*y+z/3=100.百雞問題:

公雞一只值錢5，母雞一只值錢3算法思想二的流程圖：開始定義x,y,z,cont變量X<=20y<=33如果zmod3=0and5*x+3*y+z/3=100輸出百雞以及統計時間的結果YYY結束NNNZ=100-x-y請同學們根據流程圖，設計程序。算法思想二的流程圖：開始定義x,y,z,cont變量X<=2算法二參考程序代碼：PrivateSubCommand2_Click()Dimx,y,contAsLongcont=0Print"公雞母雞小雞"Forx=1To20Fory=1To33z=100-x-yIfzMod3=0And5*x+3*y+z/3=100ThenPrintx,y,zcont=cont+1NextyNextxPrint"共計算";cont;"次。"EndSub百雞問題:

公雞一只值錢5，母雞一只值錢3，小雞三只值錢1，今有錢一百，買雞一百只，問公雞、母雞、小雞各幾何？算法二參考程序代碼：PrivateSubCommand2算法分析：百雞問題:

公雞一只值錢5，母雞一只值錢3，小雞三只值錢1，今有錢一百，買雞一百只，問公雞、母雞、小雞各幾何？懶惰枚舉法需要嘗試20*34*100=66000次，算法的效率顯然很低。非懶惰枚舉法只須嘗試20*33=660次。實現時約束條件又限定z能被3整除時，才會判斷“5*x+3*y+z/3=100”。這樣省去了不整除3時的算術計算和條件判斷，進一步提高了算法的效率。算法分析：百雞問題:

公雞一只值錢5，母雞結束語：百雞問題:

公雞一只值錢5，母雞一只值錢3，小雞三只值錢1，今有錢一百，買雞一百只，問公雞、母雞、小雞各幾何？通過以上兩種算法可以看出，枚舉法是蠻力策略的一種表現形式，也是一種使用非常普遍的思維方法。然而對于同一個問題，可以選擇不同的枚舉范圍、不同的枚舉對象，這樣解決問題的效率差別可能會很大。所以選擇合適的方法會讓解決問題的效率大大提高。希望同學們通過這節課，能感受到算法與程序設計的魅力，我們要繼續加油，在算法的道路中，走的更遠。結束語：百雞問題:

公雞一只值錢5，母雞一百雞問題佛山市高明區第一中學授課人：何桂紅百雞問題佛山市高明區第一中學授課人：何桂紅

在求解一個較小規模的問題時，可以根據問題中的約束條件把可能的情況一一列舉出來，然后注意嘗試從中找到滿足約束條件的解，若該問題規模較大，符合條件的情況很多，則需要進一步考慮，排除一些明顯不合理的情況，盡可能減少問題可能解的列舉數目。在求解一個較小規模的問題時，可以根據問題中的約束條件把百雞問題的故事:

中國古代數學名著《張邱建算經》中曾記載一道聞名世界的百雞問題，題曰：“公雞一只值錢5，母雞一只值錢3，小雞三只值錢1，今有錢一百，買雞一百只，問公雞、母雞、小雞各幾何？”

這是一道不定方程的問題，它可以在許多不定方程的書中找到，百雞問題既很實際又很有趣，在其流傳的一千多年中，人們為它的來源編織了很多美妙的傳說，下面的故事就是其中的一例：公元前五世紀，有位姓張的貧苦人家的少年，他們全家只靠少年的父親張老頭賣雞來維持生活。這位少年聰明好學，又特別喜愛數學，他在十二三歲時，就已攻讀了《九章算術》等數學名著，當地人稱他為“張神童”，“張神童”的名字傳開后，引起了一些人的興趣。一天，一位官員拿來一百文錢，要求按當時的雞價：公雞每只五文，母雞每只三文，小雞每三只一文，購買恰好一百只雞。“張神童”為一愁莫展的父親解決了難題，他給來人送上4只公雞，18只母雞和78只小雞，共百雞，值錢百文。第二天此人又帶來一百文錢，還要買一百只雞，但不能與上次重復。這次“張神童”讓父親拿出18只公雞，11只母雞和81只小雞，顯而易見雞值百錢，滿足了來人的要求。第三天，這個人帶著一百文錢再次來到張家，還要求百錢買百雞，且不能與上兩次重復，“張神童”又一次為父親解了圍，他讓父親給來人12只公雞，4只母雞和84只小雞，又湊成了百雞值百錢，三次的考驗使這位官員對“張神童”的神機妙算贊嘆不已，從此“張神童”的名氣更大了，這位“張神童”據說就是我國著名的數學家張邱建。百雞問題的故事:具體問題（百雞問題）：

公雞一只值錢5，母雞一只值錢3，小雞三只值錢1，今有錢一百，買雞一百只，問公雞、母雞、小雞各幾何？分析問題：

百雞問題實際上是不定方程問題，用現在的解法比較容易。我們不妨設公雞、母雞、小雞各為x、y、z，則根據題意得：求此方程的正整數解。

將（2）×3代入（1）得7x+4y=100……（3）由此得出x是4的倍數，且x＜14，于是x只能是4，8，12代入（3）可得y的三個對應解是8，11，4，所以此問題有三組正整數解：具體問題（百雞問題）：

公雞一只值錢5，母具體問題（百雞問題）：

公雞一只值錢5，母雞一只值錢3，小雞三只值錢1，今有錢一百，買雞一百只，問公雞、母雞、小雞各幾何？分析問題：

百雞問題實際上是不定方程問題，用現在的解法比較容易。我們不妨設公雞、母雞、小雞各為x、y、z，則根據題意得：求此方程的正整數解。

將（2）×3代入（1）得7x+4y=100……（3）由此得出x是4的倍數，且x＜14，于是x只能是4，8，12代入（3）可得y的三個對應解是8，11，4，所以此問題有三組正整數解：所以y=(100-7x)/4=25-2x+x/4，令x/4=t,（t為整數）所以x=4t，把x=4t代入7x+4y=100得到：y=25-7t，易得z=75+3t，所以：x=4t，y=25-7t，z=75+3t。因為x,y,z大于等于0所以4t大于等于0，25-7t大于等于0，75+3t大于等于0。解得t大于等于0小于等于25/7又因為t為整數，所以t=0,1,2,3（這里不要忘記t有等于0得可能）。當t=0時：x=0,y=25,z=75；當t=1時

x=4；y=18；z=78當t=2時

x=8；y=11；z=81當t=3時

x=12；y=4；z=84

具體問題（百雞問題）：

公雞一只值錢5，母百雞問題:

公雞一只值錢5，母雞一只值錢3，小雞三只值錢1，今有錢一百，買雞一百只，問公雞、母雞、小雞各幾何？算法設計：根據問題中的約束條件將可能的情況一一列舉出來，但如果情況很多，排除一些明顯的不需要理會的情況，盡可能減少問題可能解的列舉數目，然后找出滿足問題條件的解。完成百雞百錢問題的常規算法（懶惰枚舉）的實現和改進算法（非懶惰枚舉）的實現，以證明對于同一問題可以有不同的枚舉范圍，不同的枚舉對象，解決問題的效益差別會很大。百雞問題:

公雞一只值錢5，母雞一只值錢3百雞問題:

公雞一只值錢5，母雞一只值錢3，小雞三只值錢1，今有錢一百，買雞一百只，問公雞、母雞、小雞各幾何？算法設計：此算法的流程圖算法思想一

懶惰枚舉法：首先問題有三種不同的雞，我們可以設公雞為x只，母雞為y只，小雞為z只。由題意給出一共要用100錢買一百只雞，如果我們全部買公雞最多可以買100/5=20只，顯然x的取值范圍是1~20之間；如果全部買母雞最多可以買100/3=33只，顯然y的取值范圍在1~33之間；如果全部買小雞最多可以買100*3=300只，可是題目規定是買100只，所以z的取值范圍是1~100.那么約束條件為：x+y+z=100且5*x+3*y+z/3=100。則x,y,z當前的值就是答案。百雞問題:

公雞一只值錢5，母雞一只值錢3算法思想一的流程圖：開始定義x,y,z,cont變量X<=20y<=33z<=33百雞和百錢？輸出百雞以及統計時間的結果YYYY結束NNNN請同學們根據流程圖，設計程序。算法思想一的流程圖：開始定義x,y,z,cont變量X<=2算法一參考程序代碼：PrivateSubCommand1_Click()Dimx,y,z,contAsLongcont=0Print"公雞母雞小雞"Forx=1To20Fory=1To33Forz=1To100Ifx+y+z=100And5*x+3*y+1/3*z=100ThenPrintx,y,zcont=cont+1NextzNextyNextxPrint"共計算";cont;"次。"EndSub百雞問題:

公雞一只值錢5，母雞一只值錢3，小雞三只值錢1，今有錢一百，買雞一百只，問公雞、母雞、小雞各幾何？算法一參考程序代碼：PrivateSubCommand1百雞問題:

公雞一只值錢5，母雞一只值錢3，小雞三只值錢1，今有錢一百，買雞一百只，問公雞、母雞、小雞各幾何？算法設計：此算法的流程圖算法思想二

非懶惰枚舉法：假如我設了公雞和母雞的個數為x和y了，那么小雞和母雞的數量就是確定的，那么小雞的數量就是固定的為100-x-y,此時就不再需要進行枚舉了，約束條件就只有一個了：5*x+3*y+z/3=100.百雞問題:

公雞一只值錢5，母雞一只值錢3算法思想二的流程圖：開始定義x,y,z,cont變量X<=20y<=33如果zmod3=0and5*x+3*y+z/3=100輸出百雞以及統計時間的結果YYY結束NNNZ=100-x-y請同學們根據流程圖，設計程序。算法思想二的流程圖：開始定義x,y,z,cont變量X<=2算法二參考程序代碼：PrivateSubCommand2_Click()Dimx,y,contAsL