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

解説

これでf (2)の３回目の生は終わりを告げ、消滅しf (1)へと戻ります。

そして、for文の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++;
　　　　　}
無視されますから、for文の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++;
　　　　　}
命令が実施され、f (2)の４回目の発生となります。

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

3つともセルの内容が違いますので、
試験
　　　　　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++;
　　　　　}
の否定側の
　　　　　else{
　　　　　　　 h();
　　　　　　　 cn++;
　　　　　}
の命令が遂行され、4個目の順列
をコンソールにはき出します。
for文のi++により、

となりますが、これは1番目のセルと３番目のセルが同じなので、
検査
　　　　　if(g>0){
　　　　　　　 for(j=0;j<g;j++){
　　　　　　　　　　if(x[g]==x[j])goto tobi;
　　　　　　　 }
　　　　　}
に抵触して、

となります。
今度は、２番目のセルと３番目のセルの内容が同じなので、やはり
　　　　　if(g>0){
　　　　　　　 for(j=0;j<g;j++){
　　　　　　　　　　if(x[g]==x[j])goto tobi;
　　　　　　　 }
　　　　　}
の試験をクリアできません。
これで、f (2)の４回目の生が寿命を迎え、消滅します。

そして、セル番号１の世界も天寿を全うし、
２度目の消滅を体験します。

for文の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++;
　　　　　}
の肯定側
　　　　　if(g+1<n){
　　　　　　　 f(g+1);
　　　　　}
が実行されf (1)の３度目の誕生を迎えます。

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

これは、2つのセルに内容が違いますので、
　　　　　if(g+1<n){
　　　　　　　 f(g+1);
　　　　　}
　　　　　else{
　　　　　　　 h();
　　　　　　　 cn++;
　　　　　}
の肯定部分が遂行され、f (2)の５度目の生誕となります。

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

と変化していって、はじめて３つのセルの内容がすべて異なり、
　　　　　if(g+1<n){
　　　　　　　 f(g+1);
　　　　　}
　　　　　else{
　　　　　　　 h();
　　　　　　　 cn++;
　　　　　}
の否定部分の命令が遂行され５個目の順列
がコンソールに出力されます。
以下、

セル番号２の世界の５度目の消滅。

と変化していき、６個目の順列
がコンソールに打ち出されます。

セル番号２の世界の６度目の消滅。

セル番号１の世界の３度目の消滅。

セル番号０の世界のはじめての消滅を迎え、
プログラムはf (0)を呼び出してから
はじめてPrivate Sub CommandButton1_Clickに戻り、
自分の任務をすべて完遂し終焉を迎えます。
プログラムは、消滅しましたが、コンソールには結果
が燦然と輝いています。

最後の方、叙述を簡単にしましたが、
簡略にした部分を皆さんが補ってください。
詳しい記述を延々と繰り返したのでは、
逆に読む気力が失せると考え、簡単にしました。

ｎ＝３を選んだ理由はお分かりですね。
ｎ＝２ではトレースとして簡単すぎます。
しかし、ｎ＝４では、私も書く気になれませんし、
読む皆さんもウンザリですよね。

みなさん、ｎ＝４のトレースは大変ですが、
頭の中でやってみてください。
コンピュータの動きを追うことはとても大切なことです。

では、ｎ次順列生成
#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[30][30],n;
long cn;
はグローバル配列およびグローバル変数にしておきましょう。
第８講で作った方式では、
４次が限界ですが、
将来は改良して３０次魔方陣までも作成可能にしますので、
配列は大きめにx[30][30]にしてあります。

ｎ次魔方陣の行などの合計は
ｎ＊（ｎ＊ｎ＋１）／２
で計算できます。
なぜなら
（１＋２＋３＋・・・＋ｎ＊ｎ）÷ｎ
＝ｎ＊ｎ（ｎ＊ｎ＋１）／２÷ｎ
＝ｎ＊（ｎ＊ｎ＋１）／２
です。
さあ、汎用的魔方陣自動生成ソフトに挑戦しましょう！


第６話へ　第８話へ




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