知恵袋で見つけた場合の数の道順問題をPythonで解いてみました。(^_^;
図のような道路がある町において、道路を進む際、進むことのできる道路の方向が東方向、北方向および北東方向の3方向に限られているとき、図のA地点からB地点を経由してC地点へ行く道順は何通りあるか。
(1) 65通り (2) 78通り (3) 84通り (4) 91通り (5) 98通り
+-+-+-C N |/|/|/| /| +-+-+-+ *-+-- |/|/|/| | +-+-+-+ | |/|/|/| +-+-B-+ |/|/|/| +-+-+-+ |/|/|/| A-+-+-+
最短なら斜め(/)をできるだけ多く通った方がいいから、最短経路とはちょっと違うけど、拙ブログの「最短経路の場合の数の問題をJavaで解いてみた。」を参考にして作りました。(^_^;
ちなみに、自分で解く場合は、拙プログラムのように、逐次足し算でやる方法と、斜め(/)を通る回数(0,1,2)で場合分けする方法があります。
● NumOfPath1.py
# coding: UTF-8 # NumOfPath1.py from time import time sMap = [ " +-C", " |/|", " +-+", " |/|", " +-+", " |/|", " +-+-B-+", " |/|/| ", " +-+-+ ", " |/|/| ", " 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 ] if iMap[i-1][j-1]==1: iMap[i][j]+=iMap[i-2][j-2] # 結果の表示 for i in reversed(range(1,m,2)): for j in range(1,n,2): print("%4d"%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 13 91 0 0 13 65 0 0 13 39 1 5 13 13 1 3 5 0 1 1 1 0 ∴91 Runtime : 0.001 [sec]
※参考URL
●道順が何通りあるか考える問題について質問です。 - 碁盤のマスの... - Yahoo!知恵袋
●高校数学【場合の数と確率】〈最短経路の数〉図(一番下の画像)の... - Yahoo!知恵袋
●最短経路の場合の数の問題をJavaで解いてみた。 - rscのブログ
●立体の最短経路の場合の数の問題をJavaで解いてみた。 - rscのブログ
●立体の最短経路の場合の数の問題をJavaで解いてみた。(2) - rscのブログ
