天平机器人

13只大小相同的球，其中一只 球与其他的12只球质量不一样，可能比其他球重，也可能比其他球轻。现有一只没有砝码的天平，天平只可以使用3次，如何利用天平找出这只质量与其他球不同的球？


下面是我写的机器人，可以在N个球中寻找这个异重球，是用javascript实现的。


http://www.lightmtv.org/minibot/minibot.html

此题的正解：


第一步：天平左侧： 1, 2, 3, 4 ，天平右侧：
5, 6, 7, 8


情况A：平衡，则说明异重球在，9,10,11,12,13中


第A2步：天平左侧： 9, 10 ，天平右侧： 1, 11


情况AA：平衡，则说明异重球在12,13中


第AA3步：天平左侧： 12，天平右侧： 1


情况AAA：平衡，则说明异重球为13号球。


情况AAB：不平衡，则说明异重球为12号球，且可知此球相对是重是轻。


情况AB：左重右轻，则说明可能是9,10中一球重，或11轻。


第AB3步：天平左侧： 9，天平右侧： 10


情况ABA：平衡，则说明11号球轻。


情况ABB：左重右轻，则9号球为重球


情况ABC：右重左轻，则10号球为重球、


情况AC：右重左轻，与AB同


情况B:左重右轻，则说明可能是1,2,3,4中一球重，或5,6,7,8中一球轻


天平右侧：
2, 7, 8

情况BA：平衡，则说明可能是3，4中一球重

重侧为异重球，且此球为重球。平衡则无解。

情况BC：右重左轻，与情况BB同



解题过程：当我想要编写算法在N个球中寻找异重球时，开始是茫然，不知道如何下手，但当我想到的一些状态后，就有了思路，这些状态是，天平的左倾，右倾，平衡，球是可能重，可能轻，未知，标准重量，这些状态都需要被表示，被记录。每个球的初始状态都是未知，在解题的过程中都会重新计算他的状态。因此需要一个函数，根据天平的状态来计算球的可能状态。然后需要思考的是最重要的问题，写一个函数，根据球的状态来决定将哪些球放在左边，哪些球放在右边，简单的说是将目标球分成3份。

评论

4 楼 jasongreen 2007-07-15  

还有谁做过可以互动的吗？ 由玩家来告知天平状态

3 楼 jasongreen 2007-06-13  

我的也是针对N个球的，不过对13球问题可以很好给出解答，13球是个特殊个案

2 楼 Lich_Ray 2007-06-08  

奇怪，怎么代码多了一遍？！

1 楼 Lich_Ray 2007-06-08  

不好意思。我也做了这题。不过是用此手段面向任意数量的球，用Python写的。
在《程序员》上看到题目的。

《程序员》上使用了将球分为0～n-1，n～2n-1，2n～N-1（n=(N%3)?(N/3+1):(N/3)）两两递归比较的方法。但由于在整个比较过程中，这个球到底偏轻还是偏重一直没有确定而进行了多次无效的比较，一个字：慢。

我的主要思想与《程序员》中的类似，不过对球的列表的分片有所不同：
parts = [balls[:n], balls[n:2*n], balls[2*n:3*n]]
保证3片球数相同。确定是那一片出了问题后返回它时，最后一片由于可能不是balls[2*n:3*n]（len(balls)%3!=0），所以返回balls[2*n:]。

球包括号码和质量两个属性，类定义如下：
class Ball:
    def __init__ (self, weight):
self.weight = weight
self.number = 0[/python]
（注：number的默认值0是无效的，号码从1开始）
sum()用于给质量求和：
def sum (balls):
    tmp = 0
    for ball in balls:
tmp += ball.weight
    return tmp[/python]
天平函数，返回比较结果——HEAVY = 1，LIGHT = -1，EQUAL = 0：

def metage (leftBalls, rightBalls):
    left = sum(leftBalls)
    right = sum(rightBalls)
    if left > right: return HEAVY
    if left < right: return LIGHT
    return EQUAL

用全局变量QUESTION保存问题球是轻是重，这由预测量函数pre()给出，它工作后还返回有问题的分片。这样test()函数在工作时可以少一半比较次数。

test函数递归调用自身，可以采用折半比较的方式。但那样会提供算法的时间复杂度。假设n个质量数据求和要进行n次运算，折3片比较共需p=2*(x/3+x/3^2+...x/3^(N-1))次运算，化简得p=x-x/3^n，即求和运算次数不会大于球总个数。而折半比较则需(2^(N+1)-1)x（不准）次运算，明显多于使用分3片比较。

具体比较的条件详见代码，自行阅读。

最后解释一下数据文件的读入情况。数据文件是普通文本文件，每行一个数字，其中一个与其它不同。open(sys.argv[1]).readlines()返回一个由每行的字符串构成的列表，weight_list = map(string.atoi, open(sys.argv[1]).readlines())对这个列表中的每一项进行转数字操作并存入weight_list。ball_list = map(Ball, weight_list)把表中每一项创建Ball对象，最后test(pre(ball_list)计算返回球的编号。

#metage.py
import sys
import string

#作指示符的全局变量
HEAVY = 1
LIGHT = -1
EQUAL = 0
QUESTION = 0
ANSWER = ""

class Ball:
    def __init__ (self, weight):
	self.weight = weight
	self.number = 0

#求球重和的函数
def sum (balls):
    tmp = 0
    for ball in balls:
	tmp += ball.weight
    return tmp

#称量函数
def metage (leftBalls, rightBalls):
    left = sum(leftBalls)
    right = sum(rightBalls)
    if left > right: return HEAVY
    if left < right: return LIGHT
    return EQUAL

#多了一次称量，同时判断球是轻还是重
def pre (balls):
    global QUESTION
    n = len(balls) / 3
    parts = [balls[:n], balls[n:2*n], balls[2*n:3*n]]
    statu = metage(parts[0], parts[1])
    if statu == EQUAL:
	QUESTION = metage(parts[2], parts[0])
	return balls[2*n:]
    QUESTION = statu
    if metage(parts[0], parts[2]) == EQUAL:
	return parts[1]
    else:
	return parts[0]

#真正的称量过程，递归地用你所说的办法
def test (balls):
    l = len(balls)
    if l == 1:
	return balls[0].number
    n = l / 3
    if l < 3:
	n = 1
    parts = [balls[:n], balls[n:2*n], balls[2*n:3*n]]
    statu = metage(parts[0], parts[1])
    if statu == EQUAL:
	return test(balls[2*n:])
    elif statu == QUESTION:
	return test(balls[:n])
    else:
	return test(balls[n:2*n])

#读读文件
weight_list = map(string.atoi, open(sys.argv[1]).readlines())
ball_list = map(Ball, weight_list)
i = 1
#设置球号
for ball in ball_list:
    ball.number = i
    i += 1
if QUESTION == 1:
    ANSWER = "heavier"
else:
    ANSWER = "lighter"
print "The No.%d ball is %s than others." % (test(pre(ball_list)), ANSWER)

数据文件的内容类似这个：
13
14
13
13
13
13
把它的文件名作第一个参数：
python metage.py filename