プログラマ脳を鍛える数学パズル 4, 5

プログラマ脳を鍛える数学パズル シンプルで高速なコードが書けるようになる70問

問題 4

出題意図は…ルールの読み替えができるかどうか…だろうか？

def cout_days(length, cutters):
    rods = 1
    days = 0
    # 棒が何本に増えたかという考え方をする。
    # 20m の棒を切っていくなら、rods が 20 本になった時点が終了地点のはずだ
    while rods < length:
        days += 1
        if rods < cutters:
            # 棒の本数が切断者を下回るなら、全ての棒が2等分されたはずだ
            rods *= 2
        else:
            # 棒の本数が切断者を上回るなら、切断者が全員仕事したはず。
            # 既存の棒を切って増やしたなら切断者の数だけ増える
            rods += cutters
    return days


print(cout_days(20, 3))  # 20m を 3 人で
print(cout_days(100, 5))  # 100m を 5 人で

問題5

MAX15 枚以下で、両替の組み合わせを計算せよ。

組み合わせを作る問題。
Python, Scala, Ruby なんかは、 combination 関数があるので、それを呼べば一発。

だけど、敢えて再起で書いてみた

max_stack = 15
memo = {}

def exchange(remain, usables, coin_stack):
    # メモがあるならそこから返す
    key = (remain, len(usables), len(coin_stack))
    if key in memo:
        return memo[key]

    if remain == 0:
        # 再起の果てで、0 円達成 = 両替できたらOK終了
        print(coin_stack)
        return 1
    elif len(coin_stack) >= max_stack:
        # コインの組み合わせが 15 を超えそうなら、NG
        return 0

    counter = 0

    for next in range(len(usables)):
        next_coins = usables[next:]  # 使えるコインの種類は、そのままか先頭から１種類減る
        next_remain = remain - next_coins[0]  # 残りの支払い金額計算して
        next_stack = coin_stack[:]
        next_stack.append(next_coins[0])  # コインスタックを増やす(表示用)
        counter += exchange(next_remain, next_coins, next_stack)

    # 戻ってきたらメモに記録
    memo[key] = counter
    return counter


print(exchange(1000, [500, 100, 50, 10], []))

メモ化しとけばはやいかなーと思ったのだけど、そもそもこれの意味があるか分からない。
メモ化は後付け。

ちなみに順列の場合は、利用可能なコインなんて引数持たずに、[500, 100, 50, 10] でしれっと再起すればいい。
再起階層にリミットがあるので、普通のマシンでバッファオーバーフローとか考える必要がないのは楽。