作者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