1
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 5 years have passed since last update.

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

Posted at

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

1
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
1
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?