1本の棒を1cmごとに切り分ける(Ruby) #Ruby

１本の棒があり、それを複数人で半分に切っていって、最終的に1cmのかけらの集合体にします。
ただし、１本の棒を同時に切ることが出来るのは１人だけです。（切り分けられた棒が2つあれば、同時に２人で切ることが出来る。）

m人の人がいる時に、長さncmの棒は最低何回で1cmのかけらの集合体になるかを考えていきます。

考え方

棒の長さとかけらの数、切られた棒の個数と人の数によって処理を変えていきます。

まずはかけらの個数が棒の長さよりも大きくなった場合の処理を書きます

qiita.rb

def barcutting(people, length, pieces)
  if pieces >= length
    0
  end
end

ここでは、長さをlength(cm)、人数をpeople(人)、かけらの数をpeices(個)とします。
また、barcutting関数を定義し、値が与えられると自動的に切り分ける回数を返す様にします。

piecesは最終的には1cmになっているはずなので、その合計の長さが元々の棒の長さ(length)以上になった場合に、切る回数のカウントを止めています。

次にかけらの個数より切る人数が多い場合の処理を書いていきます

qiita.rb

def barcutting(people, length, pieces)
  if pieces >= length
    0
  else pieces < people
    1 + barcutting(people, length, pieces * 2)
  end
end

かけらの数よりも人数が多い場合は、全てのかけらを半分に切ることが出来るので、かけらの数は２倍になります。ここではbarcutting関数の中で再度barcutting関数を呼び出して、piecesの数を２倍にしています。また、その際に１を足すことで、切る回数のカウントも1つ増やしています。

最後に切る人数よりかけらの個数が多い場合の処理を書いていきます

qiita.rb

def barcutting(people, length, pieces)
  if pieces >= length
    0
  elsif pieces < people
    1 + barcutting(people, length, pieces * 2)
  else
    1 + barcutting(people, length, pieces + people)
  end
end

切る人数よりもかけらの数が多い場合は、全てのかけらを半分に切ることができません。１本の棒（かけら）を同時に切ることが出来るのは１人だけです。なので、人数分のかけらだけ半分に切ることができます。
ここでは再度関数内でbarcutting関数を呼び出し、piecesの数に人数分の値を加えています。そうすることで、人数分だけ、かけらの数を増やす事が出来ます。また、その際に切る回数のカウントも1つ増やしています。

答え

qiita.rb

def barcutting(people, length, pieces)
  if pieces >= length
    0
  elsif pieces < people
    1 + barcutting(people, length, pieces * 2)
  else
    1 + barcutting(people, length, pieces + people)
  end
end
puts barcutting(3, 20, 1)
puts barcutting(5, 100, 1)

qiita.rb

8
22

ちなみに

再帰関数を使わない方法も模索中です。。。