September 21, 2006

《称球问题》的完整代码

晕死,上次发的那篇文章居然忘了给代码。现在把它贴出来,顺便加点注释。
(最近拼命写Lua数据结构实现中...)

#metga.py
#useage: python metga.py datefile
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 < style="color: rgb(51, 51, 255);">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]

#递归地分3片称球
def test (balls):
l = len(balls)
if l == 1:
return balls[0].number
n = l / 3
if l < n =" 1" parts =" [balls[:n]," statu =" metage(parts[0]," style="color: rgb(51, 51, 255);">if statu == EQUAL:
return test(balls[2*n:])
elif statu == QUESTION:
return test(balls[:n])
else:
return test(balls[n:2*n])

#读取数据文件(内容为n个数字,每个一行,其中有一个与其它不等)
weight_list = map(string.atoi, open(sys.argv[1]).readlines())
ball_list = map(Ball, weight_list) #创建球组成的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)

可恶的Blogger对于程序的排版支持约等于无,忙死我了。等我学完编译原理,我一定要开发一个JavaScript实现的词法分析器!

No comments: