Magicode logo
Magicode
1

5人の海賊と100枚の金貨を雑に解く

論理クイズ

有名な問題である海賊と金貨 が再帰で簡単に書けそうなので解いてみる

過半数で可決と、過半数では否決の2パターンあるので両方に対応したい

 ー 可決するための数を求める関数を少しいじるだけで対応させる

再帰

5人組での最適解は4人組での最適解を見て考え、4人組での最適解は3人組での ... というような線形再帰的な考えが自然だが、「金貨5枚と100人の海賊」のように最初の何人かがどうあがいても否決されてしまう場合に無駄な計算をさせたくなかったので末尾再帰で考えることにした


[(97,1),(0,2),(1,3),(0,4),(2,5)]

感想

過半数で可決の方だとただ"0", "1"が交互になるだけだけど、過半数では否決される方だとなかなか面白い規則が見られる

いろいろ変えて動かしてみてね

Discussion

コメントにはログインが必要です。