第２講 試行錯誤法でヒント数０数独の解答を作る（１）
第５話 １からｎまでの和を関数の再帰的使用によって実現
を実現するコード
一見関係なさそうな１～ｎまでの和を求める次のコードを
#include<iostream>
using namespace std;
int f(int s);
int n;
int w = 0;
int main() {
cout << "n = ";
scanf_s("%d", &n); //キーボードからnの値を取得
cout << "1からnまでの和 = " << f(1) << endl;
cout << "プロジェクト成功" << endl;
return(0);
}
int f(int s) {
w += s;
if (s + 1 <= n)f(s + 1);
return(w);
}
関数の再帰的使用によって実現してください。
では、ｎ次順列を関数の再帰的使用によって実現しましょうと言いたいところですが、
初心者の域を出たばかりの人には敷居が高いでしょうから、
ヒントを与えます。
#include<iostream>
using namespace std;
int main() {
int a[5], cn = 0;
for (int i = 1; i < 6; i++) {
a[0] = i; //a[0]に1，2，3, 4, 5を入力
for (int j = 1; j < 6; j++) {
if (j != a[0]) {
a[1] = j; //kがa[0]と一致しない数字を入力
for (int k = 1; k < 6; k++) {
if (k != a[0] && k != a[1]) {
a[2] = k; //kがa[0]とa[1]のいずれとも一致しない数字を入力
for (int l = 1; l < 6; l++) {
if (l != a[0] && l != a[1] && l != a[2])
{
a[3] = l; //ｌがa[0]とa[1]とa[2]のいずれとも一致しない数字を入力
for (int m = 1; m < 6; m++) {
if (m != a[0] && m != a[1] && m != a[2]
&& m != a[3]) {
a[4] = m; //ｌがa[0]とa[1]とa[2]とa[3]のいずれとも一致しない数字を入力
cn++;
cout << a[0] << " " <<
a[1] << " " << a[2] << " " <<
a[3] << " " << a[4] << endl;
}
}
}
}
}
}
}
}
}
cout << "順列の場合の数は" << cn << endl;
cout << "プロジェクト成功" << endl;
return(0);
}
に階層がわかるように色を塗ってみましょう。エクセルとホームページビルダーの色合いが異なるために
完全には一致していませんが色を塗ったコードと下表の色の対応に注目してください。
私は、入れ子式人形（マトリョーシカ人形
）を使って関数の再帰的使用を説明します。
上は５次元for文ですが、入れ子式になっているのがお分かりですね。
関数の再帰的使用を使えばそれぞれの部屋（0，1，2，3, 4）ではfor文を一次元にすることができます。
プログラミングにおいては0からスタートするために部屋番号（0，1，2，3, 4）の場合５部屋になります。
つまり、0をカウントするからです。
普通は1から数えますから、普通の場合には(1, 2, 3, 4, 5)で最後の数字が５で、
部屋番号と部屋数は一致します。
この場合には
for (int i = 1; i < 6; i++) {
a[1] = i; //a[1]に1，2，3, 4, 5を入力
for (int j = 1; j < 6; j++) {
if (j != a[1]) {
a[2] = j; //ｊがa[1]と一致しないときにjを入力
for (int k = 1; k < 6; k++) {
if (k != a[1] && k != a[2]) {
a[3] = k; //kがa[1]とa[2]のいずれとも一致しない数字を入力
for (int l = 1; l < 6; l++) {
if (l != a[1] && l != a[2] && l != a[3]) {
a[4] = l; //ｌがa[1]とa[2]とa[3]のいずれとも一致しない数字を入力
for (int m = 1; m < 6; m++) {
if (m != a[1] && m != a[2] && m != a[3] && m != a[4]) {
a[5] = m; //mがa[1]とa[2]とa[3]とa[4]のいずれとも一致しない数字を入力
cn++;
となります。
-------------------------------------------------
実を言いますと、
「プログラミングにおいては0からスタートするため」
という言い方は正しくありません。
定義の問題で部屋番号を（0，1，2，3, 4）と呼ぶか、
(1, 2, 3, 4, 5)とするかは、
プログラムを書いている人の自由です。
ですから、「プログラマーが0からスタートさせるため」が正確な言い方になります。
なのに私が（0，1，2，3, 4）の呼称を使い続けてきたのは、
読者に部屋番号と部屋に入る人を区別してもらうためというのが一つの理由ですが、
本質的な理由としましては、
int a[6], cn = 0;
としなければならないからです。
要素数がnの場合
int a[n];
ではエラーします。正しくは、
int a[n + 1];
です。a[0]があるからです。
ですが、これはどこにも使われずにメモリを無駄にしているだけです。
それで（0，1，2，3, 4）としてきたわけです。
C言語やC++では
int a[5];の5は要素数（部屋数）です。末尾の数字ではありません。
a[0], a[1], a[2], a[3], a[4]
と並べればわかる通り、要素数（部屋数）は５個です。
ですから、部屋数が５の場合
int a[5];
と宣言しなければなりません。
-------------------------------------------------
普通の部屋は横に並びますが、この世界では入れ子式に並びます。
一番外側の部屋が0の世界、外側から2番目の部屋が1の世界、外側から3番目の部屋が2の世界、
外側から4番目の部屋が3の世界、外側から5番目の部屋が4の世界
となっていることがわかります。
部屋という言葉をよく使いますが、次元という比喩もよく使います。
外側が0次元の世界、2番目が1次元の世界、3番目が2次元の世界、4番目が3次元の世界、5番目が5次元の世界
ですから
の上の数字は部屋番号ないしは次元番号というわけです。
さあ、ｎ次順列自動生成プログラムを組んで、
を実現しましょう。
一応汎用的なプログラムになりましたが、
ｎは10ぐらいが限界です。
第４話へ 第６話へ
