首页 > 代码库 > 鸡兔同笼问题、百鸡问题、辗转相除法求最大公约数
鸡兔同笼问题、百鸡问题、辗转相除法求最大公约数
一、鸡兔同笼
鸡和兔子35只，腿一共有94条，求出鸡和兔子的数量各是多少？（鸡的数目是23，兔子的数目是12）
$n = 0;
for($ i=1;$i<35;$i++){
$n ++; //n=34;
$ j=35-i;
if(i*2+j*4==94){
printf("鸡的数目是%d只, 兔子的数目是%d只",$i,$j);
}
}
此时，循环进行了34次。但是，有些循环是无意义的，因为得到了结果，循环还在继续往下执行。我们知道：两个未知数，两个方程，其方程组的解唯一！那么我们可以让流程控制的if语句在得到结果以后，终止循环！
改进如下:
$n = 0;
for($ i=1;$i<35;$i++){
$n ++; //n=22;
$ j=35-i;
if(i*2+j*4==94){
printf("鸡的数目是%d只, 兔子的数目是%d只",$i,$j);
break;
}
}
此时，循环只需要进行22次即可。再有，在确定循环变量的时候，分析：兔有四条腿，而鸡只有两只脚，兔子数明显比鸡的个数所得到的腿数更有效！（有点绕，大家不理解的看下面代码~）
终极版改进如下：
$n = 0;
for($ i=1;$i<35;$i++){
$n ++; //n=11;
$ j=35-i;
if(i*4+j*2==94){
printf("鸡的数目是%d只, 兔子的数目是%d只",$j,$i);
break;
}
}
最后，我们获得结果只需要循环11次！比起最开始的34次，节省了23次不必要的循环！可能大家觉得没什么，如果是循环一万次一百万次呢，不必要的循环多了，消耗的资源也就多了，获得最终结果的速度也慢了。
二、百鸡问题
张丘建在《算经》中提出了“百鸡问题”：鸡公一值钱五，鸡母一值钱三，鸡雏三值钱一，百钱买百鸡，问鸡公、母、雏各几何？
先给大家罗列出结果：
公鸡有0只,母鸡有25只,小鸡有75只
公鸡有4只,母鸡有18只,小鸡有78只
公鸡有8只,母鸡有11只,小鸡有81只
公鸡有12只,母鸡有4只,小鸡有84只
同样的，我们让计算机帮我们计算，代码如下：
$n = 0;
for($cocks = 0;$cocks <= 20;$cocks ++){
for($hens = 0;$hens <= 33;$hens ++){
$n++; //n = 714;
$chicks = 100 - $cocks - $hens;
if(5*$cocks + 3*$hens + $chicks/3 == 100) {
printf("公鸡有%d只,母鸡有%d只,小鸡有%d只<br />",$cocks,$hens,$chicks);
}
}
}
要想得到结果，计算机需要循环21*34=714次。接下来怎么优化呢？假设公鸡数为x，母鸡数为y，小鸡数为z。我们先把z消去，得7x+4y = 100，x = （100-4y）/7，那么x最大只能得到14，节省了（20-14）*34=204次循环！另外，我们可以发现，如果少买7只母鸡，就可多买4只公鸡和3只小鸡！我们是不是可以再得到最大的母鸡数，然后递减7，以及公鸡数+4、小鸡数+3来获取最终结果呢？
代码如下：
$n = 0;
for($cocks = 0;$cocks <= 14;$cocks ++){
for($hens = 33;$hens >=0;$hens --){
$n++;
$chicks = 100 - $cocks - $hens;
if(5*$cocks + 3*$hens + $chicks/3 == 100) {
printf("公鸡有%d只,母鸡有%d只,小鸡有%d只<br />",$cocks,$hens,$chicks);
break; //得到最大的母鸡数;
}
}
if(printf()){
break; //如果printf（）有返回值，即内层循环得出了结果，那么就终止！;
}
}
不知道为什么浏览器报错了。。。程序出现问题，待改进。
三、辗转相除法求最大公约数
$num1 = $_GET[‘n1‘];
$num2 = $_GET[‘n2‘];
$num = $num1;
$div = $num2;
// 3, 求余数,开始循环体
do {
$mod = $num % $div;
// 刚才的除数就变成了被除数
$num = $div;
// 刚才的余数就变成了除数
$div = $mod;
}while($mod != 0);
echo "最大公约数为：",$num;
鸡兔同笼问题、百鸡问题、辗转相除法求最大公约数