第１５講 関数の再帰的呼び出しによる順列の作成
第11話 順列作成プログラムの解説７（トレースの最終局面）
コード再掲
#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;
}

２度目の生を受けた一番内側の人形も最終ループを迎えます。

もちろん重複検査をクリアできず、一番内側の人形の命も終了となります。

そして２番人形も初めての生が終わりになり、消滅します。

１番人形の２巡目によって

以下

となり３個目の順列の生成に成功します。

４個目の順列の発見です。

５個目の発見

６個目の発見

こうして一番外側の人形も消滅の時を迎えます。
しかし、３つの人形の協働によって６つの順列がコンソールには輝いています。
最後、mainに戻り
　 　cout<<"順列が"<<cn<<"個できました。"<<endl;
によって

となりmainは任務を遂行することができました。

今話は、トレースを簡略にしてしまいましたが、
賢明なる皆さんのことですからお分かりでしょう。
今回は、複雑になりすぎないように３次を例にしましたが、
５次であろうと８次であろうと同じであることはお分かりでしょう。

for文版順列作成プログラムなら、
次数が変わる度に非常に手間のかかるプログラミングをしなければならないに対して、
関数に自己再帰は簡単なコーティングによって、
理論的には何次でも可能な普遍的なプログラムです。
関数の再帰的呼び出しがいかに優れているかわかります。
さて、皆さん今回作った順列のプログラムを少し改良して魔方陣作成プログラムを考えましょう。
もちろん、理論的には何次魔方陣であっても可能なプログラムを比較的に簡単に組むことができますので、
普遍版魔方陣自動生成プログラムとしましょう。
ただ、現実的には力業ではパーソナルコンピュータの力を持ってしても４次が限界です。
実は、ちょっとした改良を加えるだけで、６次あたりまで作成が可能なプログラムに変更することができます。
さらに、改良を加えていくと２６次魔方陣でさえ、
１秒に数百という単位での作成が可能になります。
今回作っていただく魔方陣作成プログラムの何億倍や何京倍というレベルを遙かに超える超高速プログラムが可能になるのです。

さあ、普遍版魔方陣自動生成プログラムを組んでみましょう！

第１０話へ　第16講第１話へ

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