第９話 ３次順列のトレース第４回
コード再掲
#include<iostream>
using namespace std;
void f(int s); //sは次元番号=部屋番号
int n; //次元数（部屋数）をキーボードから指定
int cn = 0; //順列を数える変数
int a[10];//大きめにとった
int main() {
cout << "n = ";
scanf_s("%d", &n); //キーボードからnの値を取得
f(0);
cout << "順列の場合の数は" << cn << "です。" << endl;
cout << "プロジェクト成功" << endl;
return(0);
}
void f(int s) {
for (int i = 1; i < n + 1; i++) {
if (s == 0) {
a[s] = i;
}
if (s > 0) {
for (int j = 0; j < s; j++) {
if (i == a[j])goto tobi;
a[s] = i;
}
}
if (s + 1 < n)f(s + 1); //１つ上の次元に飛翔（1つ奥の部屋に入室）
if (s + 1 == n) { //一番奥の部屋に到達！
for (int j = 0; j < n; j++) { //順列を表示
cout << a[j] << " ";
}
cout << endl;
cn++; //順列数をカウント
}
tobi:;
}
}
図の上はsに対応した部屋番号であり、
下は人の出席番号iであることに注意して以下をお読みください。
if (s > 0) {
for (int j = 0; j < s; j++) {
if (i == a[j])goto tobi;
a[s] = i;
}
}
tobi;に飛ばされますから
はありえません。
以下は図のみを追います。
重複なく３つの部屋に異なる３人が入ったので、
と表示されます。部屋2のループは終わったので、
メモリ上から部屋2は消滅して、
となります。そして、部屋0の第２ループによって、
となり、
if (s + 1 < n)f(s + 1); //１つ上の次元に飛翔（1つ奥の部屋に入室）
によって部屋1が再生成され、
図の上はsに対応した部屋番号であり、
下は人の出席番号iであることに注意して以下をお読みください。
部屋1は再生成といっても前世の記憶を持っているわけではないので、
再振出しなりiの第１ループから始まります。
出席番号1が重複していませんから、
if (s + 1 < n)f(s + 1); //１つ上の次元に飛翔（1つ奥の部屋に入室）
によって、
上の次元へと跳躍します。
の２つの状態は、
上は211、下は213と重複があるので、
if (s > 0) {
for (int j = 0; j < s; j++) {
if (i == a[j])goto tobi;
a[s] = i;
}
}
によってtobi;に飛ばされますから
起こりません。
これで重複がなくなり、
３個目の順列が出力されます。
第８話へ 第10話へ
トップへ