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

問題概要

長さnの棒をm人で切って1cm単位にする。ただし一回に切れるのは1人。何ステップで切れるか。

Code

とりあえず何も考えずにやってみたバージョン。方針は「長いものから切っていく」

def cutbar(length, member):
    bar = [length]
    step = 0
    while bar != [1]*len(bar): #すべて長さが1なら終了
        for i in range(min(member, len(bar))):
            piece = bar.pop(0) #先頭(=最大値)を取り出す
            if piece == 1:
                break
            else:
                cut1 = round(piece/2)
                cut2 = piece - cut1
                bar += [cut1, cut2]
        bar.sort(reverse=True) #降順でソート
        step += 1
    return step

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

再起を使って

再帰でやったほうがスマート。以下のコードはほとんど本文の受け売りですが、、、

#Q04棒の切り分け
#再帰を使って

def cutbars(length, member, pieces): #棒の最初の長さ、人数、現在の棒切れの数
    if pieces >= length: #切り終えた
        return 0
    elif pieces < member: #全部の棒切れを一様に切る
        return 1 + cutbars(length, member, pieces * 2)
    else: # member分の棒切れだけを切る
        return 1 + cutbars(length, member, pieces + member)

print(cutbars(20, 3 ,1))
print(cutbars(100, 5, 1))