プログラマ脳を鍛える数学パズル シンプルで高速なコードが書けるようになる70問をやる。今回は、Q04:棒の切り分け。

Q: 長さn[cm]の1本の棒を1[cm]単位に切り分ける。ただし、1本の棒を一度に切ることが出来るのは1人だけ(ex. 棒が3本あれば同時に3人で切ることができる)。最大m人いるとき、最短何回で切り分けられるか。

20cmを3人の場合と、100cmを5人の場合と、それぞれ求めろ。

def divide(m:Int, n:Int, num:Int = 1, acc:Int = 0):Int = {
  if(num >= n) acc
  else if(num < m) divide(m, n, num*2, acc + 1)
  else divide(m, n, num + m, acc + 1)
}
divide(3, 20)
divide(5, 100)