改編自:A202 學長的鬼腳圖
學長的鬼腳圖,經過擦擦塗塗修修改改後
竟然也可以排序了 !?!?!
9─┬──┬─────1
3─┴──┼─┬─┬─3
7──┬─┴─┼─┴─7
1──┴───┴───9 (一個可靠的排序網絡)
沒錯,鬼腳圖搖身一變變成了可靠的排序方式,叫做"並行排序"
這是一個由許多比較器所組成的比較網絡(範例為4輸入4輸出),而他是一個可靠的排序網絡 (比較網絡中的排序網絡)
一個可靠排序網絡的工作方式
經過4個比較之後,網絡輸出端即會輸出正確的遞增排序數字出來~~
下面是一個插入排序的排序網絡
a1 ─┬───┬───┬───┬───┬───┬───┬─ b1
a2 ─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─ b2
a3 ───┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─── b3
a4 ─────┴─┬─┴─┬─┴─┬─┴─┬─┴───── b4
a5 ───────┴─┬─┴─┬─┴─┬─┴─────── b5
a6 ─────────┴─┬─┴─┬─┴───────── b6
a7 ───────────┴─┬─┴─────────── b7
a8 ─────────────┴───────────── b8
沒錯~
這次希望你可以來判定,經過擦擦塗塗修修改改的鬼腳圖到底是不是可靠的排序網絡呢?
第一行為n,m n(0<n<=64)代表這個比較網絡有幾個輸入,m(0<m<=256)代表長度
第二行有一個數字x(0<x<=1000),代表測試排序的數字有幾組,你可以相信如果是一個不可靠的排序網絡,這個表現會在測試數組中出現
接下來x行為n個輸入的數字 (0<=An<=2147483647)
之後為排序網絡輸入
測資間沒有空行,以eof結尾
如果是一個可靠的排序網絡的話
請輸出 "This is a reliable sorting ghost leg!"
如果不是一個可靠的排序網路的話
請輸出 "So sad......This is just a ghost leg."
4 12 1 0 1 1 0 -A--C------- -A--C-D--E-- ---BC-D--E-- ---B--D----- 8 27 1 1 0 1 1 5 1 4 3 -A---H---N---S---X---A---C- -A-B-H-I-N-O-S-T-X-Y-A-B-C- ---B-C-I-J-O-P-T-U-Y-Z-B--- -----C-D-J-K-P-Q-U-W-Z----- -------D-E-K-L-Q-R-W------- ---------E-F-L-M-R--------- -----------F-G-M----------- -------------G------------- 8 14 1 0 0 1 1 0 1 1 1 --A----------- --A--B-------- --A--B--C----- --A--B--C--D-- --A--B--C--D-- -----B--C--D-- --------C--D-- -----------D--
This is a reliable sorting ghost leg! This is a reliable sorting ghost leg! So sad......This is just a ghost leg.
您應該注意的是
如果一個比較網絡是
a1 --A-----C--
a2 --A--B-C---
a3 --A--B-----
這代表對於A比較器 您應該比較a1跟a3
對於B比較器 您應該比較 a2跟a3
對於C比較器 您應該比較 a1跟a2
而比較器編號只會在A~Z之間
但是不代表每個英文字母只會出現一次
但是保證相同的字母不會出現在旁邊,避免搞混
感謝morris1028 , liouzhou_101 和 stanley17112000 通知
2011/08/05 16:24 修正測資 , 重測6筆資料
2011/08/05 20:55 加強測資 , 重測7筆資料
2011/08/06 00:29 修正測資 , 重測7筆資料
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
|
沒有發現任何「解題報告」
|
|||||