第15講 関数の再帰的呼び出しによる順列の作成
第7話 順列作成プログラムの解説3(遙かなるトレースその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;
}

   for(i=1;i<n+1;i++){
     a[g]=i;
によって、

1番目の人形=1番目のセル=セル番号g=0のセルに内容物である1が入ります。
g=0ですから、if文
     if(g>0){
       for(j=0;j<g;j++){
         if(a[g]==a[j]){
           h=0;
           break;
         }
       }
     }

は実行されませんので、h=1のままで、次のif文
     if(h==1){
       if(g+1<n){
         f1(g+1);
       }
       else{
         cn++;
         f2();
       }
     }

が実施されます。g+1=0+1=1ですからg+1<nは真ですので、
         f1(g+1);
によって、f1(1)が呼び出されます。つまり、2番目の人形が呼び出され2番目のセルが発生します。

 

この状態では2つの人形が存在しています。
入れ子式の人形はあくまで比喩にすぎません。
入れ子式人形なら、七福神の場合はじめから一番大きい人形に人形が6つ入っていますが、
関数の再帰的呼び出しにおいては、呼び出されたときに初めて人形が発生するのです。
ですから入れ子式の人形は、現時点においては2個しかありません。
セル番号0の人形(一番外側の人形)とセル番号1の人形(外側から2番目の人形)のみです。
外側から2番目の人形の内側には、人形は存在しないのです。

さて、2番目の人形の
   for(i=1;i<n+1;i++){
     a[g]=i;
の最初のループによって

となります。g=1ですから、if
     if(g>0){
       for(j=0;j<g;j++){
         if(a[g]==a[j]){
           h=0;
           break;
         }
       }
     }
が遂行されます。
       for(j=0;j<g;j++){
         if(a[g]==a[j]){
           h=0;
           break;
         }
       }

の第1回目のループで
         if(1==1)
なので、

           h=0;
           break;

の命令が遂行されます。すると、h=0ですから
   if(h==1){
       if(g+1<n){
         f1(g+1);
       }
       else{
         cn++;
         f2();
       }
     }

は実行されず、2番目の人形の第2回ループとなり

となりますが、これは重複検査
     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();
       }
     }
が実行され、f1(2)が呼び出され、3番目の人形が発生します。

 

となります。

 








第6話へ 第8話へ

戻る

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

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