第15講 関数の再帰的呼び出しによる順列の作成
第6話 順列作成プログラムの解説2(遙かなるトレースへの旅立ち)
コード再掲
#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;
}
各関数に任務を確認したので、いよいよ遙かなる頂きへのトレースを始めましょう。
トレースは3次順列で行う前話の説明を思い出してください。
   cn=0;
で順列総数カウンターが0に初期化され、
   f1(0);
によって、g=0の条件の下に1番外側の人形が呼び出されます。
この際このプログラムを理解するのに大切なのが、
void f1(int g);
のgの役割を掴むことです。
gとは何かといういいますと、
外側から何番目の人形であることを示しています。
ただす、0から始まりますのでg=0のときは外側から1番目の人形を指しています。
つまり、g+1が外側から何番目の人形かを示しています。
入れ子式の人形で比喩しているgの役割は、実際には何でしょうか。
実はセル番号です。

セル番号はどの次元世界であるかを示しています。
セル番号が0なら1番目のセルを
セル番号が1なら2番目のセルを
セル番号が2なら3番目のセルを
示しています。
このプログラムを理解する上大切なことは、セル番号とセルに入る数字の関係です。

二つの関係は、ビール瓶におけるラベルと瓶の中に入っているビールの関係に相当します。
一番搾りというラベルの貼った、
ビール瓶においてラベルと内容物であるビールを混同する人はいませんが、
順列プログラムにおいては、まったく違うものを混同してしまう可能性があります。
理由は、0・1・21・2・3と一つずれていますが、両方とも同じ整数であるからです。
gは世界の識別番号=セル番号であり、
   fo
r(i=1;i<n+1;i++){
     a[g]=i;
iはその識別番号のセルに入れられる数字です。
giの役割の違いを明確にすることがこのプログラムを理解するために肝要です。

セル番号=世界の識別番号 gはビール瓶のラベルであり、
セルに入る数字iはビール瓶に入っているビールに相当するものです。

   f1(0);
によって、1番目の人形が呼び出されたとき、

まだ、2番目3番目の人形は存在していませんので、

という状態です。1番目の人形のみがメモリー上に存在していて、
呼び出されたばかりではまだ何の仕事もしていませんので、
空欄なのです。働き始めて、セルに内容である数字(ビールに相当するもの)が入ります。








第5話へ 第7話へ

戻る

C言語 C++講義第1部へ
VB講義へ
VB講義基礎へ

vc++講義へ第1部へ
初心者のための世界で一番わかりやすいVisual C++入門基礎講座
初心者のための世界で一番わかりやすいVisual Basic入門基礎講座
初心者のための世界で一番わかりやすいVBA入門講義(基礎から応用まで)