排序網路(sorting network)問題 uva1117

uva sorting

white95129 2022-07-08 22:47:05 ‧ 1359 瀏覽

分享至

近日刷uva題時遇到了一題有關排序網路的問題，由於對我而言是未知的概念便做了一番研究，但多次查詢後卻發現網上有關此的程式資料較少，多半是理論和複雜的學術證明，而題目大意是這樣的:

有一個比較函式(CE)，CE(a,b)，若a>b則a、b值互換。現有n個暫存器，第一個輸入的正整數為測資數，接著輸入兩個整數n,m，n代表有幾個暫存器(r1,r2...rn)，m代表指令數(函式執行數)，接下來輸入m * 2個整數，兩兩一組，代表要執行CE的暫存器，且這兩個數為連續整數(1 2,2 3,3 4)。求最少需要再加幾個指令，才能使整套指令在移除任意一個指令後其r1仍為目標暫存器中最小值。

這題是uva1117 - reliable program，可能我對題意有錯誤理解也說不定，目前我沒有在網上見過這題的討論或是程式碼，該題在udebug中也沒有任何範例測資，我是有想過雙調排序等可能性，但始終覺得我的想法難以實現或效率太低恐超時，希望有大神給個建議或概念，指點迷津。