第７話 ３次順列のトレース第１回
コード再掲
#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:;
}
}
では n = 3 の場合でトレースしてみましょう。
n = 3ですからnは3として記述します。
そして、皆さんはそれを参考にして
n = 4 の場合・n = 5 の場合でトレースしてください。
s = 0(f(0)の0)のとき0（茶色の）部屋にいます。
for (int i = 1; i < 3 + 1; i++) {
if (s == 0) {
a[s] = i;
}
すなわち
for (int i = 1; i < 4; i++) {
if (s == 0) {
a[s] = i;
}
によって1が入り a[0] = 1 となります。
if (s > 0) {
for (int j = 0; j < s; j++) {
if (i == a[j])goto tobi;
a[s] = i;
}
}
s = 0ですから間の４行は実行されずに、
if (s + 1 < 3)f(s + 1); //１つ上の次元に飛翔（1つ奥の部屋に入室）
s + 1は1なのでf(s + 1);が実行され1つ上の次元に飛翔して赤の部屋に移動して赤の部屋に入ります。
現在どの部屋にいるかを明確に掴んでください。
赤の部屋に入ったということはf(1)です。
すなわちs = 1です。
for (int i = 1; i < 4; i++) {//赤の部屋のfor文最初の状態でi = 1です。
（本来は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 == 0) {
a[s] = i;
}
のa[s] = i;は実行されずに
if (s > 0) {
for (int j = 0; j < s; j++) {
if (i == a[j])goto tobi;
a[s] = i;
}
}
に進み、
for (int j = 0; j < s; j++) {
は
for (int j = 0; j < 1; j++) {
でこのfor文は1回だけ実行され、
if (i == a[j])goto tobi;
は
if (1 == a[0])goto tobi;
a[0] = 1でしたから等号が成り立ち、
tobi:;
に飛び
for (int i = 1; i < 4; i++) {
の２回目でi = 2となります。
s = 1のために
if (s == 0) {
a[s] = i;
}
は実行されずに
if (s > 0) {
for (int j = 0; j < 1; j++) {
if (i == a[j])goto tobi;
a[s] = i;
}
}
に進み、for (int j = 0; j < 1; j++) {
if (i == a[j])goto tobi;
a[s] = i;
}
の第１回が実行され、i == a[j]は2 == a[0]すなわち2 == 1
となり等号が成立せずにif (i == a[j])goto tobi;は無視され、
a[s] = i;
からa[1] = 2;
となります。部屋0と部屋1には異なる人が入ります。
ごめんなさい！疲れてしまったので続きは明日以降にします。
第６話へ 第８話へ
トップへ