百元买百鸡算法

㈠ 百钱百鸡(穷举算法)

设公鸡、母鸡、小鸡分别为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
对于这个问题实际上可以不用三重循环，而是用二重循环，因为公鸡和母鸡数确定后，小鸡数就定了，即 。请同学们自己分析二重循环和三重循环的运行次数，做为练习自己调试这一方法。参考资料：东北大学计算中心 --网络文库