
プログラマ脳を鍛える数学パズル シンプルで高速なコードが書けるようになる70問
- 作者: 増井敏克
- 出版社/メーカー: 翔泳社
- 発売日: 2015/10/14
- メディア: 単行本(ソフトカバー)
- この商品を含むブログ (11件) を見る
問題 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:] # 使えるコインの種類は、そのままか先頭から1種類減る 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]
でしれっと再起すればいい。
再起階層にリミットがあるので、普通のマシンでバッファオーバーフローとか考える必要がないのは楽。