引き続き問題を解いていきます。
問題はプログラマ脳を鍛える数学パズルより。
今回の問題
最近は電車もバスも電子マネーが当たり前。でも、いまだに現金で払う人も多いもの。今回はバスに設置されている両替機を考えます。
この機械では、10円玉、50円玉、100円玉、500円玉の組み合わせに両替することができ、いずれの硬貨も十分な枚数がセットされています（中略）。
両替する際に、使われない硬貨はあっても構いませんが、バスの中でたくさんの小銭が出ると困るため、最大で15枚になるように両替します。例えば、1000円を両替するときに、「10円玉を100枚」という両替はできません。
問題
1000円札を入れたときに出てくる硬貨の組み合わせは何通りあるかを求めてください。なお、硬貨の順番は区別しないものとします。
実装手順
①各硬貨が取りうる枚数をループで網羅する
②硬貨ごとに1回のループが完了するたびに合計額が1000円か否かを判定する
書いたPHPコードと出力結果
q05.php
<?php
$sum = 0;
$count = 0;
// 各硬貨が取りうる枚数をループ文で網羅する
// 500円硬貨は最大2枚
for ($count_500 = 0; $count_500 <= 2; $count_500++) {
// 100円硬貨は最大10枚
for ($count_100 = 0; $count_100 <= 10; $count_100++) {
// 50円硬貨は最大15枚（問題の制約）
for ($count_50 = 0; $count_50 <= 15; $count_50++) {
// 10円硬貨は最大10枚（問題の制約）
for ($count_10 = 0; $count_10 <= 15; $count_10++) {
// 金額を合計する
$sum = 500*$count_500 + 100*$count_100 + 50*$count_50 + 10*$count_10;
// 枚数を合計する
$number = $count_500 + $count_100 + $count_50 + $count_10;
// 枚数が15枚以下、かつ、金額1000円の場合を数え上げる
if ($number <= 15) {
if ($sum === 1000) {
$count = $count + 1;
echo '解答'.$count.'<br/>';
echo '500円玉は'.$count_500.'枚<br/>';
echo '100円玉は'.$count_100.'枚<br/>';
echo '50円玉は'.$count_50.'枚<br/>';
echo '10円玉は'.$count_10.'枚<br/>';
echo '<br/>';
}
}
}
}
}
}
// 結果を出力する
echo $count.'通り';
// 解答
20通り
解答1
500円玉は0枚
100円玉は5枚
50円玉は10枚
10円玉は0枚
解答2
500円玉は0枚
100円玉は6枚
50円玉は8枚
10円玉は0枚
解答3
500円玉は0枚
100円玉は7枚
50円玉は6枚
10円玉は0枚
解答4
500円玉は0枚
100円玉は8枚
50円玉は4枚
10円玉は0枚
解答5
500円玉は0枚
100円玉は9枚
50円玉は1枚
10円玉は5枚
解答6
500円玉は0枚
100円玉は9枚
50円玉は2枚
10円玉は0枚
解答7
500円玉は0枚
100円玉は10枚
50円玉は0枚
10円玉は0枚
解答8
500円玉は1枚
100円玉は0枚
50円玉は9枚
10円玉は5枚
解答9
500円玉は1枚
100円玉は0枚
50円玉は10枚
10円玉は0枚
解答10
500円玉は1枚
100円玉は1枚
50円玉は7枚
10円玉は5枚
解答11
500円玉は1枚
100円玉は1枚
50円玉は8枚
10円玉は0枚
解答12
500円玉は1枚
100円玉は2枚
50円玉は5枚
10円玉は5枚
解答13
500円玉は1枚
100円玉は2枚
50円玉は6枚
10円玉は0枚
解答14
500円玉は1枚
100円玉は3枚
50円玉は3枚
10円玉は5枚
解答15
500円玉は1枚
100円玉は3枚
50円玉は4枚
10円玉は0枚
解答16
500円玉は1枚
100円玉は4枚
50円玉は0枚
10円玉は10枚
解答17
500円玉は1枚
100円玉は4枚
50円玉は1枚
10円玉は5枚
解答18
500円玉は1枚
100円玉は4枚
50円玉は2枚
10円玉は0枚
解答19
500円玉は1枚
100円玉は5枚
50円玉は0枚
10円玉は0枚
解答20
500円玉は2枚
100円玉は0枚
50円玉は0枚
10円玉は0枚
今回の学び
- 解く問題の制約をコードに組み込むと計算量が減りループ処理が早くなる
- 10円玉ではなく500円玉からループ処理を始めたことによって計算量をへらす工夫ができた
- 汎用的に使えるコードになっていないので、再帰処理で書き直したコードを別途あげる