ホームページへ戻る
第１章: 探索の基本（forループ探索）
いきなりですが、問題です。
例題１: 虫食い算(A)
 | 左図の筆算が成立するように□の中に数字を埋めなさい。 |
|
この問題を人が解く場合、例えばこんな考え方をするでしょう。
| ・ |
もし、最上段の２桁の数が81なら、「81×99＝8019」でも計算結果となる最下段の４桁目が９に満たない。
従って、最上段の２桁の数は91でなければならない。
|
| ・ |
もし、二段目の２桁の数が98なら、「91×98＝8918」でも計算結果となる最下段の４桁目が９に満たない。
従って、二段目の２桁の数は99でなければならない。
|
結果、「91×99＝９００９」が答えになる。解決の糸口を発見できたので、見事に解答が出ました。では、次の問題はどうでしょう。
例題２: 虫食い算(B)
 | 左図の筆算が成立するように□の中に数字を埋めなさい。 |
|
これは、解決の糸口がつかみにくい問題です。でもコンピュータなら、例題１も例題２も、同じ解き方で簡単に答を求めてしまいます。コンピュータはこんな方法で解きます。
| ・ |
２桁の数は、１０から９９の９０種類ある。従って、２桁×２桁の組み合わせは全部で「90×90＝8100」通りある。
|
| ・ |
このすべての組み合わせを試みて題意に一致するものを見つける。
|
全くあきれ果てた方法ですね。そもそもコンピュータ自体に思考能力などはありません。コンピュータは単純な多量の演算を高速に実行するという能力を持っているだけなのです。
では、この「例題２：虫食い算(B)」に挑戦してみましょう。
総てのパターンを生成
２桁の数は10から99までの90通り。２桁×２桁の組み合わせは90×90=8100通り。
この総ての組み合わせを順次生成するには、こんな記述で簡単に実現出来ます。List.1-1
|
題意との一致を調べる
上の処理で生成された8100通りの各パターンをそれぞれ題意と一致するかチェックします。
| ・ |
各数字の桁数をチェック
３段目と４段目の数は３桁。５段目の数は４桁でなければなりません。
例えば３桁かどうかをチェックするには、こんな記述になります。 List.1-2
|
| ・ |
指定された位置の数のチェック
指定されている位置の数のチェックは少し面倒な記述になりますが、
先に、ある数ｎのｍ桁目の数を取得出来る関数 PosN(m,n) を作っておけば
楽になります。そうすれば、ｄの３桁目が４かどうかをチェックする記述は
こうなります。List.1-3
|
|
以上の準備を踏まえておけば、例題２を解くプログラムは次のようになります。List.1-4
ホームページへ戻る
|
List.1-1
// 総てのパターンを生成
for (a=10; a<=99; a++) { // 1段目の数を生成
for (b=10; b<=99; b++) { // 2段目 〃
// この場所で90×90=8100通りの
// 組み合わせが順次実現される
}
}
List.1-2
// ３桁チェック
if (c>=100 && c<=999) {
// この場所はcが３桁の数である場合のみ
}
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;
}
// 虫食い算(例題２)を解く
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; // 解の記録
}
}
}
}
}
|
