第10講 プロシージャの再帰的使用による魔方陣の自動生成
第１話 n次順列自動生成ソフトからグローバル変数を追放する
グローバル配列・変数を追放したソフトコード例
Module Module1
Sub Main() '私は社長だ。
Console.WriteLine ("これはすべての順列を求めるソフトです。")
Console.WriteLine ("何の順列を発生させるのかをnに入力してエンターして下さい。")
Console.Write ("n=")
Dim cn(0), x(25), n As Integer
n = Console.ReadLine()
cn(0) = 0
f(0, n, x, cn)
Console.WriteLine("生成された{0:d}次順列は{1:d}個です。", n, cn(0))
End Sub
Sub f(g As Integer, n As Integer, x() As Integer, cn() 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, n, x, cn)
Else
cn(0) += 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
さて、魔方陣生成ソフト開発に入ります。
せっかく引数にしてグローバル変数をすべて追放しましたが、
シンプルにするためにもとのコード
Module Module1
Dim cn, x(25), n As Integer
Sub Main() '私は社長だ。
Console.WriteLine ("これはすべての順列を求めるソフトです。")
Console.WriteLine ("何の順列を発生させるのかをnに入力してエンターして下さい。")
Console.Write ("n=")
n = Console.ReadLine()
cn = 0
f (0)
Console.WriteLine("生成された{0:d}次順列は{1:d}個です。", n, cn)
End Sub
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
に直して下さい。
引数が多いとf(g)とf(g + 1)の関係が見えにくくなるからです。
入れ子式人形の例えでいうと、
gは外側の人形、g + 1はその内側の人形になります。
最初の課題を出しましょう。
n次順列生成ソフトをn×n次順列生成ソフトに改め、
さらに、実行画面が
これはすべてのn次方陣を求めるソフトです。
何次の方陣を発生させるのかをnに入力し
エンターするとn次方陣がすべて生成されます。
n=2
1 2
3 4
1 2
4 3
1 3
2 4
1 3
4 2
1 4
2 3
1 4
3 2
2 1
3 4
2 1
4 3
2 3
1 4
2 3
4 1
2 4
1 3
2 4
3 1
3 1
2 4
3 1
4 2
3 2
1 4
3 2
4 1
3 4
1 2
3 4
2 1
4 1
2 3
4 1
3 2
4 2
1 3
4 2
3 1
4 3
1 2
4 3
2 1
生成された2次方陣は24個です
となるようにしてください。
1 2
3 4
のように順列を２次元に並べたものを２次方陣と名付けます。
ｎ次順列のｎは正方形の一辺です。
ですから、３次方陣なら
1 2 3
4 5 6
7 8 9
がその一例となります。
尚、
Dim cn, x(25), n As Integer
ですからnの入力限界は5です。
（5は方陣の一辺で、
25はすべての数字の種類数です。
すなわち5×5です。）
もっとも第10講で開発する魔方陣自動生成ソフトでは、
４次魔方陣が限界ですが。
作成速度を１万倍以上にしないと５次には対応できません。
