Posted at

C#で数学パズル - センチュリーパズル(西洋小町)を効率よく解く

More than 1 year has passed since last update.

小町数を使った数学パズルの第7弾です。たぶん、小町数を使ったパズルはこれが最後。


センチュリーパズルとは

1~9までの数字を1回だけ使って帯分数をつくり、その値が100を表すようにするパズルをセンチュリーパズルと言います。

別の表現だと、「K + N / D = 100」を満たす K,D,Nを求めよ。ただし、K,N,Dは1~9の数を1つずつ使用すること。

となります。

例えば、

3 + 69258 / 714 = 100

は求める答えの一つです。

欧米で知られている小町数パズル(いわゆる西洋小町パズル)のひとつです。(小町: 1-9が一つずつで構成されている)


どうやって解くか

3つの式が等しくなる小町数」では、再帰処理をし1-9の順列を求めることで解を求めました。このセンチュリーパズルも同様の手法が使えますが、ここでは別のアプローチを取ることにします。

K + N / Dのそれぞれが、正の数であることから、Kは、1から99までの値に絞られます。

つまり、

 for (int k = 1; k <= 99; k++) {

...
}

というループの中で、N,D を求めてゆけば良いことになります。

k=3の場合を考えてみると、N/Dは、97になるので、



97/1, 194/2, 291/3, 388/4, 485/5,...



と調べてゆき、K,N,Dが1-9で構成されていれば、求める答えになります。

N,Dは桁数がどんどん増えてゆきますから、K, N,Dの桁数の合計が10桁以上になったら、小町を満たさなくなりますので、Kの処理を終わります。

このパズルは再帰処理を使わないので、容易に理解できると思います。


C#のコード

これをC#のコードにしたのが、以下のコードです。

using System.Linq;

using System.Collections.Generic;

namespace CenturyPuzzleApp {
public class Answer {
public int WholeNumber { get; set; } // K K以外の名前を付けたが...
public int Denominator { get; set; } // D 分母
public int Numerator { get; set; } // N 分子
}

public class CenturyPuzzle {
public IEnumerable<Answer> Solve() {
// CenturyPuzzle
// 整数部を基準にして、総当りで求めている
for (int k = 1; k <= 99; k++) {
var x = 100 - k; // X == N / D
var denominator = 1; // 分母 もっと大きな数から始められるはずだが...
while (true) {
// 分子 K + N / D = 100 となる N を求めている --> N = D * (100 - K)
var numerator = denominator * x;
var frac = $"{k}{numerator}{denominator}";
if (frac.Length > 9)
// これ以上やっても解はない。小町にはならない
break;
if (IsKomachi(frac)) {
yield return new Answer {
WholeNumber = k,
Numerator = numerator,
Denominator = denominator
};
}
denominator++;
}
}
}

// 小町数か、(引数は数値を文字列に変換したもの)
private bool IsKomachi(string s) {
return s.OrderBy(c => c).SequenceEqual("123456789");
}
}
}

using System;

using System.Text;

namespace CenturyPuzzleApp {
class Program {
static void Main(string[] args) {
var cp = new CenturyPuzzle();
var sb = new StringBuilder();
foreach (var a in cp.Solve()) {
sb.AppendFormat("{0} + {1} / {2} = 100\n",
a.WholeNumber, a.Numerator, a.Denominator);
}
Console.WriteLine(sb.ToString());
}
}
}


結果

3 + 69258 / 714 = 100

81 + 5643 / 297 = 100
81 + 7524 / 396 = 100
82 + 3546 / 197 = 100
91 + 5742 / 638 = 100
91 + 5823 / 647 = 100
91 + 7524 / 836 = 100
94 + 1578 / 263 = 100
96 + 1428 / 357 = 100
96 + 1752 / 438 = 100
96 + 2148 / 537 = 100

最初のKの値が3からいきなり81に飛んじゃうんですね。


この記事は、Gushwell's C# Programming Pageで公開したものをに加筆・修正したものです。