可能路徑數

-3

爲什麼在下圖中有從S到T的2^k個可能路徑。任何人都可以解釋。注意：圖中所有方向都是從左到右。可能路徑數

enter image description here

來源

2017-04-01 jitendra kumhar

這是如何編程題？ – Mureinik

這是幹什麼用的？如果是作業，請標記爲這樣。考慮每個節點可能採用的路徑數量。單個節點的添加對可能的路徑數量有什麼影響？ – chessofnerd

我投票結束這個問題作爲題外話，因爲它不是一個編程問題，並且提問者沒有顯示他自己的工作。 –

每對並行的路徑，你只能在一個時間選擇其中一個。
所以有這樣的平行路徑對。
因此，組合的總數是：2 * 2 * 2 ...... k倍= 2^ķ

來源

2017-04-01 14:33:19

在計數配置，有時有助於找到一種方法來編碼的配置，然後計算可能的代碼。只要在編碼的對象和代碼之間存在1-1對應關係，這就起作用。

在這種情況下，您可以在每個階段採用頂部分支或底部分支。如果相應路徑在該階段採用頂部分支，否則爲1，那麼通過在給定位位置處使用0來將路徑編碼爲k位二進制數。這顯然是1-1對應關係，因此這種路徑的數量是k比特數的數量是2^k（計算k比特數的數量本質上是相同的問題，所以這不完全是一個證明，但是如果你已經熟悉k比特數是如何工作的，這可以闡明路徑問題）。

例如（具有k = 4）：

path code num 
vvvv 0000 0 
vvv^ 0001 1 
vv^v 0010 2 
vv^^ 0011 3 
v^vv 0100 4 
v^v^ 0101 5 
v^^v 0110 6 
v^^^ 0111 7 
^vvv 1000 8 
^vv^ 1001 9 
^v^v 1010 10 
^v^^ 1011 11 
^^vv 1100 12 
^^v^ 1101 13 
^^^v 1110 14 
^^^^ 1111 15

（由下面的Python 3腳本生成的，如果你要玩它:)

def pathCodes(k): 
    print('path code num') 
    for n in range(2**k): 
     b = bin(n)[2:] 
     b = ('0'*(k-len(b))) + b 
     s = b.replace('0','v') 
     s = s.replace('1','^') 
     print(s,b,n)

來源

2017-04-01 17:22:11

回答

相關問題