算法，称球问题

win_hate

以下这个连接
http://bbs.chinaunix.net/viewthr ... &extra=page%3D1
因为标题不规范而被锁定。再次提醒大家发帖标题要清楚，明白，谢谢合作。

现另开一贴，我的方法如下：

设数据分为三组 A[1..4],B[1..4],C[1..4]

1 如果  sum(A, 1..4) == sum(B, 1..4) // 目标在 C 中
  1.1 如果 sum (A, 1..3) == sum (C, 1..3)
           目标为 C[4] 再作一次比较可知轻重，退出。
  1.2 如果 sum (A, 1..3) > sum (C, 1..3)
           目标较轻，比较 C[1], C[2] 可推出目标之索引，退出。
  1.3 如果 sum (A, 1..3) < sum (C, 1..3) 同1.2

2 如果 sum(A, 1..4) > sum (B, 1..4) // 目标不在 C 中，若目标在A中，则重，在B中，则轻。
  2.1  如果 A[3]+B[3] +B[4] == A[4] + B[1] + B[2]
        目标在 A[1]A[2] 中，且目标较重，比较 A[1], A[2] 可得目标索引，退出。
  2.2  如果 A[3]+B[3] +B[4] > A[4] + B[1] + B[2]    // (X)
        2.2.1 如果 B[1]!=B[2], 则目标在 B 中，较轻，从比较结果可知索引，退出。
        2.2.2 如果 B[1]==B[2], 则目标不为 B[1], B[2]。
        同时，目标也不为 A[4]，因为若目标在A中，必定较重，这与(X) 相悖。
        目标不为 B[3], B[4]，因为若目标在 B 中，必定较轻，这与(X) 相悖.
        故目标为 A[3](其实此时(X) 可化为A[3]>A[4] 了), 退出。
  2.3 如果 A[3]+B[3] +B[4] < A[4] + B[1] + B[2]   
        同 2.2

3 如果 sum(A, 1..4) > sum (B, 1..4)  
        同 2

q.e.d

[ 本帖最后由 win_hate 于 2005-11-9 10:50 编辑 ]

converse

1.1应该是"目标为C[4]"吧~~~

win_hate

对，马上更正！

FH

这都搞算法啦？

zh_manyu

将球分为4组每三个一组（A，B，C，D组）
A，B，C，D int数组表示轻球为0重球为1
拿A，B组到天平上
if（A>B）
{
  拿C和A到天平
  if（C=A）
  {
     球为轻 在B中；
     拿B中两个球到天平
     if（B[0]>B[1])
          B[1]为所要找的球；
     if（B[0]=B[1])
          B[2]为所要找的球；
  }

  if（C<A）
  {
     球为重 在A中；
     拿A中两个球到天平
     if（A[0]>A[1])
          A[0]为所要找的球；
     if（A[0]=A[1])
          A[2]为所要找的球；
  }         
}

if（A<B）和if（A=B）我就不写 出来了

[ 本帖最后由 zh_manyu 于 2005-11-9 12:47 编辑 ]

win_hate

原帖由 zh_manyu 于 2005-11-9 12:46 发表
将球分为4组每三个一组（A，B，C，D组）
A，B，C，D int数组表示轻球为0重球为1
拿A，B组到天平上
if（A>B）
{
  拿C和A到天平
  if（C=A）
  {
     球为轻 在B中；
     拿B中两个球到天平
      ...


if（A<B）和if（A=B）我就不写 出来了

能把 A==B 的情况写出来吗？ 谢谢.

yzc2002

刚想了个称13球的方法：
有13个球，有一个坏的，称三次把坏球找出
(1)分成三堆，分别为4、4、5，4个和4个称一下，如不等，则坏球在这8个球中，剩下的和称12个球没区别，见上面win_hate的称法
(2)若4 个和4个相等，则坏球在5个中，把5个分成三堆：A{a1,a2}、B{b1,b2}、C{c1}，从好球中拿一个补到C中，记为c2，B和C称一下，如果：
   <1>相等，则坏球在A中，把a1和一个好球称一下，如果平，则a2是坏球，否则a1是坏球
   <2> B>C，坏球在B或C中，把b1、b2称一下，如果相等，则坏球是c1；不等，说明坏球在b1、b2中，且重，所以哪个重就是哪个坏
   <3> B<C，坏球在B或C中，把b1、b2称一下，如果相等，则坏球是c1；不等，说明坏球在b1、b2中，且轻，所以哪个轻就是哪个坏

yarco1

不要搞特殊阿, 有没m球的算法?

zh_manyu

原帖由 win_hate 于 2005-11-9 13:01 发表


能把 A==B 的情况写出来吗？ 谢谢.

很不要意思这种 有个情况没考虑 是错的


看来只能分3组来解决

cooljia

上来就想分四组的人肯定就错了.