第８話 ３次順列のトレース第３回
コード再掲
#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であることに注意して以下をお読みください。
各部屋には１人しか入れない原則の通りで、
３つ部屋に異なる３人が入っています。
void f(int s) {
for (int i = 1; i < 4; 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:;
}
}
最後の２行によって、
どの世界に戻りますか。
答えは20行下。
動的関数についてまだ説明していませんでした。
本当は上図は正しくありません。
本当は
です。
動的関数とは任務を与えられているときだけ存在し、
任務を終えると消滅するのです。
C++やC言語は基本的には動的変数ないしは動的関数によって組み立てられています。
演劇で自分の役まで進んだら舞台に上がり、
自分の役が終わったらステージから降ります。
それと同じで動的変数や動的関数は任務がある時だけステージに上がり、
任務を終えたら舞台から降りるのです。
ステージや舞台は比喩でして、
正確には、自分の番になったらメモリに登場して、終わったらメモリから去ります。
「終わったらメモリから去ります」をより正確に言うとメモリから消滅します、となります。
動的関数や動的変数は生成消滅を限りなく繰り返しています。
なぜ、そんなことをするのでしょうか。
理由は、ステージ＝メモリ大きさに限りがあるからです。
任務を与えられたときにメモリ上に生成され、
任務を終了したらメモリ上から消滅するわけです。
ですから、前話の
も正しくは、
です。部屋1と部屋2はメモリ上にまだ生まれてきていません。
を使うときは、現在のみでなく未来のことも考えていることになります。
現在メモリ上に存在している部屋は
のみです。
大事な脱線でしたが、話を元に戻します。
これは部屋1に戻り、
for (int i = 1; i < 4; i++) {
の第２ループが終わり、第３ループに入りました。
そして、
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;
}
}
があるからです。したがって、第２ループに入り、
となります。こうして、
無事に第２個目の順列が生成されました。第７話へ 第９話へ
トップへ