36.百錢百雞問題
中國古代數(shù)學(xué)家張丘建在他的《算經(jīng)》中提出了的“百錢買百雞問題”：雞翁一，值錢五，雞母一，值錢三，雞雛三，值錢一，百錢買百雞，問翁、母、雛各幾何？
*題目分析與算法設(shè)計
設(shè)雞翁、雞母、雞雛的個數(shù)分別為x,y,z，題意給定共100錢要買百雞，若全買公雞最多買20只，顯然x的值在0~20之間；同理，y的取值范圍在0~33之間，可得到下面的不定方程：
5x+3y+z/3=100
x+y+z=100
所以此問題可歸結(jié)為求這個不定方程的整數(shù)解。
由程序設(shè)計實現(xiàn)不定方程的求解與手工計算不同。在分析確定方程中未知數(shù)變化范圍的前提下，可通過對未知數(shù)可變范圍的窮舉，驗證方程在什么情況下成立，從而得到相應(yīng)的解。
*程序說明與注釋
#include
void main()
{
int x,y,z,j=0;
printf("Folleing are possible plans to buy 100 fowls with 100 Yuan.\n");
for(x=0;x<=20;x++) /*外層循環(huán)控制雞翁數(shù)*/
for(y=0;y<=33;y++) /*內(nèi)層循環(huán)控制雞母數(shù)y在0~33變化*/
{
z=100-x-y; /*內(nèi)外層循環(huán)控制下，雞雛數(shù)z的值受x,y的值的制約*/
if(z%3==0&&5*x+3*y+z/3==100)
/*驗證取z值的合理性及得到一組解的合理性*/
printf("%2d:cock=%2d hen=%2d chicken=%2d\n",++j,x,y,z);
}
}
*運行結(jié)果
Follwing are possible plans to buy 100 fowls with 100 Yuan.
1:cock=0 hen=25 chicken=75
2:cock=4 hen=18 chicken=78
3:cock=8 hen=11 chicken=81
4:cock=12 hen=4 chicken=84
*總是的進一步討論
這類求解不定方程總理的實現(xiàn)，各層循環(huán)的控制變量直接與方程未知數(shù)有關(guān)，且采用對未知數(shù)的取值范上窮舉和組合的方法來復(fù)蓋可能得到的全部各組解。能否根據(jù)題意更合理的設(shè)置循環(huán)控制條件來減少這種窮舉和組合的次數(shù)，提高程序的執(zhí)行效率，請讀者考慮。
中國古代數(shù)學(xué)家張丘建在他的《算經(jīng)》中提出了的“百錢買百雞問題”：雞翁一，值錢五，雞母一，值錢三，雞雛三，值錢一，百錢買百雞，問翁、母、雛各幾何？
*題目分析與算法設(shè)計
設(shè)雞翁、雞母、雞雛的個數(shù)分別為x,y,z，題意給定共100錢要買百雞，若全買公雞最多買20只，顯然x的值在0~20之間；同理，y的取值范圍在0~33之間，可得到下面的不定方程：
5x+3y+z/3=100
x+y+z=100
所以此問題可歸結(jié)為求這個不定方程的整數(shù)解。
由程序設(shè)計實現(xiàn)不定方程的求解與手工計算不同。在分析確定方程中未知數(shù)變化范圍的前提下，可通過對未知數(shù)可變范圍的窮舉，驗證方程在什么情況下成立，從而得到相應(yīng)的解。
*程序說明與注釋
#include
void main()
{
int x,y,z,j=0;
printf("Folleing are possible plans to buy 100 fowls with 100 Yuan.\n");
for(x=0;x<=20;x++) /*外層循環(huán)控制雞翁數(shù)*/
for(y=0;y<=33;y++) /*內(nèi)層循環(huán)控制雞母數(shù)y在0~33變化*/
{
z=100-x-y; /*內(nèi)外層循環(huán)控制下，雞雛數(shù)z的值受x,y的值的制約*/
if(z%3==0&&5*x+3*y+z/3==100)
/*驗證取z值的合理性及得到一組解的合理性*/
printf("%2d:cock=%2d hen=%2d chicken=%2d\n",++j,x,y,z);
}
}
*運行結(jié)果
Follwing are possible plans to buy 100 fowls with 100 Yuan.
1:cock=0 hen=25 chicken=75
2:cock=4 hen=18 chicken=78
3:cock=8 hen=11 chicken=81
4:cock=12 hen=4 chicken=84
*總是的進一步討論
這類求解不定方程總理的實現(xiàn)，各層循環(huán)的控制變量直接與方程未知數(shù)有關(guān)，且采用對未知數(shù)的取值范上窮舉和組合的方法來復(fù)蓋可能得到的全部各組解。能否根據(jù)題意更合理的設(shè)置循環(huán)控制條件來減少這種窮舉和組合的次數(shù)，提高程序的執(zhí)行效率，請讀者考慮。