Scratch趣味數(shù)學(xué)之百元買百雞

陳新龍

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

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

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

設(shè)X：公雞Y：母雞Z：小雞

則X+Y+Z=100（只）

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

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

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

設(shè)定四個(gè)變量，其中三個(gè)變量分別對(duì)應(yīng)公雞、母雞、小雞，還有一個(gè)變量對(duì)應(yīng)列表值（目的是為了進(jìn)行列表輸出）。因?yàn)榉匠痰慕獠晃ㄒ?，還要設(shè)定三個(gè)列表存儲(chǔ)方程的解。定義公雞、母雞、小雞的初始值要分別在各自循環(huán)前定義，并且不要忘記在每次循環(huán)結(jié)束前對(duì)公雞、母雞、小雞的數(shù)目增加1，利用三重循環(huán)嵌套進(jìn)行窮舉計(jì)算，最終獲得結(jié)果。

之前我們已經(jīng)分析了公雞、母雞、小雞的取值范圍，相當(dāng)于確定了程序循環(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數(shù)字存入列表相應(yīng)位置，當(dāng)循環(huán)完成后就可以獲得全部解了（如圖2）。

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

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