September 16, 2006

《称球问题》的 python 版解答

《程序员》杂志第8期上讲解了这样一个问题:在N个球中,有一个球重量与其他球重不同(偏重或偏轻),在没有砝码的天平上进行k(N<=(3^k-1)/2)次称量,得到这个球的编号,并判断它比其它球轻或重。

《程序员》上使用了将球分为0~n-1,n~2n-1,2n~N-1(n=(N%3)?(N/3+1):(N/3))两两递归比较的方法。但由于在整个比较过程中,这个球到底偏轻还是偏重一直没有确定而进行了多次无效的比较,而且使用C++描述,对于这个需要大量出来数组的算法来说十分繁琐。我采用了支持函数式编程的Python语言优化了这个算法,脚本和测试用数据文件(举例)在附件中有下载。

主要思想与《程序员》中的类似,不过对球的列表的分片有所不同:
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
(注:number的默认值0是无效的,号码从1开始)
sum()用于给质量求和:
def sum (balls):
tmp = 0
for ball in balls:
tmp += ball.weight
return tmp
天平函数,返回比较结果——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)计算返回球的编号。

关于python的函数式编程请初学者自己参考教材理解。感谢网友孔辉GID2257990(Lava-Lava平台)在程序调试方面给予的帮助。

No comments: