Form1
第９講 プロシージャの再帰的使用
第３話 順列の作成
Form1
個数がｎ個のときの順列をｎ次順列と呼ぶことにします。
まず、３次順列のコード例は次のようになります。
Public Class Form1
Private Sub Button1_Click(ByVal sender As System.Object, ByVal e As
System.EventArgs) Handles Button1.Click
'変数の宣言と初期化
Dim h1, h2, s As Integer
Dim a(12) As Integer
s = 0
'データグリッドビューのデータのクリア
DataGridView1.Rows.Clear()
'順列の作成
For i = 1 To 3 '１番最初のセル
a(0) = i
For j = 1 To 3 '２番目のセル
a(1) = j
h1 = 1
If a(0) = a(1) Then h1 = 0 '１番目のセルと２番目のセルの重複検査
If h1 = 1 Then
For k = 1 To 3 '３番目のセル
a(2) = k
h2 = 1
For l = 0 To 1 '３番目のセルと１，２番目のセルの重複検査
If a(l) = a(2) Then
h2 = 0
Exit For
End If
Next
If h2 = 1 Then 'DataGridViewへの表示と総数カウント
DataGridView1.Rows.Add() '１行追加
For l = 0 To 2
DataGridView1(l, s).Value = a(l).ToString '順列の表示
Next
s = s + 1 '総数カウント
End If
Next
End If
Next
Next
DataGridView1.Rows.Add() '１行追加
DataGridView1(12, s + 1).Value() = s '総数の表示
End Sub
End Class
実行結果
すでにこのコードを見ただけで、頭が爆発しそうです。
大変難解です。
解説は、次話で詳しく行うとして
４次順列を続けて掲載しましょう。
４次順列
Public Class Form1
Private Sub Button1_Click(ByVal sender As System.Object, ByVal e As
System.EventArgs) Handles Button1.Click
'変数の宣言と初期化
Dim h1, h2, h3, s As Integer
Dim a(12) As Integer
s = 0
'データグリッドビューのデータのクリア
DataGridView1.Rows.Clear()
'順列の作成
For i = 1 To 4 '１番最初のセル
a(0) = i
For j = 1 To 4 '２番目のセル
a(1) = j
h1 = 1
If a(0) = a(1) Then h1 = 0 '１番目のセルと２番目のセルの重複検査
If h1 = 1 Then
For k = 1 To 4 '３番目のセル
a(2) = k
h2 = 1
For l = 0 To 1 '３番目のセルと１，２番目のセルの重複検査
If a(l) = a(2) Then
h2 = 0
Exit For
End If
Next
If h2 = 1 Then
For l = 1 To 4
a(3) = l
h3 = 1
For m = 0 To 2 '４番目のセルと１，２，３番目のセルの重複検査
If a(m) = a(3) Then
h3 = 0
Exit For
End If
Next
If h3 = 1 Then
DataGridView1.Rows.Add( ) '１行追加
For m = 0 To 3
DataGridView1(m, s).Value = a(m) '順列の表示
Next
s = s + 1 '総数カウント
End If
Next
End If
Next
End If
Next
Next
DataGridView1.Rows.Add() '１行追加
DataGridView1(12, s + 1).Value() = s '総数の表示
End Sub
End Class
実行結果
以上から、プロシージャの自己再帰を使わないと５次、６次、７次になる相当困難であることを感じ取っていただければと思います。
プロシージャの自己再帰であれば、たったひとつのプログラミングで一般化が可能です。
つまり、理論的には１００次であろうと１０００００次であろうと計算可能なわけです。
ただ、２０１０年購入時において最高のスペックを誇っていた私のパソコンでも８次おいてすでに１９秒の計算時間がかかりますので、
１００次を計算させるとするとどのぐらいかかるか見当もつきませんが。
というのは概算で、９次なら１９×９＝１７１秒、１０次なら１７１×１０＝１７１０秒と階乗に比例する単位で計算時間が増えていくからです。
ですから現実的でないとはいえますが、理論的には１００次であろうと１０００００次であろうと可能なわけです。
それに対して、For文版の方は一般性がないのでいちいちプログラムコードを書き換えなければなりません。
そして、手間が信じられないほどかかります。
４次順列で５次元ループになりますから、１２次配列ならなんと１３次元ループになってしまいます。
逆に自己再帰型の場合は、コードをいちいち書き換えないで何万次元であろうと理論的には可能なのです。
如何に自己再帰型が優れているかわかります。
VC++講義第１部へ
vb講義へ
ＶＢ講義基礎へ
初心者のための世界で一番わかりやすいVisual C++入門基礎講座
数学研究室に戻る
