n回曲がる最短経路問題・考察(1)を示します。
(考察1)
n×nの格子状の道路がある町を考える。交差点Aから交差点Bまで、最短経路で移動する。ただし、交差点間の距離は同じとする。
n=1,2,…,9について、k回曲がる経路数を求めた。
●プログラム(CB111.bas)
' << CB111.bas >> ' n×nの格子状の道路がある町 ' Public COUNT(99): ' COUNT(I):I(1≦I≦2n-1)回曲がる ' 最短経路の個数。 Public N: ' nの値。 Public C(99): ' 組合せを保存する配列。 ' Do ' Nの読み込み。 Read N If N <= 0 Then EXit Do ' ' 初期設定。 For I=1 To 2*N-1: COUNT(I)=0: Next I ' ' 組合せの生成。 Call Comb(1) ' ' 結果の表示。 Print Using"##×##の格子状の道路";N;N Print"曲がる回数 経路数" For I=1 To 2*N-1 Print Using" #### ######";I;COUNT(I) Next I Print Loop End ' ' 2n個からn個取りだす組合せ生成プログラム。 Sub Comb(K) If K > 2*N Then T=0 For J=1 To 2*N: T=T+C(J): Next J If T = N Then S=0 For J=2 To 2*N If C(J-1) <> C(J) Then S=S+1 Next J COUNT(S)=COUNT(S)+1 End If Else C(K)=0: Call Comb(K+1) C(K)=1: Call Comb(K+1) End If End Sub ' ' データ。 Data 2, 3, 4, 5, 0
実行結果
2× 2の格子状の道路
曲がる回数 経路数
1 2
2 2
3 2
3× 3の格子状の道路
曲がる回数 経路数
1 2
2 4
3 8
4 4
5 2
4× 4の格子状の道路
曲がる回数 経路数
1 2
2 6
3 18
4 18
5 18
6 6
7 2
5× 5の格子状の道路
曲がる回数 経路数
1 2
2 8
3 32
4 48
5 72
6 48
7 32
8 8
9 2
OK