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 隻;

次數:121

 

發佈留言