第９講 関数の再帰的使用
第10話 トレースによる解説
コード主要部分例
void f(int g){
int i,j,h;
for(i=0;i<n;i++){
if(g==0)x[g]=i+1;
h=1;
if(g>0){
for(j=0;j<g;j++){
if(x[j]==i+1){
h=0;
break;
}
}
if(h==1)x[g]=i+1;
}
if(h==1){
if (g+1 < n){
f(g+1);
}
else{
for(j=0;j<n;j++)cout << x[j] << " ";
cout << endl;
cn++;
}
}
}
}
この難解なプログラムを解説していきましょう。
テーマ名に、聞いたことのない言葉が登場しています。
トレースとは、コンピュータの動きを一つ一つ追うことです。
３次順列生成でトレースすると、
後５話ぐらい必要になりますし、
煩雑すぎますので、２次順列生成をトレースして、
３次や４次の場合は皆さん自身にやっていただくことにします。
かなり面倒ですが、トレースは大変大切ですから、
必ずやって下さい。
３次順列生成ですから、n=2が以下のトレースの前提となります。
main()からf(0)で関数f()に仕事が依頼されますから、最初gは0です。
以下
for(i=0;i<n;i++){
・
}
の動きを追います。
i=0の場合、
if(g==0)x[g]=i+1;
は
if(0==0)x[0]=0+1;
ですから、if文の条件が満たされ、x[0]=0+1が実行されてx[0]は1となります。
次の
h=1;
if(g>0){
for(j=0;j<g;j++){
if(x[j]==i+1){
h=0;
break;
}
}
if(h==1)x[g]=i+1;
}
青はgが0ですから実行されません。
すると、hは1のままですから、
if(h==1){
if (g+1 < n){
f(g+1);
}
else{
for(j=0;j<n;j++)cout << x[j] << " ";
cout << endl;
cn++;
}
}
すなわち、
if(h==1){
if (0+1 < n){
f(0+1);
}
else{
for(j=0;j<n;j++)cout << x[j] << " ";
cout << endl;
cn++;
}
}
の肯定部分が実施されて、
f(0)は、自分の分身f(1)を呼び出します。
このとき、gは1になっています。
for(i=0;i<n;i++){
if(g==0)x[g]=i+1;
ですから、青は無視されて、
h=1;
if(g>0){
for(j=0;j<g;j++){
if(x[j]==i+1){
h=0;
break;
}
}
if(h==1)x[g]=i+1;
}
へと進みますが、g=1なので、
ピンクが実行されます。
j=0のとき、
for(j=0;j<1;j++){
if(x[0]==0+1){
h=0;
break;
}
}
if(h==1)x[g]=i+1;
}
if(h==1){
if (g+1 < n){
f(g+1);
}
else{
for(j=0;j<n;j++)cout << x[j] << " ";
cout << endl;
cn++;
}
}
x[0]は1ですから
h=0;
break;
が実行されてしまいます。
ここでbreak;は強制的にfor文（繰り返し処理＝ループ処理）をやめさせるものですが、
g=1の時には、break;は意味のない文となります。
強制的にやめさせなくてもfor文は終了してしまうからです。
break;が生きるのはg>1のときです。
さて、hが0となり、ピンクが実行されずに、iが1つ進み、
i=1の場合となります。
if(g==0)x[g]=i+1;
は
if(1==0)x[1]=1+1;
ですから実行されずに、
h=1;
if(g>0){
for(j=0;j<g;j++){
if(x[j]==i+1){
h=0;
break;
}
}
if(h==1)x[g]=i+1;
}
すなわち
h=1;
if(g>0){
for(j=0;j<g;j++){
if(x[j]==i+1){
h=0;
break;
}
}
if(h==1)x[g]=i+1;
}
へと進みます。
j=0のとき、
h=1;
if(g>0){
for(j=0;j<g;j++){
if(x[0]==1+1){
h=0;
break;
}
}
if(h==1)x[g]=i+1;
}
のx[0]==1+1はx[0]が1なので成り立たずに、
hは1のままで、
if(h==1)x[g]=i+1;
が実行されx[1]=2となり、
if(h==1){
if (g+1 < n){
f(g+1);
}
else{
for(j=0;j<n;j++)cout << x[j] << " ";
cout << endl;
cn++;
}
}
の青が実行されて、はじめてコンソール画面に
12
が打ち出されます。
ごめんなさい。２次に限定しても煩雑すぎます。
以下はご自分でトレースを行って、実行画面が
12
21
となることを確認して下さい。
さて、ｎ×ｎ次順列を２次元に並び直して、
すべての横合計・縦合計・対角線合計が同じになるものを見いだして、
ｎ次魔方陣を生成するというソフトの開発に取り組みます。
このソフトによって、
対称変換をすると重なるものや鏡像を別のものとして数えると
３次魔方陣は８個、４次魔方陣は７０４０個の答えを持っていることを、
確認されます。
理論的には何次魔方陣で作れるソフトですが、
現時点では４次が限界ですし、７０４０個作り出すにも２０分ぐらい必要としますが、
本講義の進展と共に作成スピードは数万倍→数億倍→数兆倍→数京倍となり、
２６次魔方陣クラスでも１秒で数百の勢いで生成するようになっていきます。
第10講第1話の課題を出します。
なるべくシンプルになるように、
int x[20];
int n,cn;
とグローバル配列を1つとグローバル変数を２つ用意してしまいましたが、
いずれも引数にすれば、
グローバル変数はすべて追放してローカル変数にすることが出来ます。
ただし、cnはポインタで宣言して
int x[25],n,*cn;
としておいた方がよいでしょう。
f()のmain()とf()からの呼び出しはf(0,n,x,cn);
（順番は任意ですが、main()とf()からの呼び出しは同じ順に、
さらにvoid f(int g,int n,int x[],int *cn)の()内も同じ順に、
そろえなければなりません。）
という形になります。
もっともf()をint型に変更すれば、
int x[25],n,cn;
でも可です。
好きな方を採用しましょう。
ただし、*cnを採用する場合
*cn++; ではだめです。
(*cn)++;
しなければなりません。
*cn++; だと*(cn++);
と解釈されてしまうからです。
C言語の文法では*とcnと++あるときに、
cnと++のつながりを優先することになっているからです。
『優先？』でしょうが、
２＋３×４
のときに計算の原則は左から右なのに×を優先して、＋が次に行われましたね。
もし＋を先にやらせたければ、
（２＋３）×４
としなければなりませんでしたね。
それと同じです。
C言語の文法でも×が優先する等の順番があるのですが、
*cn++; はプログラムにある程度慣れている人でも、
どちらが優先なのか迷うことがあります。
迷うときは、念のために(*cn)++; と()を使ってしまえばよいのです。
本来は、*cn++; は*(cn++); とかく必要はありませんが、
優先順序が怪しい場合には迷わず()を使いましょう。
私も優先順序は未だに記憶が曖昧です。
尚、グローバル変数（プログラム全体で有効な変数）は使わずに、
ローカル変数（関数内のみで有効な変数）のみでプログラムを組むが、
プログラミングの原則です。
そこで、第10講第1話の宿題として、
３つのグローバル変数をすべて追放せよ、
という課題を課すことにします。
