八枚银币

說明
現有八枚銀幣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"

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

最少2次，最多4次。

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

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

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

这样应该是3步

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

一条语句搞定：


假币 = 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))

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

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

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