Help us understand the problem. What is going on with this article?

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で公開したものをに加筆・修正したものです。

Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
No comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
ユーザーは見つかりませんでした