知恵袋で見つけた最短経路の問題をPythonで解いてみました。(^_^;
図において、AからBにいたる最短経路を求めるものは全部で何通りあるか。
+-+-+-+-+-+-B
| | | | | | |
+-+-+-+-+-+-+
| | | | | | |
+-+-+-+-+-+-+
| | | | | | |
+-+-+-+-P-+-+-+-+-+-+
| | | | | | | | | | |
+-+-+-+-+-Q-+-+-+-+-+
| | | | | | | | | | |
+-+-+-+-+-+-R-+-+-+-+
| | | | | | |
+-+-+-+-+-+-+
| | | | | | |
+-+-+-+-+-+-+
| | | | | | |
A-+-+-+-+-+-+ 拙ブログの「最短経路の場合の数の問題をJavaで解いてみた。」を参考にして作りました。(^_^;
ちなみに、自力で解くときは、逐次足し算でやるのは、大変そうです。(^_^;
Pを通る場合、Qを通る場合、Rを通る場合に場合分けして、
9Ｃ5×9Ｃ3＋9Ｃ4×9Ｃ4＋9Ｃ3×9Ｃ5＝37044[通り]
>>> from scipy.special import comb >>> comb(9,5)*comb(9,3)+comb(9,4)*comb(9,4)+comb(9,3)*comb(9,5) 37044.0
● NumOfShortestPath1.py
# coding: UTF-8 # NumOfShortestPath1.py from time import time sMap = [ " +-+-+-+-+-+-B", " | | | | | | |", " +-+-+-+-+-+-+", " | | | | | | |", " +-+-+-+-+-+-+", " | | | | | | |", " +-+-+-+-P-+-+-+-+-+-+", " | | | | | | | | | | |", " +-+-+-+-+-Q-+-+-+-+-+", " | | | | | | | | | | |", " +-+-+-+-+-+-R-+-+-+-+", " | | | | | | | ", " +-+-+-+-+-+-+ ", " | | | | | | | ", " +-+-+-+-+-+-+ ", " | | | | | | | ", " A-+-+-+-+-+-+ ", " ", ] def main(): tm = time() # Timer Start m,n = len(sMap),len(sMap[0]) iMap = [[0 for i in range(n)] for j in range(m)] ## print(m,n); print(iMap) # s／g型のsMapからs＼g型のiMapを作成 for i in range(m): for j in range(n): if sMap[i][j] in '|-': iMap[m-1-i][j] = 1 ## print(iMap) # 逐次足し算 iMap[1][1] = 1 # 和の初期値。StartのAだけ1、他の点は0 for i in range(1,m,2): for j in range(1,n,2): if iMap[i][j-1]==1: iMap[i][j]+=iMap[i][j-2] if iMap[i-1][j]==1: iMap[i][j]+=iMap[i-2][j] # 結果の表示 for i in reversed(range(1,m,2)): for j in range(1,n,2): print("%6d"%iMap[i][j],end='') print() print() print("∴%d"%iMap[m-1][n-1]) print("Runtime : %.3f [sec]"%(time()-tm)) # Timer Stop & Disp if __name__ == '__main__': main()
●実行結果
0 0 0 0 126 630 1974 4914 10584 20580 37044
0 0 0 0 126 504 1344 2940 5670 9996 16464
0 0 0 0 126 378 840 1596 2730 4326 6468
1 6 21 56 126 252 462 756 1134 1596 2142
1 5 15 35 70 126 210 294 378 462 546
1 4 10 20 35 56 84 84 84 84 84
1 3 6 10 15 21 28 0 0 0 0
1 2 3 4 5 6 7 0 0 0 0
1 1 1 1 1 1 1 0 0 0 0
∴37044
Runtime : 0.003 [sec]※参考URL
●最短経路の場合の数の問題をJavaで解いてみた。 - rscのブログ
●立体の最短経路の場合の数の問題をJavaで解いてみた。 - rscのブログ
●立体の最短経路の場合の数の問題をJavaで解いてみた。(2) - rscのブログ
●知恵袋で見つけた場合の数の道順問題をPythonで解いてみた。 - rscのブログ
