第1章: 魔物の正体(forループ探索)

 いきなりですが、問題です。

 例題1: 虫食い算(A)

左図の筆算が成立するように□の中に数字を埋めなさい。


 人がこの問題を解く場合、例えばこんな方法で解くでしょう。

 ・もし、最上段の2桁の数が81なら、「81×99=8019」でも
  最下段の4桁目に満たない。
  従って、最上段の2桁の数は「91」でなければならない。

 ・もし、二段目の2桁の数が98なら、「91×98=8918」でも
  最下段の4桁目に満たない。
   従って、二段目の2桁の数は「99」でなければならない。

結果、「91×99=9009」が答えである。解決の糸口を発見できたので、見事に解答が出ました。では、次の問題はどうでしょう。

 例題2: 虫食い算(B)

左図の筆算が成立するように□の中に数字を埋めなさい。


 これは、解決の糸口がつかみにくい問題です。でもコンピュータなら、例題1も例題2も、同じ解き方で簡単に答を求めてしまうでしょう。コンピュータはこんな方法で解きます。

 ・2桁の数は、10から99の90種類ある。従って、2桁×2桁の
  組み合わせ
は全部で「90×90=8100」通りある。

 ・このすべての組み合わせを試みて題意に一致するものを
  見つける。

 全くあきれ果てた方法ですね。そもそもコンピュータ自体に思考能力などはありません。コンピュータは単純な多量の演算を高速に実行するという能力を持っているだけなのです。


 では、先ほどの「例題2:虫食い算(B)」に挑戦してみましょう。

 総てのパターンを生成

 2桁の数は10から99までの90通り。2桁×2桁の組み合わせは90×90=8100通り。
 この総ての組み合わせを順次生成するには、こんな記述で簡単に実現出来ます。List.1-1

 題意との一致を調べる

 上の処理で生成された8100通りの各パターンをそれぞれ題意と一致するかチェックします。

 ・各数字の桁数をチェック
   3段目と4段目の数は3桁。
   5段目の数は4桁でなければなりません。
  例えば3桁かどうかをチェックするには、こんな
  記述になります。 List.1-2

 ・指定された位置の数のチェック
   指定されている位置の数のチェックは少し面倒な
   記述になりますが、先に、ある数nのm桁目の数
   を取得出来る関数 PosN(m,n) を作っておけば楽に
   なります。そうすれば、dの3桁目が4かどうかを
   チェックする記述はこうなります。List.1-3

 以上の準備を踏まえておけば、例題2を解くプログラムは次のようになります。List.1-4


   ホームページへ戻る
パズル問題解法のアルゴリズム講座

目  次

 第1章: 魔物の正体(forループ探索)

 第2章: 多重ループ探索→再帰呼び出し

 第3章: 反復深化

 第4章: 幅優先探索

 第5章: 2人対戦ゲーム






List.1-1

    // 総てのパターンを生成
    for (a=10; a<=99; a++) {        // 1段目の数を生成
        for (b=10; b<=99; b++) {    // 2段目	〃

            // この場所で90×90=8100通りの
            // 組み合わせが順次実現される

        }
    }

List.1-2

    // 3桁チェック
    if (c>=100 && c<=999) {

        // この場所はcが3桁の数である場合のみ

    }

List.1-3

    // 指定された位置の数をチェック
    if (PosN(d, 3) == 4) {

        // この場所はdの3桁目が4である場合のみ

    }


List.1-4

int A, B;    // 解の記録(1段目と2段目の数)

// 10進数nのm桁目の数を返す関数
int PosN(int n, int m)
{
    int i;

    // nをm-1回,10で割る
    for (i=1; i<m; i++)
        n /= 10;

    // 10で割った余りを返す
    return n % 10;
}
// 虫食い算(例題2)を解く
void Puzzle()
{
    int a, b, c, d, e;

    for (a=10; a<=99; a++) {        // 1段目の数を生成
        for (b=10; b<=99; b++) {    // 2段目    〃

            c = a * (b % 10);       // 3段目の数を計算
            d = a * (b / 10);       // 4段目      〃
            e = a *  b;             // 5段目      〃

            // 各数字の桁数をチェック
            if (c >= 100  && c <= 999 &&
                d >= 100  && d <= 999 &&
                e >= 1000 && e <= 9999) {

                // dの2桁目が4で,eの3桁目が3か?
                if (PosN(d,2)==4 && PosN(e,3)==3) {
                    A = a;  B = b;  // 解の記録
                }
            }
        }
    }
}


Copyright© takaken. All rights reserved.