第９講 関数の再帰的使用
第５話 関数の再帰的使用によるｎ次順列生成解説その２
コード再掲
#include<iostream>
using namespace std;
void f(int g);
void h();
int x[15],n;
long cn;
void main(){
　　 cout<<"何次順列を生成しますか？"<<endl;
　　 scanf("%d",&n);
　　 cout<<endl;
　　 cn=0;
　　 f(0);
　　 cout<<n<<"次順列が"<<cn<<"個生成されました。"<<endl;
}
void f(int g){
　　 int i,j;
　　 for(i=1;i<n+1;i++){
　　　　　x[g]=i;
　　　　　if(g>0){
　　　　　　　 for(j=0;j<g;j++){
　　　　　　　　　　if(x[g]==x[j])goto tobi;
　　　　　　　 }
　　　　　}
　　　　　if(g+1<n){
　　　　　　　 f(g+1);
　　　　　}
　　　　　else{
　　　　　　　 h();
　　　　　　　 cn++;
　　　　　}
　　　　　tobi:;
　　 }
}
void h(){
　　 for(char i=0;i<n;i++)cout<<x[i]<<" ";
　　 cout<<endl;
}

解説
最初
int x[15],n;
long cn;
はグローバルにしないで、
f(g,n,cn,x) として関数を呼び出していましが、
次元を決定づけているものはｇであることを強調するために、
今回はx[15]とn、cnはグローバル配列とグローバル変数にしてあります。
このためにf(g)というすっきした呼び出しになっています。
尚、f(g,cn,n,x) とする場合は
**xの最初のアドレスを引数として引き渡していたのでしたね。
**xは実質２次元配列と同じものでしたから、
実質２次元配列を渡していたのです。
　　 cout<<"何次順列を生成しますか？"<<endl;
　　 scanf("%d",&n);
　　 cout<<endl;
　　 cn=0;
２行目で、コンソールから順列の次数を取得しています。
４行目で初期化しています。
cnは、順列総数を数えるカウンタ
（数えるものという意味です）変数です。
さて、トレースを今からしていきますが、
現在どのセル番号ｇの世界にいるのかを常に明確に意識しながら、
以下をお読みください。
現在どのセルにいるのかをはっきり掴んでいないと、
トレースが理解できなくなります。
現在いるセル（現在アクティブなセル）を

で表すことにします。



また、ｎ＝３の場合
でトレースしていることも念頭においてください。
　　f (0)
ではじめて、世界

が生成します。
というのは、関数は呼び出されたときのみ、
コンピュータのメモリ上に生じるからです。
　　 for(i=1;i<n+1;i++){
　　　　　x[g]=i;
最初にｉに１が入ります。

　　　　　if(g>0){
　　　　　　　 for(j=0;j<g;j++){
　　　　　　　　　　if(x[g]==x[j])goto tobi;
　　　　　　　 }
　　　　　}
g = 0ですから、Ｉｆ文は実行されませんから
tobiへの跳躍は行われず、
　　　　　if(g+1<n){
　　　　　　　 f(g+1);
　　　　　}
　　　　　else{
　　　　　　　 h();
　　　　　　　 cn++;
　　　　　}
実行されます。g = 0ですから、
g + 1 < nは 0+ 1 < nすなわち1 < 3 で成り立ちますので、
　　　　　　　 f(g+1);
の命令が遂行されます。
g = 0ですので、f (g + 1)はf (1)です。
したがって、f (0)がf (1)を呼び出しました。
その結果、２番目の世界（セル番号１の世界）

が発生します。
　　 for(i=1;i<n+1;i++){
　　　　　x[g]=i;
によって、

となります。g = 1ですから、
　　 for(i=1;i<n+1;i++){
　　　　　x[g]=i;
　　　　　if(g>0){
　　　　　　　 for(j=0;j<g;j++){
　　　　　　　　　　if(x[g]==x[j])goto tobi;
　　　　　　　 }
　　　　　}
のIf文が実施され、j = 0のとき、
x[g] = x[j] は x[1] = x[0] となるためにgoto tobi;
（セル番号１の世界にいるからですよ。）
が行われために
　　　　　if(g+1<n){
　　　　　　　 f(g+1);
　　　　　}
　　　　　else{
　　　　　　　 h();
　　　　　　　 cn++;
　　　　　}
は遂行されません。したがって、for文は次ぎに進みｉ＝２となり、

今度はｊ＝０のとき、x[1]≠x[0]なので、goto tobi;は行われず、
　　　　　if(g+1<n){
　　　　　　　 f(g+1);
　　　　　}
　　　　　else{
　　　　　　　 h();
　　　　　　　 cn++;
　　　　　}
が実行されます。g = 1ですから、g + 1 < n は　1 + 1 < 3で真ですから、
　　　　　　　　f (g + 1)すなわちf (2)
の命令が遂行されます。すなわち、f (1)がf (2)を呼び出し、

３番目の世界（ｇ＝２の世界）が誕生します。
　　　　　if(g+1<n){
　　　　　　　 f(g+1);
　　　　　}
　　　　　else{
　　　　　　　 h();
　　　　　　　 cn++;
　　　　　}
によって、ｉ＝1が入り、

となります。
　　　　　if(g>0){
　　　　　　　 for(j=0;j<g;j++){
　　　　　　　　　　if(x[g]==x[j])goto tobi;
　　　　　　　 }
　　　　　}
は1回目のループすなわちj = 0のとき、
x[g] = x[j] は　x[2] = x[0]となりますからgoto tobi;によって、
　　　　　if(g+1<n){
　　　　　　　 f(g+1);
　　　　　}
　　　　　else{
　　　　　　　 h();
　　　　　　　 cn++;
　　　　　}
は遂行されず、for文は進みi=2となり、

となります。
　　　　　if(g>0){
　　　　　　　 for(j=0;j<g;j++){
　　　　　　　　　　if(x[g]==x[j])goto tobi;
　　　　　　　 }
　　　　　}
今回は、2回目のループすなわちｊ＝１のとき、x[g] = x[j]　は　x[2] = x[1]となり、
　　　　　if(g+1<n){
　　　　　　　 f(g+1);
　　　　　}
　　　　　else{
　　　　　　　 h();
　　　　　　　 cn++;
　　　　　}
は実施にいたらず、for文は最後に進み、

となります。x[2]≠x[0]、x[2]≠x[1]なので、はじめて
　　　　　if(g>0){
　　　　　　　 for(j=0;j<g;j++){
　　　　　　　　　　if(x[g]==x[j])goto tobi;
　　　　　　　 }
　　　　　}
のチェックをクリアして、
　　　　　if(g+1<n){
　　　　　　　 f(g+1);
　　　　　}
　　　　　else{
　　　　　　　 h();
　　　　　　　 cn++;
　　　　　}
が実行されるわけですが、g = 2 ですから
g + 1 < n　は 2 + 1 < 3で成り立ちませんので、
elseの部分が実行され
f (2)ははじめて自分だけに
与えられている核ボタンを押す権限＝表示関数h()呼び出す権限
　　　　　else{
　　　　　　　 h();
　　　　　　　 cn++;
　　　　　}
を遂行して、

シートに1個目の順列を表示させることに成功します。

本日のトレースはここまで。これ以降のトレースは次話で。

第４話へ　第６話へ




魔方陣 数独で学ぶ VBA 入門
数独のシンプルな解き方・簡単な解法の研究
VB講義へ
ＶＢ講義基礎へ
初心者のための世界で一番わかりやすいVisual C++入門基礎講座
初心者のための世界で一番わかりやすいVisual Basic入門基礎講座
初心者のための世界で一番わかりやすいVBA入門講義（基礎から応用まで）
初心者のための VC++による C言語 C++ 入門 基礎から応用まで第１部
eclipse java 入門
java 入門 サイト 基礎から応用まで
VC++ C言語 C++ 入門 初心者 基礎から応用まで
本サイトトップへ