弹簧秤称球问题算法分析及程序模拟-技术圈

一、抛出问题

昨天绍兴越州中学赵军老师在QQ群里发了一个有趣的问题，引起了众多老师的热烈讨论。问题如下：

6只球外观完全一样，但5球重量一样，仅有一只重量不同，不知是轻还是重。问：使用一只弹簧称，其可以称出任意多个球的重量，最多称重三次，如何求出每个球重量？

一开始大家都以为是传统的无砝码天平称球问题，想用分治算法来解决。在赵军老师的提示之后，才发现弹簧秤和无砝码天平的区别：弹簧秤是可以称量出小球的具体重量的，而且题目要求求出每个球的具体重量。

我看了一下题目和大家的讨论，一时半会也想不出什么办法来，就备课去了。

二、惊现妙解

过了一会儿，发现QQ群里又多了不少消息，其中桐乡高级中学朱海宁老师的发言引起了我的注意。

朱老师把小球依次编号1-6，分成3次称量，第一次将球1,2,3合在一起称，第二次将球2,3,4,5合在一起称，第三次将球3,4合在一起称，可以表示为：3x=123，4y=2345，2z=34。

一开始我没怎么看懂，发现朱老师提供的表达式中没有出现6号球，心里就产生了疑问，万一6号球是异球呢？不称量它怎么得出异球的重量？于是随口说了一句：@桐乡高级中学朱海宁有6个球哦。

朱老师耐心地回答我：可以推出来的，比如x=y，那就是6号球有问题，单独称一下就好。

听了这句话，我感觉有点明白了，其实第三次称量不一定是将球3,4合在一起称。若前两次称量结果证明了x=y，则说明6号球是异球，那么第三次就直接称量6号球，再根据前两次称量结果，可以计算出其他球的重量。

我又继续思考了x!=y的情形，发现可以轻松地推导出异球为1和5的情形，即当y=z时，异球为1；当x=z时，则异球为5。

但如果异球不是1和5呢？用纯数学推导的方法似乎难以实现。我一下子又没有思路了。

三、灵光一现

突然我灵光一现——为什么一定要采用数学推导的方式呢？计算思维，利用计算机来帮忙解决问题，不正是我们信息技术学科的核心素养吗？

模拟算法是最容易想到的方法，给定一些测试数据去模拟计算结果。本问题只有6个小球，问题规模并不大，我们没有必要直接编程解题，可以先在脑海中模拟一下。

我先假设2号球是异球且偏轻，假设普通球的重量均为3，可设置2号球的重量为2，这样就能计算出x = 8/3，y = 11/4，z = 6/2，从而得到关系式x < y < z。

同理，若3号球是异球且偏轻，则有z < x < y；若4号球是异球且偏轻，则有z < y < x。

由此我们就得出了当异球偏轻时的各种可能性，而且可以根据x，y，z的值计算出所有小球的重量。

当异球偏重时可以采用同样的办法解决，无非是不等号的方向变化了而已。

四、算法梳理

现在我们来把整个算法梳理一下：

1．先取出任意3个球（编号1,2,3）一起称，得到表达式3x=123；

2．从已称量的3个球中任意拿出2个（假设是2，3，属于A组），再从未称量的球中任意拿出2个（编号4,5，属于B组），合在一起称，得到表达式4y=2345；

3．若x==y，则说明球6为异球，称量球6；

4．若x!=y，则从A组拿出任意一个球（假设是3），从B组拿出任意一个球（假设是4），合在一起称，得到表达式2z=34；

5．根据x，y，z的大小关系，可以得知异球：若y=z，则说明异球在x中，且异球为1；若x=z,则说明异球在y中，且异球为5。

其他情况可以将数据代入进一步计算和推导。

当异球偏轻时：若x，则异球为1；若x，则异球为2；若z，则异球为3；若z，则异球为4；若y，则异球为5。

当异球偏重时：若x>y=z，则异球为1；若x>y>z，则异球为2；若z>x>y，则异球为3；若z>y>x，则异球为4；若y>x=z，则异球为5。

当然，第三次称量的两个球也不一定非得是3和4，只要保证从A,B组中各取一个就行了。其组合可以是24、25、34或35。

我把上述算法梳理发到了QQ群里，获得了老师们的认可，赵老师和朱老师都为我点赞。

五、程序模拟

事情到这里似乎已经结束了。但只提出算法，不编写程序不是我的风格。不把事情完全做好我是不会罢休的。于是我决定编写程序实现算法功能。

这是我的第一版程序：

def fun_1(a):    x = sum(a[:3])  # 第一次称重：3x=123    y = sum(a[1:5]) # 第二次称重：4y=2345    if x/3 == y/4: # 前面5个球等重，则球6为异球        z = a[5] # 第三次称重：称量异球6        print(f"异球为6，其重量为{z}，其他球重量为{x//3}")    else:        z = a[2] + a[3] # 第三次称重：2z=34        if y/4 == z/2: # 异球为1            print(f"异球为1，其重量为{x-z}，其他球重量为{z//2}")        elif x/3 == z/2: # 异球为5            print(f"异球为5，其重量为{y-x}，其他球重量为{z//2}")        elif x/3 < y/4 < z/2 or x/3 > y/4 > z/2: # 异球为2            print(f"异球为2，其重量为{y-3*z//2}，其他球重量为{z//2}")        elif z/2 < y/4 < x/3 or z/2 > y/4 > x/3: # 异球为4            print(f"异球为4，其重量为{z-x//3}，其他球重量为{x//3}")        else: # 异球为3            print(f"异球为3，其重量为{2*z-x}，其他球重量为{x-z}")import random       for i in range(16):    a = [3] * 6 # 初始化每个小球重量均为3    num = random.randint(0, 5) # 选择任意一个小球为异球    a[num] = a[num] + random.choice([-1,1]) #异球重量可轻可重    print(a)    fun_1(a, 2, 4)

程序完全按照前面的算法来编写，自认为应该是完美无缺的。但是程序运行结果却让我傻了眼——第一个数据就错了，明明是4号球偏轻，程序却说异球为2，而且各个球的重量都算错了。

我增加循环次数，又测了好几次，发现其他小球为异球时都是对的，就是4号球出错。

问题出在哪里呢？

我陷入了沉思中。

六、找出BUG

为什么4号球总是出错呢？我又看了看测试结果，发现程序总是把4号球错认为2号球。

这说明什么问题呢？

会不会是因为先判断2号球，再判断4号球的缘故？我尝试着把多分支语句中elif语句的位置换了一下，让程序先判断4号球，再判断2号球。

再次运行程序，观看测试结果。果然不出所料，现在程序把2号球错认为是4号球了。

原来问题出在这里！

再仔细看看代码，发现这两条elif语句竟然是等效的，仅仅是写法变了一下而已！

原来问题出在这里！

那该怎么修改呢？看上去似乎没有办法。难道我的算法本身就是错的？

我再一次陷入了沉思。

七、问题解决

2号球和4号球到底谁才是异球？条件表达式怎么会一模一样呢？是我漏掉了什么东西吗？

再仔细看看算法分析。咦，我好像发现了点什么。

当异球为2时，4号球是普通球，则z应该为整数；同理，当异球为4时，2号球是普通球，则x应该为整数。

妙啊！这是属于我的尤里卡时刻！

好了，现在只需要加上两个限制条件就行了，第二版程序如下：

def fun_2(a):    x = sum(a[:3])  # 第一次称重：3x=123    y = sum(a[1:5]) # 第二次称重：4y=2345    if x/3 == y/4: # 前面5个球等重，则球6为异球        z = a[5] # 第三次称重：称量异球6        print(f"异球为6，其重量为{z}，其他球重量为{x//3}")    else:        z = a[2] + a[3] # 第三次称重：2z=34        if y/4 == z/2: # 异球为1            print(f"异球为1，其重量为{x-z}，其他球重量为{z//2}")        elif x/3 == z/2: # 异球为5            print(f"异球为5，其重量为{y-x}，其他球重量为{z//2}")        elif z/2 == z//2 and (x/3 < y/4 < z/2 or x/3 > y/4 > z/2): # 异球为2            print(f"异球为2，其重量为{y-3*z//2}，其他球重量为{z//2}")        elif x/3 == x//3 and (z/2 < y/4 < x/3 or z/2 > y/4 > x/3): # 异球为4            print(f"异球为4，其重量为{z-x//3}，其他球重量为{x//3}")        else: # 异球为3            print(f"异球为3，其重量为{2*z-x}，其他球重量为{x-z}")

运行程序，测试结果完美无瑕。

八、精益求精

现在，问题应该说得到完美解决了。但解决问题从来都没有最好，只有更好。

第三次称量的方式有4种，我只考虑了其中一种。另外3种的结果是不是和前面一致？我还没有编程验证。这件事情不做好，就不算完。

于是，秉着精益求精的精神，追求完美的我又给出了第三版程序：

def fun_3(a, i, j):    x = sum(a[:3])  # 第一次称重：3x=123    y = sum(a[1:5]) # 第二次称重：4y=2345    if x/3 == y/4: # 前面5个球等重，则球6为异球        z = a[5] # 第三次称重：称量异球6        print(f"异球为6，其重量为{z}，其他球重量为{x//3}")    else:        z = a[i-1] + a[j-1] # 第三次称重：2z=24或25或34或35        if y/4 == z/2: # 异球为1            print(f"异球为1，其重量为{x-z}，其他球重量为{z//2}")        elif x/3 == z/2: # 异球为9-j            print(f"异球为{9-j}，其重量为{y-x}，其他球重量为{z//2}")        elif z/2 == z//2 and (x/3 < y/4 < z/2 or x/3 > y/4 > z/2): # 异球为5-i            print(f"异球为{5-i}，其重量为{y-3*z//2}，其他球重量为{z//2}")        elif x/3 == x//3 and (z/2 < y/4 < x/3 or z/2 > y/4 > x/3): # 异球为j            print(f"异球为{j}，其重量为{z-x//3}，其他球重量为{x//3}")        else: # 异球为i            print(f"异球为{i}，其重量为{2*z-x}，其他球重量为{x-z}")
import random       for i in range(16):    a = [3] * 6 # 初始化每个小球重量均为3    num = random.randint(0, 5) # 选择任意一个小球为异球    a[num] = a[num] + random.choice([-1,1]) #异球重量可轻可重    print(a)    fun_3(a, 2, 4)    fun_3(a, 2, 5)    fun_3(a, 3, 4)    fun_3(a, 3, 5)    print("#" * 20)

程序运行结果如下：

终于搞定了，又可以愉快地玩耍上课了。

需要本文源代码和word文档的，可以加入“Python算法之旅”知识星球参与讨论和下载文件，“Python算法之旅”知识星球汇集了数量众多的同好，更多有趣的话题在这里讨论，更多有用的资料在这里分享。

我们专注Python算法，感兴趣就一起来！

相关优秀文章：

阅读代码和写更好的代码

最有效的学习方式

Python算法之旅文章分类