Re: [問題] 9條電線...

看板puzzle (益智遊戲 - 數獨,拼圖,推理,西洋棋)作者perfectcamel (完美駱駝)時間16年前 (2010/03/26 05:20)推噓0(0推 0噓 6→)

留言6則, 2人參與討論串5/6 (看更多)

※ 引述《stool100 (思念是毒妳是解藥)》之銘言： : 一個101摩天大樓.. : 一樓到 101 樓有九條獨立的電線 : 就是一樓有九個線頭 : 101樓也是有九個線頭 : 顏色相同....如何查線?? : 限制的工具只有一個量測導通於否的電表.. : 可以將任意條線短路.. : 不過只能上樓一次.......... : 如何將一樓線號 123456789 對上101 樓ABCDEFGHI?? 看到各種有趣的辦法,小弟來獻醜一下剛剛看到bigboat大大的發文之後,突發奇想覺得這題好像有通解稍微想了一下,決定po上來給各位大大鞭先說原題的情況,是3的倍數此時將線路短路為1 2 3 3 3 3...的組合(這邊指的是線路數目) 先假設1組的線路為A,2組的線路為BC, 很多3組的線路分別為K(x,y),其中x代表他是第幾組的線路,y代表第幾條線路 (以上的符號都是方便說明,事實上在過程中,我們不知道每條的順序,可以任意定義) 上樓測出組合後,清除掉所有連線,把A,B,K(1,1)連起來對所有n,我們把每個K(n-1,2)和K(n,1)連起來,然後最後的一組,則將K(q,2)和C連起來 (假設q是最後一組) 下樓之後,由於我們已經知道A了, 所以就可以藉由和A連結的是來知道誰是B和K(1,1) (B和K(1,1)之間是不會搞混的,他們一個是3組一個是2組) 知道K(1,1)之後,就可以開始查第1組, 結果會發現K(1,2)是有和別人短路的線路,其連結對象便是K(2,1) 而K(1,3)則和所有線路斷路,由此可以分辨K(1,2)和K(1,3) 以此方式類推,當知道K(n-1,1)時,就可以分辨出K(n-1,2)和K(n-1,3), 且可以找出K(n,1) 當搜尋進行到最後一組時,我們已經找出K(q,1) 此時和C有連結的q組成員則是K(q,2),另外一條線路則是K(q,3) 這個方法理解之後,便可以做總數為3n+1和3n+2的case 3n+1的case做法完全相同,只是一開始的分組變為1 1 2 3 3 3 3 3 3 3... 隨便排除一個1組然後像剛剛解3n的問題那樣接下樓時,沒有和任何人接起來的1組就可以被分辨出來了 3n+2也是類似的做法,一開始的分組變成1 2 2 3 3 3 3 ... 上樓後,把其中一個2組移出,先照著3n的方式接好然後把剛剛移出的2組其中一個成員接到1上如此一來,關於後面無限的3組的部分就沒問題了而2組中,靠著"另一條線路是不是和所有人斷路"就可以分辨是不是先被我們移除的2組然後每一組內可以用是否和1連結來分辨彼此這樣一來,所有數字的線路都可以用這個方法解決不是很擅長講解= =a 如果看不太懂請鞭小力一點 -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 114.45.9.192