作者H45 (!H45)
看板logic
標題Re: [請益] 找出假幣
時間Fri Jan 27 20:29:21 2006
深究：k個錢幣中有一袋假幣(與真幣重量不同)，請利用天平秤秤n次找出假幣
，並說出假幣的重量較輕還是重。請問Minimum of n？
如何以一個演算法算出這個Minimum of n?
Algorithm: To find Minimum of n.
Input: k個錢幣
Output: 最少必須秤n次
以下是我自己努力過的結果
我試圖找出「規律」，但是似乎很困難
我會繼續把各個情況列出來，不知道有沒有助於找出這種演算法
如果演算法不適合在這個板出現
請告知我自d
Begin Case:
Case1. k=1
它就是假幣
Case2. k=2
Begin Case:
Case1. 未知假幣輕重：
Begin Case:
Case1. 未知假幣是哪一個：無解
Case2. 已知假幣是哪一個：
Step1. 取假幣放天秤左邊；取剩下一個放天秤右邊；沒有剩下不秤的。
Begin Case:
Case1. 天秤向左傾：天秤左邊的那一個是假幣；假幣較重。
Case2. 天秤向右傾：天秤左邊的那一個是假幣；假幣較輕。
Case3. 天秤不傾斜：不可能。
End Case
End Case
Case2. 假幣較重、未知假幣是哪一個：
Step1. 取任一個放天秤左邊；取剩下一個放天秤右邊；沒有剩下不秤的。
Begin Case:
Case1. 天秤向左傾：天秤左邊的那一個是假幣；假幣較重。
Case2. 天秤向右傾：天秤右邊的那一個是假幣；假幣較重。
Case3. 天秤不傾斜：不可能。
End Case
Case3. 假幣較輕、未知假幣是哪一個：
Step1. 取任一個放天秤左邊；取剩下一個放天秤右邊；沒有剩下不秤的。
Begin Case:
Case1. 天秤向左傾：天秤右邊的那一個是假幣；假幣較輕。
Case2. 天秤向右傾：天秤左邊的那一個是假幣；假幣較輕。
Case3. 天秤不傾斜：不可能。
End Case
End Case
Case3. k=3
Begin Case:
Case1. 未知假幣輕重：
Begin Case:
Case1. 未知假幣是哪一個：
Step1. 取任一個放天秤左邊；取剩下任一個放天秤右邊；剩下一個不秤。
Begin Case
Case1. 天秤向左傾：
Step2. 拿下天秤左邊的那一個，取剩下一個不秤的放天秤左邊。
Begin Case
Case1. 天秤向左傾：天秤右邊的那一個是假幣；假幣較輕。
Case2. 天秤向右傾：不可能。
Case3. 天秤不傾斜：剩下一個不秤的是假幣；假幣較重。
End Case
Case2. 天秤向右傾：
Step2. 拿下天秤左邊的那一個，取剩下一個不秤的放天秤左邊。
Begin Case
Case1. 天秤向左傾：不可能。
Case2. 天秤向右傾：天秤右邊的那一個是假幣；假幣較重。
Case3. 天秤不傾斜：剩下一個不秤的是假幣；假幣較輕。
End Case
Case3. 天秤不傾斜：剩下那一個不秤的是假幣。
Step2. 取假幣和剩下任一個，到「Case2. k=2→Case1. 未知假幣輕重→Case2. 已知假幣是哪一個」。
End Case
Case2. 已知假幣是哪兩個：
Step1. 取不是假幣放天秤左邊，取剩下一個放天秤右邊。
Begin Case
Case1. 天秤向左傾：天秤右邊的那一個是假幣；假幣較輕。
Case2. 天秤向右傾：天秤右邊的那一個是假幣；假幣較重。
Case3. 天秤不傾斜：剩下那一個不秤的是假幣。
Step2. 取假幣和剩下任一個，到「Case2. k=2→Case1. 未知假幣輕重→Case2. 已知假幣是哪一個」。
End Case
Case3. 已知假幣是哪一個：
Step1. 取假幣和剩下任一個，到「Case2. k=2→Case1. 未知假幣輕重→Case2. 已知假幣是哪一個」。
End Case
Case2. 假幣較重
Begin Case:
Case1. 未知假幣是哪一個：
Step1. 取任一個放天秤左邊，剩下任一個放天秤右邊，剩下一個不秤。
Begin Case:
Case1. 天秤向左傾：天秤左邊的是假幣；假幣較重。
Case2. 天秤向右傾：天秤右邊的是假幣；假幣較重。
Case3. 天秤不傾斜：剩下不秤的是假幣；假幣較重。
End Case
Case2. 已知假幣是哪兩個：
Step1. 取不是假幣放天秤左邊，剩下任一個放天秤右邊，剩下一個不秤。
Begin Case:
Case1. 天秤向左傾：不可能。
Case2. 天秤向右傾：天秤右邊的是假幣；假幣較重。
Case3. 天秤不傾斜：剩下一個不秤的是假幣；假幣較重。
End Case
End Case
Case3. 假幣較輕
Begin Case:
Case1. 未知假幣是哪一個：
Step1. 取任一個放天秤左邊，剩下任一個放天秤右邊，剩下一個不秤。
Begin Case:
Case1. 天秤向左傾：天秤右邊的是假幣；假幣較輕。
Case2. 天秤向右傾：天秤左邊的是假幣；假幣較輕。
Case3. 天秤不傾斜：剩下不秤的是假幣；假幣較輕。
End Case
Case2. 已知假幣是哪兩個：
Step1. 取不是假幣放天秤左邊，剩下任一個放天秤右邊，剩下一個不秤。
Begin Case:
Case1. 天秤向左傾：天秤右邊的是假幣；假幣較輕。
Case2. 天秤向右傾：不可能。
Case3. 天秤不傾斜：剩下一個不秤的是假幣；假幣較輕。
End Case
End Case
End Case
Case4. k=4
Begin Case:
Case1. 未知假幣輕重：
Begin Case:
Case1. 未知假幣是哪一個：
Case2. 已知假幣是哪三個：
Case3. 已知假幣是哪兩個：
Case4. 已知假幣是哪一個：
End Case
Case2. 假幣較重：
Begin Case:
Case1. 未知假幣是哪一個：
Case2. 已知假幣是哪三個：
Case3. 已知假幣是哪兩個：
End Case
Case3. 假幣較輕：
Begin Case:
Case1. 未知假幣是哪一個：
Case2. 已知假幣是哪三個：
Case3. 已知假幣是哪兩個：
End Case
End Case
End Case
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 218.34.68.20
1F：推 joad:看起來好像程式碼 XD 01/31 02:54
2F：推 motai:感覺可以不用寫那麼多 @ @" 02/01 17:18