小町数を使った数学パズルの第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で公開したものをに加筆・修正したものです。