第９講 関数の再帰的使用
第６話 関数の再帰的使用によるｎ次順列生成解説その３
コード再掲
#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;
}
b

解説

 ０ １ ２
1 2 3

1個目の順列の作成表示に成功すると、f (2]は寿命を終えて、消滅し

 ０ １
1 2

となります。f (1)のfor文のi++によって、

 ０ １
1 3

となります。x[1]≠x[0]なので、チェック
　　　　　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 + 1 < n  は　1 + 1 < 3
で成り立ち、
　　　　　　　　f (g + 1)
が呼び出され、セル番号２の世界の2回目の生誕となります。

 ０ １ ２
1 3 ｉ

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

 ０ １ ２
1 3 1

となります。残念ながら、x[2] = x[0] ですから
　　　　　if(g>0){
　　　　　　　 for(j=0;j<g;j++){
　　　　　　　　　　if(x[g]==x[j])goto tobi;
　　　　　　　 }
　　　　　}
の1回目のループにおいてgoto tobi;によって
　　　　　if(g+1<n){
　　　　　　　 f(g+1);
　　　　　}
　　　　　else{
　　　　　　　 h();
　　　　　　　 cn++;
　　　　　}
を飛び越し、f (2)のfor文のi++により、

 ０ １ ２
1 3 2

となります。x[2]≠x[0]、x[2]≠x[1]なので、
　　　　　if(g>0){
　　　　　　　 for(j=0;j<g;j++){
　　　　　　　　　　if(x[g]==x[j])goto tobi;
　　　　　　　 }
　　　　　}
において2回とも跳躍はされず、
　　　　if(g+1<n){
　　　　　　　 f(g+1);
　　　　　}
　　　　　else{
　　　　　　　 h();
　　　　　　　 cn++;
　　　　　}
の実行となりますが、ｇ＝２ですから g + 1 < n　は　 2 + 1 < 3　で成り立ちませんので
　　　　　else{
　　　　　　　 h();
　　　　　　　 cn++;
　　　　　}
が実行され、２個目の順列c
が表示されることになります。
そして、for文のi++によって

 ０ １ ２
1 3 3

となりますが、x[2] = x[1]で
　　　　　if(g>0){
　　　　　　　 for(j=0;j<g;j++){
　　　　　　　　　　if(x[g]==x[j])goto tobi;
　　　　　　　 }
　　　　　}
のｊ＝１のとき、goto tobi;によって
　　　　if(g+1<n){
　　　　　　　 f(g+1);
　　　　　}
　　　　　else{
　　　　　　　 h();
　　　　　　　 cn++;
　　　　　}
が無視され、
f (2)のすべての処理が終わり、
２回目のf (2)の消滅となります。

 ０ １
1 3

そして、f (1)も任務が終了して、消滅します。

 ０
1

for文のi++によって、

 ０
2

となりますが、ｇ＝０なので、
　　　　　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++;
　　　　　}
の肯定の方が実施され、セル番号１の世界の２回目の誕生となります。

 ０ １
2 ｉ

となります。
　　 for(ｉ=1;ｉ<n+1;ｉ++){
　　　　　x[g]=ｉ;
によって、

 ０ １
2 1

となります。x[1]≠x[0]で、チェック
　　　　　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++;
　　　　　}
の肯定の側が遂行され、セル番号２の世界の３回目の生成となります。

 ０ １ ２
2 1 ｉ

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

 ０ １ ２
2 1 1

となります。 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++;
　　　　　}
は実施されず、for文のi++によって

 ０ １ ２
2 1 2

今度は、 x[2] = x[0]で
　　　　　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++;
　　　　　}
は実行されず、for文のi++によって

 ０ １ ２
2 1 3

x[2]≠x[0]、x[2]≠x[1]なので３度目の正直で
　　　　　if(g>0){
　　　　　　　 for(j=0;j<g;j++){
　　　　　　　　　　if(x[g]==x[j])goto tobi;
　　　　　　　 }
　　　　　}
のチェックをクリアして
　　　　　else{
　　　　　　　 h();
　　　　　　　 cn++;
　　　　　}
の命令が行われ、３個目の順列d
が表示されます。

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





第５話へ　第７話へ


a

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