Scratch趣味數學之百元買百雞

陳新龍

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

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

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

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

則X+Y+Z=100（只）

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

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

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

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

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

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

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