パズル問題解法のアルゴリズム講座
入門編
ループ処理でパターン生成
１．総てのパターンを生成
２桁の数は10から99までの90通り。２桁×２桁の組み合わせは90×90=8100通り。この総ての組み合わせを順次生成するには、こんな記述で簡単に実現出来ます。
for (a=10; a <= 99; a++) {
for (b=10; b <= 99; b++) {
この場所で90×90=8100通りの組み合わせが順次実現される
}
}
２．題意との一致を調べる
上の処理で生成された8100通りの各パターンをそれぞれ題意と一致するかチェックします。
・各数字の桁数をチェック
３段目と４段目の数は３桁。５段目の数は４桁でなければなりません。
例えば３桁かどうかをチェックするには、こんな記述になります。
if (c >= 100 && c <= 999) {
この場所はcが３桁の数である場合のみ
}
・指定された位置における数とのチェック既に指定されている数とのチェックは少し面倒な記述になりますが、
もし、ある数ｎのｍ桁目の数を取得出来る関数があれば簡単です。
そこで、その関数 sub(n,m) を作ってしまいましょう。そうすれば、
ｄの３桁目が４かどうかをチェックする記述はこうなります。
if (sub(d,3) == 4) {
この場所はdの3桁目が4である場合のみ
}
３．プログラムの完成
以上の準備を踏まえておけば、先の例題２を解くプログラムは次のようになります。|
Ｃ言語ソースリスト
Javaアプレットの実行 |
/* 出力情報 */
int A, B; /* 1段目と2段目の数 */
int cnt; /* 解の個数 */
/* 10進数nのm桁目の数を返すサブルーチン */
int sub(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 (sub(d,2)==4 && sub(e,3)==3) { /* 例題1の場合は if (sub(a,1)==1 && sub(e,4)==9) とする */
A = a; B = b; /* 解の記録 */
cnt++; /* 解の個数 */
}
}
}
}
}