棒の切り分け：「プログラマ脳を鍛える数学パズル」Q04の答え

問題

長さn[cm]の一本の棒を1[cm]単位に切り分けることを考えます。一本の棒を一度に切ることができるのは一人だけです。（切り分けられた棒が三本あれば、同時に三人で切ることができます。）
最大m人の人がいるとき、最短何回で切り分けることができるかを求めてください。
例えば、n=8, m=3のときは次の図のようになり、4回で切り分けることができます。

問１．n=20, m=3のときの回数を求めてください。
問２．n=100, m=5のときの回数を求めてください。

元ネタ：
第8回「今週のアルゴリズム：棒の切り分け」正解者発表｜CodeIQ MAGAZINE

わたしの考え方

棒を１回切るごとに断片が1個増える。
n[cm]の棒を1[cm]単位に切り分ける＝n個の断片にすればよい。
切ることが出来る人数が１人ずつ増えて行き、m[人]で打ち止めになる。

わたしのオリジナル解答

def Cut_Tree(m, n):
    stick = 1
    t = 0
    c = 1
    while stick < n:
        if c < m:
            stick = stick + c
            t += 1
            c += 1
        else:
            stick = stick + m
            t += 1
    return t

print Cut_Tree(3, 20)
print Cut_Tree(5, 100)

模範解答のミソ

模範解答では、最初は棒の数を倍増させ、途中から+mすると言うコードになっているが、このやり方はスマートでない気がする。
もう一つの解法として、発想を逆転させて1[cm]の棒をm[人]で結合してn[cm]の棒を作ると読み替える方法が提示されている。
これに基づいてコード修正してみた。

修正されたわたしの解答

def Cut_Tree(m, n):
    stick = 1
    t = 0
    while stick < n:
        if stick < m:
            stick = stick + stick
        else:
            stick = stick + m
        t += 1
    return t

print Cut_Tree(3, 20)
print Cut_Tree(5, 100)