百元買百雞演算法

㈠ 百錢百雞(窮舉演算法)

設公雞、母雞、小雞分別為x、y、z 只，由題意得：

x＋y＋z ＝100……①
5x＋3y＋(1/3)z ＝100……②
有兩個方程，三個未知量，稱為不定方程組，有多種解。

令②×3－①得：7x＋4y＝100；

即：y ＝(100－7x)/4＝25－(7/4)x

由於y 表示母雞的只數，它一定是自然數，而4 與7 互質，因此x 必須是4 的倍數。我們把它寫成：x=4k（k 是自然數），於是y=25-7k，代入原方程組，可得：z=75+3k。把它們寫在一起有：
x ＝4k
y ＝25 - 7k
z ＝75+ 3k

一般情況下，當k 取不同數值時，可得到x、y、z 的許多組值。但針對本題的具體問題，由於x、y、z 都是100 以內的自然數，故k 只能取1、2、3 三個值，這樣方程組只有以下三組解：

一、 x ＝4；y ＝18；z ＝78

二、 x ＝8；y ＝11；z ＝81

三、 x ＝12；y ＝4；z ＝84

㈡ 百雞百錢問題（帶解答過程，最好是算數方法）

設買公雞x只，買母雞y只，買小雞z只，那麼根據已知條件列方程，有：

x+y+z=100…………（1）

5x+3y+z/3=100……（2）

（2）×3-（1），得

14x+8y=200

也就是7x+4y=100……（3）

在（3）式中4y和100都是4的倍數：

7x=100-4y=4(25-y)

因此7x也是4的倍數，7和4是互質的，也就是說x必須是4的倍數。

設x=4t

代入（3），得 y=25-7t

再將 x=4t 與 y=25-7t 代入（1），有：

z=75+3t

取t=1 t=2 t=3 就有

x=4 y=18 z=78

或 x=8 y=11 z=81

或 x=12 y=4 z=84

因為x、y、z都必須小於100且都是正整數，所以只有以上三組解符合題意。

解方程依據

1、移項變號：把方程中的某些項帶著前面的符號從方程的一邊移到另一邊，並且加變減，減變加，乘變除以，除以變乘；

2、等式的基本性質：

（1）等式兩邊同時加(或減)同一個數或同一個代數式，所得的結果仍是等式。用字母表示為：若a=b，c為一個數或一個代數式。

（2）等式的兩邊同時乘或除以同一個不為0的數，所得的結果仍是等式。用字母表示為：若a=b，c為一個數或一個代數式（不為0）。

㈢ 典型問題：百錢買百雞的演算法

百錢買百雞問題——一百個銅錢買了一百隻雞，其中公雞一隻5錢、母雞一隻3錢，小雞一錢3隻，問一百隻雞中公雞、母雞、小雞各多少）。
這是一個古典數學問題，設一百隻雞中公雞、母雞、小雞分別為x，y，z，問題化為三元一次方程組：

這里x,y,z為正整數，且z是3的倍數；由於雞和錢的總數都是100，可以確定x,y,z的取值范圍：
1) x的取值范圍為1～20
2) y的取值范圍為1～33
3) z的取值范圍為3～99，步長為3
對於這個問題我們可以用窮舉的方法，遍歷x,y,z的所有可能組合，最後得到問題的解。
數據要求
問題中的常量：
無
問題的輸入：
無
問題的輸出：
int x，y，z /*公雞、母雞、小雞的只數*/
初始演算法
1．初始化為1；
2．計算x循環，找到公雞的只數；
3．計算y循環，找到母雞的只數；
4．計算z循環，找到小雞的只數；
5．結束，程序輸出結果後退出。
演算法細化
演算法的步驟1實際上是分散在程序之中的，由於用的是for循環，很方便的初始條件放到了表達式之中了。
步驟2和3是按照步長1去尋找公雞和母雞的個數。
步驟4的細化
4．1 z＝1
4．2 是否滿足百錢，百雞
4．2．1 滿足，輸出最終百錢買到的百雞的結果
4．2．2 不滿足，不做處理
4．3 變數增加，這里注意步長為3
流程圖

圖5-8 程序執行流程圖
程序代碼如下
#include "stdio.h"
main()
{
int x,y,z;
for(x=1;x<=20;x++)
for(y=1;y<=33;y++)
for(z=3;z<=99;z+=3)
{
if((5*x+3*y+z/3==100)&&(x+y+z==100))/*是否滿足百錢和百雞的條件*/ printf("cock=%d,hen=%d,chicken=%d\n",x,y,z);
}
}
分析
程序運行結果如下：
cock=4,hen=8,chicken=78
cock=8,hen=11,chicken=81
cock=12,hen=4,chicken=84
對於這個問題實際上可以不用三重循環，而是用二重循環，因為公雞和母雞數確定後，小雞數就定了，即 。請同學們自己分析二重循環和三重循環的運行次數，做為練習自己調試這一方法。參考資料：東北大學計算中心 --網路文庫