第９講 プロシージャの再帰的使用
第10話 トレースによる解説
コード主要部分例
Sub f(g As Integer)
Dim i, j, h As Integer
For i = 0 To n - 1
If g = 0 Then x(g) = i + 1
h = 1
If g > 0 Then
For j = 0 To g - 1
If x(j) = i + 1 Then
h = 0
Exit For
End If
Next
If h = 1 Then x(g) = i + 1
End If
If h = 1 Then
If g + 1 < n Then
f (g + 1)
Else
cn += 1
For j = 0 To n - 1
Console.Write("{0:d} ", x(j))
Next
Console.WriteLine()
End If
End If
Next
End Sub
End Module
この難解なプログラムを解説していきましょう。
テーマ名に、聞いたことのない言葉が登場しています。
トレースとは、コンピュータの動きを一つ一つ追うことです。
３次順列生成でトレースすると、
後５話ぐらい必要になりますし、
煩雑すぎますので、２次順列生成をトレースして、
３次や４次の場合は皆さん自身にやっていただくことにします。
かなり面倒ですが、トレースは大変大切ですから、
必ずやって下さい。
２次順列生成ですから、n=2が以下のトレースの前提となります。
Main()からf(0)でプロシージャf()に仕事が依頼されますから、最初gは0です。
以下
For i = 0 To n - 1
・
Next
の動きを追います。
i=0の場合、
If g = 0 Then x(g) = i + 1
は
If g = 0 Then x(0) = i + 1
ですから、if文の条件が満たされ、x(0) = 0+1が実行されてx(0)は1となります。
次の
h = 1
If g > 0 Then
For j = 0 To g - 1
If x(j) = i + 1 Then
h = 0
Exit For
End If
Next
If h = 1 Then x(g) = i + 1
End If
青はgが0ですから実行されません。
すると、hは1のままですから、
If h = 1 Then
If g + 1 < n Then
f (g + 1)
Else
cn += 1
For j = 0 To n - 1
Console.Write("{0:d} ", x(j))
Next
Console.WriteLine()
End If
End If
すなわち、
If h = 1 Then
If 0 + 1 < n Then
f (0 + 1)
Else
cn += 1
For j = 0 To n - 1
Console.Write("{0:d} ", x(j))
Next
Console.WriteLine()
End If
End If
の肯定部分が実施されて、
f(0)は、自分の分身f(1)を呼び出します。
このとき、gは1になっています。
For i = 0 To n - 1
If g = 0 Then x(g) = i + 1
ですから、青は無視されて、
h = 1
If g > 0 Then
For j = 0 To g - 1
If x(j) = i + 1 Then
h = 0
Exit For
End If
Next
If h = 1 Then x(g) = i + 1
End If
へと進みますが、g=1なので、
ピンクが実行されます。
j=0のとき、
For j = 0 To g - 1
If x(j) = i + 1 Then
h = 0
Exit For
End If
Next
If h = 1 Then x(g) = i + 1
End If
If h = 1 Then
If g + 1 < n Then
f (g + 1)
Else
cn += 1
For j = 0 To n - 1
Console.Write("{0:d} ", x(j))
Next
Console.WriteLine()
End If
End If
x(0)は1ですから
h = 0
Exit For
実行されてしまいます。
こでExit Forは強制的にFor文（繰り返し処理＝ループ処理）をやめさせるものですが、
g=1の時には、Exit Forは意味のない文となります。
強制的にやめさせなくてもFor文は終了してしまうからです。
Exit Forが生きるのはg>1のときです。
さて、hが0となり、ピンクが実行されずに、jが1つ進み、
i=1の場合となります。
If g = 0 Then x(g) = i + 1
は
If g = 0 Then x(0) = i + 1
ですから実行されずに、
h = 1
If g > 0 Then
For j = 0 To g - 1
If x(j) = i + 1 Then
h = 0
Exit For
End If
Next
If h = 1 Then x(g) = i + 1
End If
すなわち
h = 1
If 1 > 0 Then
For j = 0 To 1 - 1
If x(j) = 1 + 1 Then
h = 0
Exit For
End If
Next
If h = 1 Then x(1) = 1 + 1
End If
へと進みます。
j=0のとき、
h = 1
If 1 > 0 Then
For j = 0 To 1 - 1
If x(0) = 1 + 1 Then
h = 0
Exit For
End If
Next
If h = 1 Then x(1) = 1 + 1
End If
のx(0)=1+1はx(0)が1なので成り立たずに、
hは1のままで、
If h = 1 Then x(1) = 1 + 1
が実行されx(1)=2となり、
If h = 1 Then
If g + 1 < n Then
f (g + 1)
Else
cn += 1
For j = 0 To n - 1
Console.Write("{0:d} ", x(j))
Next
Console.WriteLine()
End If
End If
の青が実行されて、はじめてコンソール画面に
12
が打ち出されます。
ごめんなさい。２次に限定しても煩雑すぎます。
以下はご自分でトレースを行って、実行画面が
12
21
となることを確認して下さい。
さて、ｎ×ｎ次順列を２次元に並び直して、
すべての横合計・縦合計・対角線合計が同じになるものを見いだして、
ｎ次魔方陣を生成するというソフトの開発に取り組みます。
このソフトによって、
対称変換をすると重なるものや鏡像を別のものとして数えると
３次魔方陣は８個、４次魔方陣は７０４０個の答えを持っていることを、
確認されます。
理論的には何次魔方陣で作れるソフトですが、
現時点では４次が限界ですし、７０４０個作り出すにも２０分ぐらい必要としますが、
本講義の進展と共に作成スピードは数万倍→数億倍→数兆倍→数京倍となり、
２６次魔方陣クラスでも１秒で数百の勢いで生成するようになっていきます。
第10講第1話の課題を出します。
なるべくシンプルになるように、
Dim cn, x(25), n As Integer
とグローバル配列を1つとグローバル変数を２つ用意してしまいましたが、
いずれも引数にすれば、
グローバル変数はすべて追放してローカル変数にすることが出来ます。
f()のMain()とf()からの呼び出しはf(0,n,x,cn)
（順番は任意ですが、Main()とf()からの呼び出しは同じ順に
さらに、Sub f(g As Integer, n As Integer, x() As Integer, cn() As Integer)と()内も同じ順に、
そろえなければなりません。）
という形になります。
ただし、xに加えてcnも配列にしておくと良いでしょう。
Dim cn(0),x(25) As Integer
cnを配列とすることによって、値ではなく箱（変数）そのものを実質送ったのと同じになりましたね。
もっとも、f()をFunctionプロシージャにして、cnの値を返させる方法もありますが、
こちらの方がやや複雑になります。
でも、好きな方を採用して下さい。
グローバル変数（プログラム全体で有効な変数）は使わずに、
ローカル変数（プロシージャ内のみで有効な変数）のみでプログラムを組むが、
プログラミングの原則です。
