2009年02月19日

[パズル]覆銭問題

  

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

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


『ナノピコ教室』の解答には、数学的な考察がなされており、どうやったら、高速なプログラムになるか(つまり計算式を導き出す方法)が書いてありますが、僕には難しすぎて理解できないので、素直に解いてみました。

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

以下にC#のコードを示します。
毎度のことながら、一部でLINQを使って書いています。

using System;
using System.Collections.Generic;
using System.Linq;

namespace fukusen {
class Program {
static void Main(string[] args) {
for (int i = 1; i < 20; i++) {
Solver sol = new Solver(i);
int n = sol.Execute();
Console.WriteLine("f({0}) = {1}", i, n);
}
}
}

class Solver {
private int number;
private bool[] disks;
public Solver(int n) {
number = n;
disks = new bool[n]; // 初期状態はすべて false
}

// 1,2,3,...n,1,2,3,...n,1,2,3,...nを永遠に繰り返す
IEnumerable<int> Repeat(int number) {
IEnumerable<int> nums = Enumerable.Range(1, number);
while (true) {
foreach (var n in nums)
yield return n;
}
}

public int Execute() {
int count = 0;
foreach (var n in Repeat(number)) {
Turn(n);
count++;
if (IsFin())
break;
}
return count;
}

// N枚のコインをひっくり返す。
public void Turn(int n) {
int i = 0;
int j = n - 1;
while (i <= j) {
bool temp = disks[i];
disks[i++] = !disks[j];
disks[j--] = !temp;
}
}

public bool IsFin() {
return disks.All(d => d == false);
}
}
}

>


※当記事に掲載したコードは、『ナノピコ教室・プログラミング問題集』(駒木悠二+有澤誠 編 共立出版株式会社)に掲載されている問題をGushwellがC#で解いたものです。


 

この記事へのトラックバックURL