八枚银币

說明
現有八枚銀幣a b c d e f g h，已知其中一枚是假幣，其重量不同於真幣，但不知是較輕或較重，如何使用天平以最少的比較次數，決定出哪枚是假幣，並得知假幣比真幣較輕或較重。
解法
單就求假幣的問題是不難，但問題限制使用最少的比較次數，所以我們不能以單純的迴圈比較來求解，我們可以使用決策樹（decision tree），使用分析與樹狀圖來協助求解。

一個簡單的狀況是這樣的，我們比較a+b+c與d+e+f ，如果相等，則假幣必是g或h，我們先比較g或h哪個較重，如果g較重，再與a比較（a是真幣），如果g等於a，則g為真幣，則h為假幣，由於h比g輕而 g是真幣，則h假幣的重量比真幣輕。

完整的比較決策樹如下圖所示：
八枚銀幣

為了方便使用迴圈，使用號碼0至7表示銀幣，範例程式可以讓您輸入假幣重量，但您無法事先得知假幣是哪一枚，程式可得知假幣是哪一枚，且它比真幣輕或重。

class Coins
  def initialize
    @coins=Array.new(8,10)
  end

  def set_fake(weight)
    @coins[rand(8)]=weight
  end

  def fake
    x=@coins[0]+@coins[1]+@coins[2]
    y=@coins[3]+@coins[4]+@coins[5]
    a=@coins[0]+@coins[3]
    b=@coins[1]+@coins[4]

    if x==y
      if @coins[6]>@coins[7]
        _compare(6,7,0)
      else
        _compare(7,6,0)
      end
    elsif x>y
      if a == b
        _compare(2, 5, 0)
      elsif a > b
        _compare(0, 4, 1)
      else
        _compare(1, 3, 0)
      end

    else
      if a == b
        _compare(5, 2, 0)
      elsif a > b
        _compare(3, 1, 0)
      else
        _compare(4, 0, 1)
      end
    end
  end


  def _compare( i, j, k)
    if @coins[i] > @coins[k]
       print("\n假幣", i + 1, "較重")
    else
       print("\n假幣", j + 1, "較輕")
    end
  end
end

 print("輸入假幣重量（比 10大或小)")
  weight =gets.to_i
coins = Coins.new
coins.set_fake(weight)
coins.fake()
print "\n"

评论

20 楼 clvv 2009-10-31  

天平的每次称量会出现三种结果左偏、右偏、平衡，所以只要每次都将剩余的所有可能分成三分。这样的排除是最优的。
8个硬币其中一个重或轻，16种情况。Log3(16)=2.5237..
楼上说的最少两次只是一种特殊情况，但是这种方法却不是最优方法。因为会出现需要4次的情况。
楼主的解法应该是最优的。

19 楼 wantdrink 2009-10-19  

8个的话最多2次就能称出

18 楼 sjbrising 2009-10-18  

lonelybug 写道

把8个钱币分别放在天平两侧，每次同时每边各拿下一个，看有没有变化。
如果有变化，再把有变化的那次的两个中的一个拿出来和剩下的其中一个比。有变化就是这个，没变化就是没有比的那个。

最少2次，最多4次。

你那个程序写不写没有任何意义。还用什么决策树，任何东西都是先有解决方法，才有后来的人给他套上名字的，不要总在解决一个问题的时候去在脑子里想自己那些死记硬背下来的算法。

我又仔细看了下你的解法。最少是两次么？？另外，为什么把8个分别放在天平两侧呢？这样的话第一次称量是没有任何意义的。应该是6个分别放两侧。

17 楼 sjbrising 2009-10-18  

lonelybug 写道

sjbrising 写道

lonelybug 写道

把8个钱币分别放在天平两侧，每次同时每边各拿下一个，看有没有变化。
如果有变化，再把有变化的那次的两个中的一个拿出来和剩下的其中一个比。有变化就是这个，没变化就是没有比的那个。

最少2次，最多4次。

这种方法是比较笨的，可以说根本没有思考就可以得出这样的结果。而且次数的期望值肯定比较大~~

你的意思是说，我没用脑子思考就能写出来问题的解决方法的其中一种！？

第一，我很谦虚的问一下，您的解决方法是！？让我们也见识一下。

第二，在探讨一个问题的时候不要涉及无畏的人身攻击，否则你的母亲会非常难过让我抨击的。

对不起，是我言辞太过激了。在这里我向您道歉。
但说真的，你的方法确实有问题。

在这里我说一下我的看法。首先，是要求称量次数尽量的少。，你的那个方法甚至有可能达到四次，肯定是不可以的。是能拿解出来，但我们作为编程人员不仅仅是能解决问题就是可以的了。我们要的是最优的解决方案。不然要那么多的算法干什么？
我直接说12个球的解法。就是三次找出坏球。并且知道这个球比好球重还是轻。

1：将12个球（1-12）分成三组，每组四个，第一次天平两端各放4个球（1-4和5-8）。如果平衡，进入第2步。如果不平衡（假设1-4重）进入第5步.
2：从9-12中取出三个球（9-11）和1-3（已经认定是好球）称。如果平衡，球12是坏球，进入第三步。如果不平衡，则可以断定坏球是比好球重还是轻。进入第四步。
3：将12和一个好球称，如果偏向12，则坏球是12，并且坏球比好球重。（完毕）
4：将9-11中除去两个球（9，10）称量，如果平衡，则坏球是11.至于比好球重还是轻在第二步中已经知道。（完毕）
5：取（1-3）+(5)作为A组。（4）+(9-11)为B组。称量。如果平衡，进入6，如果不平衡进入7.
6：至此可以判定6-8中有一个球是坏的，并且比好球轻。取两球称，可找出坏球，并且知道比好球重还是轻。（完毕）
7：（最经典）如果A重，说明4对结果没有影响，是好球，则坏球在1-3中。再一次可找出坏球。如果是B重，说明要么是4对结果有影响，要么是5对结果有影响。而这取一盒好球比较可得出结果。（完毕）

至此，12球完毕。
8球的要比12球简单的多。在此不详表。
再次对自己的言语造成伤害的人表示歉意。

16 楼 lyslim 2009-10-17  

log2(8) = 3...

3次是 肯定 能称出来的最少次数吧...

要说最少2次？ 那我运气好，一开始就拿2个来称，都有可能称出来呢...最少 1 次就可以了...-。-

15 楼 vkstar 2009-10-16  

只要2次 就可以直接称出。

14 楼 marshan 2009-10-16  

yi qun niu ren.

13 楼 mengyou0304 2009-10-15  

其实在已知轻重的情况下要求三次分辨的话最大值是3*3*3=27个

12 楼 zjf_sdnu 2009-10-15  

这样的问题用香农的信息论里的公式直接就可以算出来了，我在一本奥数书上看到的。

11 楼 googya 2009-10-12  

lonelybug 写道

sjbrising 写道

lonelybug 写道

把8个钱币分别放在天平两侧，每次同时每边各拿下一个，看有没有变化。
如果有变化，再把有变化的那次的两个中的一个拿出来和剩下的其中一个比。有变化就是这个，没变化就是没有比的那个。

最少2次，最多4次。

这种方法是比较笨的，可以说根本没有思考就可以得出这样的结果。而且次数的期望值肯定比较大~~

你的意思是说，我没用脑子思考就能写出来问题的解决方法的其中一种！？

第一，我很谦虚的问一下，您的解决方法是！？让我们也见识一下。

第二，在探讨一个问题的时候不要涉及无畏的人身攻击，否则你的母亲会非常难过让我抨击的。

就是，完全是探讨嘛，方法有很多，好的方法有也有很多！另一方面，也不要太在意别人说的一些带有攻击性、中伤人的话。人不知而不愠，不亦君子乎！

10 楼 lonelybug 2009-10-10  

sjbrising 写道

lonelybug 写道

把8个钱币分别放在天平两侧，每次同时每边各拿下一个，看有没有变化。
如果有变化，再把有变化的那次的两个中的一个拿出来和剩下的其中一个比。有变化就是这个，没变化就是没有比的那个。

最少2次，最多4次。

这种方法是比较笨的，可以说根本没有思考就可以得出这样的结果。而且次数的期望值肯定比较大~~

你的意思是说，我没用脑子思考就能写出来问题的解决方法的其中一种！？

第一，我很谦虚的问一下，您的解决方法是！？让我们也见识一下。

第二，在探讨一个问题的时候不要涉及无畏的人身攻击，否则你的母亲会非常难过让我抨击的。

9 楼 sjbrising 2009-10-09  

你的这个问题称量次数不能超过3次，否侧做法一定是错误的！

8 楼 sjbrising 2009-10-09  

我看到的一个题目和这个差不多，是这样的，12个球，有一个是坏的，称三次，找出坏球，并且知道坏球是比好球重还是轻。

7 楼 sjbrising 2009-10-09  

lonelybug 写道

把8个钱币分别放在天平两侧，每次同时每边各拿下一个，看有没有变化。
如果有变化，再把有变化的那次的两个中的一个拿出来和剩下的其中一个比。有变化就是这个，没变化就是没有比的那个。

最少2次，最多4次。

这种方法是比较笨的，可以说根本没有思考就可以得出这样的结果。而且次数的期望值肯定比较大~~

6 楼 whmily 2009-10-09  

foible 写道

一条语句搞定：


假币 = a+b+c+d > e+f+g+h ? a+b > c+d ? a > b ? a : b : c > d ? c : d : e+f > g+h ? e > f ? e :f : g > h ? g : h;


最多3步，最少2步。

在8个中随便拿4个分2个一组放入两端，如果相等拿另4个重复操作，然后将不同重量2个分组放入，取其中一个就是了。

你这个是已知假币是较重的，
正解是：
a + b == c + d ? (a + b == e + f ? (a == g ? h : g) : (a == e ? f : e)) : (a + b == e + f ? (e == c ? d : c) : (e == a ? b : a))

5 楼 foible 2009-10-09  

一条语句搞定：


假币 = a+b+c+d > e+f+g+h ? a+b > c+d ? a > b ? a : b : c > d ? c : d : e+f > g+h ? e > f ? e :f : g > h ? g : h;


最多3步，最少2步。

在8个中随便拿4个分2个一组放入两端，如果相等拿另4个重复操作，然后将不同重量2个分组放入，取其中一个就是了。

4 楼 googya 2009-10-09  

这个方法不错！
实质上，有很多方法！我这里只是想要实现，而并没考虑到算法的效率！看来以后还得把算法写的比较好了，再贴出来，以免贻笑大方！

3 楼 LargeBean 2009-10-09  

1、分成2堆，一堆4个。
2、A堆分成2堆，上秤。如果平，证明在B堆，执行以下步骤，如果不平，在A堆中执行以下步骤
3、B堆中拿出2个，上秤，如果平，证明在剩下的2个中，如果不平，替换掉一个，假币能找到。
4、在B对剩下的2个中取一个，替换掉秤上的一个，不管是否平，假币都能找到。

这样应该是3步

2 楼 lonelybug 2009-10-07  

我这属于苯法，应该还有更方便的，暂时想不到了。

1 楼 lonelybug 2009-10-07  

把8个钱币分别放在天平两侧，每次同时每边各拿下一个，看有没有变化。
如果有变化，再把有变化的那次的两个中的一个拿出来和剩下的其中一个比。有变化就是这个，没变化就是没有比的那个。

最少2次，最多4次。

你那个程序写不写没有任何意义。还用什么决策树，任何东西都是先有解决方法，才有后来的人给他套上名字的，不要总在解决一个问题的时候去在脑子里想自己那些死记硬背下来的算法。