第５話へ 第７話へ
第１５講 関数の再帰的呼び出しによる順列の作成
第６話 順列作成プログラムの解説２（遙かなるトレースへの旅立ち）
コード再掲
#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;
}
各関数に任務を確認したので、いよいよ遙かなる頂きへのトレースを始めましょう。
トレースは３次順列で行う前話の説明を思い出してください。
cn=0;
で順列総数カウンターが０に初期化され、
f1(0);
によって、g=0の条件の下に１番外側の人形が呼び出されます。
この際このプログラムを理解するのに大切なのが、
void f1(int g);
のgの役割を掴むことです。
gとは何かといういいますと、
外側から何番目の人形であることを示しています。
ただす、０から始まりますのでg=0のときは外側から1番目の人形を指しています。
つまり、g+1が外側から何番目の人形かを示しています。
入れ子式の人形で比喩しているgの役割は、実際には何でしょうか。
実はセル番号です。
| ０ | １ | ２ |
セル番号はどの次元世界であるかを示しています。
セル番号が０なら１番目のセルを
セル番号が１なら２番目のセルを
セル番号が２なら３番目のセルを
示しています。
このプログラムを理解する上大切なことは、セル番号とセルに入る数字の関係です。
| ２ | １ | ３ |
二つの関係は、ビール瓶におけるラベルと瓶の中に入っているビールの関係に相当します。
一番搾りというラベルの貼った、
ビール瓶においてラベルと内容物であるビールを混同する人はいませんが、
順列プログラムにおいては、まったく違うものを混同してしまう可能性があります。
理由は、０・１・２と１・２・３と一つずれていますが、両方とも同じ整数であるからです。
gは世界の識別番号＝セル番号であり、
for(i=1;i<n+1;i++){
a[g]=i;
のiはその識別番号のセルに入れられる数字です。
gとiの役割の違いを明確にすることがこのプログラムを理解するために肝要です。
| ０ | １ | ２ |
| ２ | １ | ３ |
セル番号＝世界の識別番号 gはビール瓶のラベルであり、
セルに入る数字iはビール瓶に入っているビールに相当するものです。
f1(0);
によって、１番目の人形が呼び出されたとき、
まだ、２番目３番目の人形は存在していませんので、
| ０ |
という状態です。１番目の人形のみがメモリー上に存在していて、
呼び出されたばかりではまだ何の仕事もしていませんので、
空欄なのです。働き始めて、セルに内容である数字（ビールに相当するもの）が入ります。
C言語 C++講義第1部へ
VB講義へ
ＶＢ講義基礎へ
vc++講義へ第1部へ
初心者のための世界で一番わかりやすいVisual C++入門基礎講座
初心者のための世界で一番わかりやすいVisual Basic入門基礎講座
初心者のための世界で一番わかりやすいVBA入門講義（基礎から応用まで）
