第12回 結城浩からの挑戦（第6回）解説編 | gihyo.jp

まだ挑戦していない方は、ぜひ先を読み進める前に挑戦してみてください。 キーワードは「ユークリッドの互除法」と「フィボナッチ数列」 今回の問題では、「⁠コンパスとハサミを使って、長方形をチョキチョキと切る」というルールが与えられています。そのルールに注意しつつ、「⁠ハサミを使う回数をできるだけ少なくするような長方形を求めなさい」という問題ですね。 このルールがいったい何を意味しているのかを見抜くことが、問題を解くうえで重要になってきます。 今回のハサミ問題のキーワードは、2つあります。 1つは「ユークリッドの互除法⁠」⁠。 もう1つは「フィボナッチ数列」です。 ユークリッドの互除法の代わりに「互いに素」や「最大公約数」がキーワードだと思ってもよいでしょう。 コンパスとハサミの操作は「ユークリッドの互除法」になっている 「ユークリッドの互除法」は、2つの正の整数が与えられた時、その最大公約数を

[millionsmile]

結城浩さんのハサミ問題の解説記事です。カレー問題の問題に読むとよいかも。

[hyuki]

CodeIQのハサミ問題の解答と解説です。正解者の分布も。