现在的位置: 主页 > 企业简介 > 文章列表

PHP经典题:百钱百鸡问题(穷举算法)

作者:福建省医学会血液病学分会 来源:www.fjhematology.org 发布时间:2017-09-08 19:15:14
 

PHP经典题:百钱百鸡问题(穷举算法)

已知:公鸡5元一只,母鸡3元一只,小鸡一元3只

现用100元钱买了100只鸡,问:公鸡母鸡小鸡各几只?

--请考虑尽可能高效的方法

思路:

如果有0只公鸡,0只母鸡,1只小鸡,数量是100吗?价钱是100吗? 否

如果有0只公鸡,0只母鸡,2只小鸡,数量是100吗?价钱是100吗? 否

如果有0只公鸡,0只母鸡,3只小鸡,数量是100吗?价钱是100吗? 否

......

如果有0只公鸡,0只母鸡,100只小鸡,数量是100吗?价钱是100吗? 否

如果有0只公鸡,1只母鸡,1只小鸡,数量是100吗?价钱是100吗? 否

如果有0只公鸡,1只母鸡,2只小鸡,数量是100吗?价钱是100吗? 否

......

如果有0只公鸡,1只母鸡,100只小鸡,数量是100吗?价钱是100吗? 否

如果有0只公鸡,2只母鸡,1只小鸡,数量是100吗?价钱是100吗? 否

......

如果有100只公鸡,100只母鸡,0只小鸡,数量是100吗?价钱是100吗? 否

如果有100只公鸡,100只母鸡,1只小鸡,数量是100吗?价钱是100吗?否

如果有100只公鸡,100只母鸡,2只小鸡,数量是100吗?价钱是100吗?否

......

这就叫做:穷举思想 (就是将所以可能的情况挨个去测试)

PHP代码:

echo "<p>原始思路:</p>";

$count = 0;

for($gongji = 0; $gongji <= 100; ++$gongji) {

for($muji = 0; $muji <= 100; ++$muji) {

for($xiaoji = 0; $xiaoji <= 100; ++$xiaoji) {

if($gongji*5 + $muji*3 + $xiaoji/3 == 100 && $gongji + $muji + $xiaoji == 100) {

echo "<br />公鸡有 $gongji 只;母鸡有 $muji 只;小鸡有 $xiaoji 只;";

}

$count++;//计算次数

}

}

}

echo "<br />次数:$count";

echo '<br />';

echo "<p>代码优化一:</p>";

$count = 0;

for($gongji = 0; $gongji <= 100; ++$gongji) {

for($muji = 0; $muji <= 100; ++$muji) {

$xiaoji = 100 - $gongji - $muji;

if($gongji*5 + $muji*3 + $xiaoji/3 == 100) {

echo "<br />公鸡有 $gongji 只;母鸡有 $muji 只;小鸡有 $xiaoji 只;";

}

$count++;//计算次数

}

}

echo "<br />次数:$count";

echo '<br />';

echo "<p>代码优化二:</p>";

$count = 0;

for($gongji = 0; $gongji <= 100/5; ++$gongji) { //根据总价:则公鸡最多有100/5只

for($muji = 0; $muji <= 100/3; ++$muji) { //根据总价:则母鸡最多有100/3只

$xiaoji = 100 - $gongji - $muji;

if($gongji*5 + $muji*3 + $xiaoji/3 == 100) {

echo "<br />公鸡有 $gongji 只;母鸡有 $muji 只;小鸡有 $xiaoji 只;";

}

$count++;//计算次数

}

}

echo "<br />次数:$count";

echo '<br />';

echo "<p>代码优化三:</p>";

$count = 0;

for($gongji = 0; $gongji <= 100/5; ++$gongji) { //根据总价:则公鸡最多有100/5只

for($muji = 0; $muji <= (100-$gongji*5)/3; ++$muji) { //根据总价与公鸡所花的钱:则母鸡最多有(100-$gongji*5)/3只

$xiaoji = 100 - $gongji - $muji;

if($gongji*5 + $muji*3 + $xiaoji/3 == 100) {

echo "<br />公鸡有 $gongji 只;母鸡有 $muji 只;小鸡有 $xiaoji 只;";

}

$count++;//计算次数

}

}

echo "<br />次数:$count";

echo '<br />';

echo "<p>代码优化四:</p>";

$count = 0;

for($gongji = 0; $gongji <= 100/5; ++$gongji) { //根据总价:则公鸡最多有100/5只

for($muji = 0; $muji <= (100-$gongji*5)/3; ++$muji) { //根据总价与公鸡所花的钱:则母鸡最多有(100-$gongji*5)/3只

$xiaoji = 100 - $gongji - $muji;

if($xiaoji % 3 != 0) {continue;}//考虑小鸡的价钱,则小鸡的数量只能被3整除才合理

if($gongji*5 + $muji*3 + $xiaoji/3 == 100) {

echo "<br />公鸡有 $gongji 只;母鸡有 $muji 只;小鸡有 $xiaoji 只;";

}

$count++;//计算次数

}

}

echo "<br />次数:$count";

输出的结果及计算次数:

原始思路:

公鸡有 0 只;母鸡有 25 只;小鸡有 75 只;

公鸡有 4 只;母鸡有 18 只;小鸡有 78 只;

公鸡有 8 只;母鸡有 11 只;小鸡有 81 只;

公鸡有 12 只;母鸡有 4 只;小鸡有 84 只;

次数:1030301

代码优化一:

公鸡有 0 只;母鸡有 25 只;小鸡有 75 只;

公鸡有 4 只;母鸡有 18 只;小鸡有 78 只;

公鸡有 8 只;母鸡有 11 只;小鸡有 81 只;

公鸡有 12 只;母鸡有 4 只;小鸡有 84 只;

次数:10201

代码优化二:

公鸡有 0 只;母鸡有 25 只;小鸡有 75 只;

公鸡有 4 只;母鸡有 18 只;小鸡有 78 只;

公鸡有 8 只;母鸡有 11 只;小鸡有 81 只;

公鸡有 12 只;母鸡有 4 只;小鸡有 84 只;

次数:714

代码优化三:

公鸡有 0 只;母鸡有 25 只;小鸡有 75 只;

公鸡有 4 只;母鸡有 18 只;小鸡有 78 只;

公鸡有 8 只;母鸡有 11 只;小鸡有 81 只;

公鸡有 12 只;母鸡有 4 只;小鸡有 84 只;

次数:364

代码优化四:

公鸡有 0 只;母鸡有 25 只;小鸡有 75 只;

公鸡有 4 只;母鸡有 18 只;小鸡有 78 只;

公鸡有 8 只;母鸡有 11 只;小鸡有 81 只;

公鸡有 12 只;母鸡有 4 只;小鸡有 84 只;

企业建站2800元起,携手武汉肥猫科技,做一个有见地的颜值派!更多优惠请戳:鄂州网站建设 http://ezhou.45qun.com

  • 上一篇:SEO心得:伪原创文章偷工减料必将受到百度严惩
  • 下一篇:最后一页
  •