プログラマ脳を鍛える数学パズル Q.4「棒の切り分け」

問題の順番が前後していますが引き続き問題を解いていきます。
問題はプログラマ脳を鍛える数学パズルより。

今回の問題

長さn[cm]の1本の棒を1[cm]単位に切り分けることを考えます。ただし、1本の棒を一度に切ることができるのは1人だけです。切り分けられた棒が3本であれば、同時に3人で切ることができます。
最大m人の人がいるとき、最短何回で切り分けられるかを求めてください。例えば、n=8, m=3のときは（中略）4回で切り分けることができます。
問題1
n=20, m=3のときの回数を求めてください。
問題2
n=100, m=5のときの回数を求めてください。

実装手順

①切り分けられた棒の個数がnを超えない場合のループ文を書く
②切り分けられた棒の個数がnを超えた場合のループ文を書く
③結果を出力する

書いたPHPコードと出力結果

q04.php

<?php
// 問題1
$m = 20;
$n = 3;
// 問題2
$m = 100;
$n = 5;

// 切る回数
$cut = 0;

// 切り分けられた棒の個数がnを超えない場合
for ($count = 1; $count < $n; $count *= 2) {
  $cut += 1;
}

// 切り分けられた棒の個数がnを超えた場合
for ($count; $count <= $m; $count += $n) {
  $cut += 1;
}

// 結果の出力
echo $cut.'回です';

// 問題1
8回です
// 問題2
22回です

今回の学び

• 問題を読んですぐに実装の方法が分からなければ、一度手書きで式や図を書いてみると法則が見つけられることがある。
• 別解で再帰処理を用いていたので、別記事でまとめる。