Scratch趣味數學之百元買百雞

陳新龍

我正在研究一道數學題，古代數學家張丘建在《算經》中的百元買百雞問題：雞翁一值錢五，雞母一值錢三，雞雛三值錢一，一百錢買百雞，問雞翁、雞母、雞雛各幾何？公雞五元一只，母雞三元一只，小雞一元三只，現(xiàn)有一百元要買一百只雞可以有幾種買法？

“百雞問題”在世界上首次提出三元一次不定方程及解法，也是經典的奧數題目。如果手工計算的話就算知道解法也不容易，但用Scratch編程用窮舉法來解這道題目的話，就顯得簡單直接了。

編程之前我們先在草稿紙上根據題目寫出不定方程。

設X：公雞Y：母雞Z：小雞

則X+Y+Z=100（只）

5X+3Y+Z/3=100（元）

為了編程時控制總運算量，先根據總價100元估算公雞、母雞、小雞的數量范圍，公雞的數量不能超過20只，母雞的數量不超過33只，小雞的數量不超過100只，在做題之前我們先把這些關系整理清楚，就方便多了。

算法代碼核心部分如圖1。

設定四個變量，其中三個變量分別對應公雞、母雞、小雞，還有一個變量對應列表值（目的是為了進行列表輸出）。因為方程的解不唯一，還要設定三個列表存儲方程的解。定義公雞、母雞、小雞的初始值要分別在各自循環(huán)前定義，并且不要忘記在每次循環(huán)結束前對公雞、母雞、小雞的數目增加1，利用三重循環(huán)嵌套進行窮舉計算，最終獲得結果。

之前我們已經分析了公雞、母雞、小雞的取值范圍，相當于確定了程序循環(huán)范圍，也就是公雞循環(huán)20次，母雞循環(huán)33次，小雞循環(huán)100次，3層循環(huán)嵌套，在最里層判斷如果X+Y+Z=100與5X+3Y+Z/3=100成立，即獲得一組解，每獲得一組解將“雞的列表值”加1，將X、Y、Z數字存入列表相應位置，當循環(huán)完成后就可以獲得全部解了（如圖2）。

外觀方面可以像我一樣增加一些對話環(huán)節(jié)，大家可以在網盤下載源代碼參考。

百錢買百雞我們用到了窮舉法（枚舉法），所謂窮舉法，顧名思義就是窮盡每一種可能性，通常在找不到解決問題的規(guī)律時對可能是解的眾多候選解按照某一順序進行逐一枚舉和檢驗，并從中找出那些符合要求的候選解作為問題的解?？紤]到算法的時間復雜度與空間復雜度還可以不斷優(yōu)化，方法并不唯一。