2020/04/14

20200414-邏輯-取得兩條線的交岔節點

(ref from https://t.ly/mZE5p )

緣起

今天上班在找資料時,看到這此Blog的資訊,疑? 來思考看看如何取得”最佳”結果吧。

而這,感覺就像是 區塊鏈 它的演算法, 要回朔它分岔的節點是那兒?? (只是這圖是反著畫)



題目

知道開頭的節點 資訊, 而假設 上下為 A、B 線。 何時可以找到它們共同的節點。

假設 A在 第M個 節點,與B在 第N個 節點 交岔。

另(A總共有A個節點、B總共有B個節點數)


思考 + 我的解法:

在原Link下,提供了”基本”解法:

方法一、A線全捉出來,B線一個個比對; 這最多需要: (A) 的 B 次方( A數+N ) 次  (取出節點次數)



而我的思考邏輯:

(先說這個沒有看網路答案的~~或許有別種解法)

;則 最多需要: MAX(M,N) x2 –1 次的查詢。  (這算是取出節點次數)


做法:

A、B 輪流取一個節點,並將它放入共同的堆疊裡,

而在放入時檢查,是否已存在? (若已存在,即找到共同的第一個節點)

例如: 放B的第N個節點時,發現已存在,則表示,A 中 M的位置 = 大於 (第一個節點 在堆疊中的 位子 X ) / 2 ) 值的 最小整數。


結論:

當   共同點的數量 > MAX(分岔數量) 時,我的做法才有利。

若   共同點的數量 < MAX(分岔數量) 時,則我的不利 (????)


(THE END)

0 意見 :

張貼留言