[パズル]覆銭問題 (Penny Flipping Problem)

 覆銭問題とは、積み上げたコインを以下の手順でひっくり返すと何回目で初期状態に戻るかというものです。

1. n枚のコインを全部表にして積み上げる
2. 最初に、上の1枚を裏返す。次に上から2枚目をまとめてひっくり返す。次に3枚、4枚とひっくり返す。
3. n枚全体をひっくり返したら、また1枚に戻る。
4. この手順を繰り返す。

英語では、Penny Flipping Problem というらしいです。



初期設定のコードを省略するために、コインの表を false, 裏を trueで表しています。回数を求めるのにどちらが表面でも同じですから。
配列にセットしたコイン(bool型)を実際にひっくり返していって、元の状態(すべてがfalse)に戻るまで、処理を繰り返しています。

なお、PennyFlippingクラスのSolveメソッドが、コインをひっくり返す処理をしていて、その回数を返しています。
せっかくなので、途中結果も表示したいので、コインをひっくり返すたびにイベントを発生させるようにし、MainPageクラスに定義したイベントハンドラで、TextBlockに、その時の状態(文字列として表現)を追加しています。
ということで、C#でイベントを定義するサンプルともなっています。

とはいっても、別スレッドで動かしているわけではないので、描画は最後にまとめて描画されます。入力できる数を20までに制限しているので、描画開始されるまでの時間はそれほど気になりませんが、もっと大きな数字にも対応するには、PennyFlippingクラスを別スレッドで動かす必要がありそうです。

それと、PennyFlippingクラスには、無限に繰り返すRepeatメソッドを定義している点に注目です。
IEnumerable<int>を返しているので、本当に無限ループしているわけではありませんが、事前に何回繰り返したら良いかわからない問題では、こういったメソッドを定義すると、すっきりしたコードが書けると思います。


■PennyFlipping.cs
■MainPage.xaml.cs
 
■MainPage.xaml
  
※『ナノピコ教室・プログラミング問題集』(駒木悠二+有澤誠 編 共立出版株式会社)に掲載されている問題を一部変更し、GushwellがC#で解いたものです。