第10話 ３次順列のトレース第４回
コード再掲
#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であることに注意して以下をお読みください。
これで重複がなくなり、
と３つ目の順列213がコンソールに打ち出されます。部屋2ループは終わりましたので、
部屋2は消滅して
部屋1のループは２巡目となり、
重複があるので最後のループに進みます。
if (s + 1 < n)f(s + 1); //１つ上の次元に飛翔（1つ奥の部屋に入室）
によって、部屋2が生成して
部屋2の最初のループで1が入ります。
重複がないので
for (int j = 0; j < n; j++) { //順列を表示
cout << a[j] << " ";
}
によって、
４個目の順列がコンソールに出力されます。
部屋2のループが進み
この状態も
if (s > 0) {
for (int j = 0; j < s; j++) {
if (i == a[j])goto tobi;
a[s] = i;
}
}
の規則を侵しているのであり得ません。
この状態も
if (s > 0) {
for (int j = 0; j < s; j++) {
if (i == a[j])goto tobi;
a[s] = i;
}
}
の規則を侵しているのであり得ません。
部屋2のループは終わり部屋2は消滅します。
さらに、部屋1もループが終わり消滅して、
iのループが進み
if (s + 1 < n)f(s + 1); //１つ上の次元に飛翔（1つ奥の部屋に入室）
によって部屋1が生成され、
となり重複がないので
if (s + 1 < n)f(s + 1); //１つ上の次元に飛翔（1つ奥の部屋に入室）
によって部屋2が生成され、
この状態も
if (s > 0) {
for (int j = 0; j < s; j++) {
if (i == a[j])goto tobi;
a[s] = i;
}
}
の規則を侵しているのであり得ません。
312で重複がなく６個目の順列が出力され、
部屋2はiのループが残っているので、
この状態も
if (s > 0) {
for (int j = 0; j < s; j++) {
if (i == a[j])goto tobi;
a[s] = i;
}
}
の規則を侵しているのであり得ません。
部屋2は消滅して、
となり部屋1のiのループが進み、
重複がないので、
if (s + 1 < n)f(s + 1); //１つ上の次元に飛翔（1つ奥の部屋に入室）
によって部屋2が生成され、
321と重複がないのでコンソールに出力され、
となります。
と
はいずれも
if (s > 0) {
for (int j = 0; j < s; j++) {
if (i == a[j])goto tobi;
a[s] = i;
}
}
の禁則を侵しているのであり得ません。
部屋2は消滅します。
部屋1のループが進み
if (s > 0) {
for (int j = 0; j < s; j++) {
if (i == a[j])goto tobi;
a[s] = i;
}
}
によって、tobiに飛ばされますから
したがって、より上の次元への移動＝より奥の部屋への入室もあり得ず
部屋1が消滅し、
最後に部屋0も消滅します。
すでに出力されており、
cout << "順列の場合の数は" << cn << "です。" << endl;
cout << "プロジェクト成功" << endl;
によって出力され
となってプロジェクトは成功です。
さて、第11話では９次順列から３次魔方陣を生成させるにはどうしたらよいか、
を説明します。
第９話へ 第11話へ
トップへ