第６話へ 第８話へ
第１５講 関数の再帰的呼び出しによる順列の作成
第７話 順列作成プログラムの解説３（遙かなるトレースその２）
コード再掲
#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;
によって、
| ０ |
| １ |
１番目の人形＝１番目のセル＝セル番号g=0のセルに内容物である１が入ります。
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)が呼び出されます。つまり、２番目の人形が呼び出され２番目のセルが発生します。
| ０ | １ |
| １ |
この状態では２つの人形が存在しています。
入れ子式の人形はあくまで比喩にすぎません。
入れ子式人形なら、七福神の場合はじめから一番大きい人形に人形が６つ入っていますが、
関数の再帰的呼び出しにおいては、呼び出されたときに初めて人形が発生するのです。
ですから入れ子式の人形は、現時点においては２個しかありません。
セル番号0の人形（一番外側の人形）とセル番号1の人形（外側から２番目の人形）のみです。
外側から２番目の人形の内側には、人形は存在しないのです。
さて、２番目の人形の
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();
}
}
は実行されず、２番目の人形の第２回ループとなり
| ０ | １ |
| １ | ２ |
となりますが、これは重複検査
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)が呼び出され、３番目の人形が発生します。
| ０ | １ | ２ |
| １ | ２ |
となります。
C言語 C++講義第1部へ
VB講義へ
ＶＢ講義基礎へ
vc++講義へ第1部へ
初心者のための世界で一番わかりやすいVisual C++入門基礎講座
初心者のための世界で一番わかりやすいVisual Basic入門基礎講座
初心者のための世界で一番わかりやすいVBA入門講義（基礎から応用まで）
