第１５講 関数の再帰的呼び出しによる順列の作成
第９話 順列作成プログラムの解説５（遙かなるトレースその４）
コード再掲
#include<iostream>
using namespace std;
void f1(int g);
void f2();
int n,cn;
int a[20];
int main(){
cout<<"何次順列を作成させるのかキーボードから入力してください。"<<endl;
cout<<"次数＝";
scanf("%d",&n);
cn=0;
f1(0);
cout<<"順列が"<<cn<<"個できました。"<<endl;
}
void f1(int g){
int i,j,h;
for(i=1;i<n+1;i++){
a[g]=i;
h=1;
if(g>0){
for(j=0;j<g;j++){
if(a[g]==a[j]){
h=0;
break;
}
}
}
if(h==1){
if(g+1<n){
f1(g+1);
}
else{
cn++;
f2();
}
}
}
}
void f2(){
int i;
for(i=0;i<n;i++){
cout<<a[i]<<" ";
}
cout<<endl;
}
| ０ | １ | ２ |
| １ | ２ | ３ |
さて、３番目の人形は順列の１個目を発見すると、消滅の時を迎えます。
なぜなら、
for(i=1;i<n+1;i++){
a[g]=i;
h=1;
if(g>0){
for(j=0;j<g;j++){
if(a[g]==a[j]){
h=0;
break;
}
}
}
if(h==1){
if(g+1<n){
f1(g+1);
}
else{
cn++;
f2();
}
}
}
のすべてのループが終了しているからです。
関数は終了と同時に消滅します。
従いまして、入れ子式の人形の３番目の人形は消えて無くなります。
内側の人形が発生したり消滅したりを繰り返すのです。
一番外側に人形でさえ最後には消滅の運命を辿ります。
| ０ | １ |
| １ | ２ |
ただし、人形は消滅しますが、int a[20];はグローバル配列でしたからa[2]=3のデータは残っています。
今回は、順列の重複は常に外側の人形と、つまり自分より若いセル番号と比較されるので、
データが残っていても問題ありませんが、後に学習が進みと魔方陣をより高速作成させる段階で、
データが残っていると問題を残す場合にも遭遇します。
データを消す場合には
void f1(int g){
int i,j,h;
for(i=1;i<n+1;i++){
a[g]=i;
h=1;
if(g>0){
for(j=0;j<g;j++){
if(a[g]==a[j]){
h=0;
break;
}
}
}
if(h==1){
if(g+1<n){
f1(g+1);
}
else{
cn++;
f2();
}
}
}
a[y][x]=0;
}
のピンクの1行が必要になります。
順列作成では自分よりセル番号が大きいセルとは重複を検査しませんので、
ピンクの部分は不要です。
もちろん、入れておいても問題はありません。
配列がグローバルであるのに対して、関数f1は動的関数ですから、任務終了とともに消滅します。
ですから、
| ０ | １ |
| １ | ２ |
のイメージが正しいのです。
さて、２番目の人形のループ第３巡目によって
| ０ | １ |
| １ | ３ |
隣これは重複検査をすり抜け、
if(h==1){
if(g+1<n){
f1(g+1);
}
else{
cn++;
f2();
}
}
によって、２回目の３番目の人形の誕生を迎えます。
| ０ | １ | ２ |
| １ | ３ |
もちろん、２回目の生誕を迎えた人形は２回目の生であることを知りません。
輪廻とは違い関数は生きていた痕跡さえ残さないのですから。
とっていってもコンソール画面には、
１個目の順列が表示されているのですから、比喩にすぎません。
C言語 C++講義第1部へ
VB講義へ
ＶＢ講義基礎へ
vc++講義へ第1部へ
初心者のための世界で一番わかりやすいVisual C++入門基礎講座
初心者のための世界で一番わかりやすいVisual Basic入門基礎講座
初心者のための世界で一番わかりやすいVBA入門講義（基礎から応用まで）
