youxi.doc

python游戏编写实例教程

  for i in seq: 
    product = int(i[:where]) * int(i[where:]) 
    if product > maximum: 
       maximum, max_item = product, i 
    elif product == maximum: 
       max_item += ','+i 
    rev = list(i) 
    rev.reverse() 
    i = ''.join(rev) 
    product = int(i[:where]) * int(i[where:]) 
    if product > maximum: 
       maximum, max_item = product, i 
    elif product == maximum: 
       max_item += ','+i 
  print "Maximum at", max_item, ",product", maximum 
当然你保留了以前的函数 calc 而只是新加一个专门给 permute7.py 调用的 calc2 函数. 你试了一下速度, 成功了比 permute6.py 快了一丁点. 虽然只是这一点儿点儿, 你也觉得快活无比. 因为又一次, 你为一个大家都觉得好的方法做出了改良. 
虽然你知道在这个阶段如果你把 calc.py 整合到排列产生器中也许会得更好的提速效果, 但你觉得现在这样已经可以很多人都认同你的能力了. 而且能把一个高效的排列产生器独开来也许是聪明的做法, 因为将来你一定会再用它的. 你看了一下所有的程式, 从 permute1.py 到 permute7.py, 再做了一次速度的检定. 反正是最后一次了, 干脆做个大的吧. 
$ time python permute2.py 123456789 5 
Got 362880 items. 
Maximum at 875319642 ,product 843973902 
 
real    0m46.478s 
user    0m46.020s 
sys     0m0.430s 
 
$ time python permute3.py 123456789 5 
Got 362880 items. 
Maximum at 875319642 ,product 843973902 
 
real    0m38.997s 
user    0m38.600s 
sys     0m0.400s 
 
$ time python permute4.py 123456789 5 
Got 362880 items. 
Maximum at 875319642 ,product 843973902 
 
real    0m33.845s 
user    0m33.460s 
sys     0m0.380s 
 
$ time python permute5.py 123456789 5 
Got 362880 items. 
Maximum at 875319642 ,product 843973902 
 
real    0m10.681s 
user    0m10.530s 
sys     0m0.150s 
 
$ time python permute6.py 123456789 5 
Got 362880 items. 
Maximum at 875319642 ,product 843973902 
 
real    0m8.279s 
user    0m8.110s 
sys     0m0.170s 
 
$ time cpython permute7.py 123456789 5 
Got 181440 items. 
Maximum at 875319642 ,product 843973902 
 
real    0m7.827s 
user    0m7.650s 
sys     0m0.180s 
嗯, 很不错. 最快的要比原先快上近七倍呢! 於是你打算明天一有空便把这个最好的公式贴到网上去, 让更多人分享. 你很放心地去睡觉了. 
但是不知为了什么, 你总觉得有些事烦扰著你, 还有什么不妥的地方呢? 你实在想不到了, 迷迷糊糊地抱著迷惑不安的心情入梦. 
终於你忍不住爬了起床, 再一次回到电脑屏幕前. 你想到了一个致命的问题, 对於很大很大的排列, permute7.py 还是会尝试一下子把所有的排列都做出来, 不用多久电脑资源就会被耗光的. 你也许要另想一个方法, 每次只做一个排列. 但你是否可以把所有的排列用 1, 2, 3, 4 的方法数出来呢? 
你看著教科书上的那幅图画, 这样的树状结构应该有办法的, 你对自己说. 
慢慢读著书上的文字. 设想有 n 个数字, 先取第一个数字. 再取第二个数字, 第二个数可以放在第一个数的左或右面, 就是有 0, 1 两个选择. 再取第三个数, 放到前面选好的两个数字中, 可以放在最左, 中间, 最右, 就是有 0, 1, 2 三个选择. 嗯, 很自然吗. 忽然你想到了二进位, 八进位那些数系转换关系. "我可以设计这样一个数, ...xyz, 其中个位数 z 是二进位的, 也就是放第二个数的两个位置; 十位数 y 是三进位的, 化表放第三个数字的三个位子, 然后百位数是四进位, 千位数是五进位的, 依以类推." 没错, 这样设计的话, 如果 0 表示放於最左面的话, 则 "2021" 这个数就代表了排列五个元素 (abcde), 取一个 a, 然后第二个 b 放在 a 的右面成 ab, 取 c 放到最右面成为 abc, 取 d 放到最左面成 dabc; 最后 e 放到中间去成为 daebc. 至於 "2021" 这个特别的设计的数可以用 ..+ x*4 + y*3 + z*2 这样的计算来映对到自然数的数列上去. 
没错了, 如求 4 个数的 4! = 24 个排列, 第 18 个排列可以这样求得, 18 除 2, 余数是 0, 所以第二个数放在第一个数的左面; 然后商 9 再除 3, 余数 0, 所以第三个数於在头两个数的最左; 最后 3 除以 4, 余数是 3, 因此第四个数要放在前三个数的第 4 个空位, 也就是最右面. 利用这个方法, 你就不必先求出整个排列才能开始计算. 尽管这好像牺牲了时间, 但省下了大量的空间. 你完全可以算出 1000 个数的最大排列方法, 纵使那可能要用去几个月的运算. 你更高兴的是用这个方法, 你可以把整个计算拆开成为一个一个的部份: 譬如说求 10! = 3628800 个排列, 你大可以把 1 到 1000000 让一部电脑做, 1000001 到 2000001 让另一部来做 ... 大家的工作并不重覆, 这等於实现并行运算了! 啊哈! 妙极了! 
忽然你灵光一闪, 对了, 这个不正是 permute4.py 的算法吗! 你昨天还久思不得其解呢, 现在你已经完全明白了. 呜, 虽然这么好的算法原来不是你原创的, 但是你仍然异常兴奋. 因为你的思路竟和那些大牛们互相吻合. 你渐渐记起了当你还在玩 DOS 游戏机的年代, 曾有个古怪的人向你吹嘘过某个电脑扑克游戏中用了一个威力很大的洗牌法, 多么的快而且公平, 不必怕黑客们用已知的随机数表来出千. 现在你猜到了, 那个算法很可能就是眼下这一个了. 有 52 张牌, 如果要预先算出 52! 个排列才能洗牌可真要命呢. 
你觉得舒服多了, 你整理了一下程式, 打算把结果告诉大家. 然而刚才的不安感又重新来袭. 你再看了一次最后也应该是最棒的程式, 心中安慰自己道: "千万不要跌进低等程式员的的陷阱, 他们疯也似的不断追求, 郤从来不知道自己的目标, 也不知道什么才是好. 完美的设计不在于你无 法添加新的功能, 完美的设计是再也不能精简现有的功能." 你觉得 permute7.py 已迫近了这一个 极限. 但你内心深处并没有因此而舒坦开来, 一种悬空的感觉自足下升起. 也许是你太累了, 于是 者你决定闭目养神数分钟再开始上网, 可惜你很快地迷迷糊糊地进入了梦境. 
待续... 
终篇:
你做了一个梦, 梦中你看到阿凡提骑著他那出名的毛驴来到你面前并向你提出挑战: "除非你解答了我的难题,不然我的驴子会不停在你耳边嘶叫令你无法睡好! 问题是: 把数字 56789 放到 [][][]*[][] 里得出最大的的乘积...." 你发出会心的微笑, 正想祭出你的 permute7.py 之时忽然想起阿凡提是不可能懂得电脑编程的! 你心中登时凉了一大截: 阿凡提的方法一定不必用电脑算出所有的排列方法, 并很快的得知答案的. 随著一声震天的驴嘶, 你惊醒了, 发现原来你伏在电脑桌上睡去了, 不小心压著了键盘上的方向键而令你的电脑发出了痛苦的 BEEP 声. 
回想梦境, 你打算暂时离开电脑, 回到问题本身上来: 怎样才能"看"出最大的乘积呢 ? 
你拿出纸笔, 开始计算: 
假设五个数为  [a][b][c]*[d][e], 展开的话成为 
 
  a * 100 * d * 10 
+ a * 100 * e * 1 
+ b * 10  * d * 10 
+ b * 10  * e * 1 
+ c * 1   * d * 10  
+ c * 1   * e * 1 
 
这个可以写成一个矩阵: 
 
      d    e 
a  1000  100 
b   100   10 
c    10    1 
你这样想到: 在整个答案中, a 带来的页献是一个百位数加上一个十位数, 而 d 的页献是一个百位数加十位数加个位数, 因此 d 要比 a 更重要. 要取得最大的积则一定要把 56789 中最大的 9 放在 d 的位置, 然后是 a, 如此类推. 
为了方便计算,你干脆用对数来记数 100 = 10e2, 用 2 来代表好了, 因此: 
   d e  
a  3 2 
b  2 1 
c  1 0 
计算每一行或列的和, 把它称为该数的基值, 我们得到 
a = 5, b = 3, c = 1, d = 6, e = 3. 
咦? b 和 e 的基值是一样的, 怎么办! 
你思考著: "啊哈! 因为我们用了对数, 而 log(1) = 0 因此把 b 和 e 之间的微小分别给忽略了!" 好吧, 试把每个数都加大一个, 得到: 
   d e 
a  4 3 
b  3 2 
c  2 1 
这样基数变成了: a = 7, b = 5, c = 3, d = 9, e = 6. 这些基数代表了该位置的重要性, 可以按大小分予不同的数字. 
好, 按基数的大小来分配数字你得到了 865 * 97. 一对答案, 哟! 不一样! 正确解是 875 * 96. 哪里不对了呢? 仔细分析下来, 你发现 b 和 e 互换了. 换的原因是这样的: 
b 的页献: b * d * 100 + b * e * 10 e 的页献: e * a * 100 + e * b * 10 + e * c 
粗看的话 e 的页献要大一些, 但因为我们把 9 配给了 d 而 8 配给了 a, 因此最终的结果是 b 的实际页献要比 e 大. 由於 e 和 b 的基数只相差在 e * c 这个个位数乘积上, d 和 a 之间的分配结果把这个小的差异覆盖掉了. 
你考虑著: "要把这样的覆盖也算上去的话, 也许可以做一个二阶基数. 如 b * d 的基数是 100, 但是由於 d 的基数为 9, 那 b 的二阶基数可以算成 9, 代表和 b 相关的是一个较为重要的数; 同样 e * a 的基数是也是 100 但由於 a 的基数只是 7, 因此 e 的二阶基数只是 7 而已. 这样就可以得出 b 要比 e 更重要了." 
於是你有了一个想法: 先写出相关矩阵, 然后计算每个数的基数和二阶基数, 再进行排序, 当两个基数很接近时就用二阶基数来判别哪个较重要. 嗯, 你觉得自己聪明极了, 於是开始验算, 但很快又发现其实 b 和 e 的二阶基数原来也是一样的!! 大家都是 15. 也许我们要用一个三阶基数才能分辨他们. 
你又想了一些新的二阶基数的定义, 有些的确给出正确的答案, 但你渐渐觉得这一切并不很妥当. 因为就算能计出 56789, 但是在更多的排列, 如 7 位数甚至 9 位数的排列你怎样保证答案也一定准确呢, 而两个基数到底怎样才算是比较接近呢? 仔细审视你的方法, 用对数来表示乃至直接相加来求所谓的基数统统都是即兴的, 毫不严谨. 或者要真正解决他们必需要把每一种情况都算进来, 而那样做的话必然要计算 n! 那么多次! 说到底还是要算排列的. 
你有些失望, 但暗中觉得松了一口气, 因为到底是 permute7.py 得到最后的胜利. 你伸了一下懒腰, 原来天都快亮了. 这时你感到有些饿, 便去拿了半个凉馒头, 冲了一些可可. 你对著空空的萤光屏, 静静地坐了大概十分钟, 然后答案进入你的脑海, 谜团被解开了. 
你的方法是求出所有位置的"重要性"(用你的语言就是求基数), 然后依次把最大的数字分配给最重要的位置. 但是位置的重要性是和其他位置纠缠在一起的, 因此一次过算出所有位置的重要性必须考虑大量不同的组合排列, 并不实际. 
但是, 我们其实可以每次只求第一个最大的基数的位置 (abc*de 的情况下最大的基数是 d), 这个最大的基数是没有争议的. 当求得这个位置时, 干脆把最大的数字放到该位子上, 然后再求一次基数, 找出接下来最大的位子, 这个位子也是无可争议的. 如此一来, 原来求 5 个数字的全排列成就简化为 5 次简单的回圈. 一个求 Factorial(n) 的问题变成了 n 次循环! 
啊哈! 
你精神大好, 从另一个角度切入: 
假如 5 个数字一样, 11111, 最大的乘积只能是 111 * 11, 现在容许改大一个数, 改哪个会使结果最大 ? 
211 * 11, 121 * 11, 112 * 11, 111 * 21, 111 * 12 ? 答案是 111 * 21, 也就是 d 的位置. 好, 把 d 替换成 9. 
问题变成 5 个数字, 111 * 91, 改一个数(除了 9), 改哪一个 ? 
211 * 91, 121 * 91, 112 * 91, 111 * 19 ? 答案是 211 * 91, 也就是 a 的位置. 好, 替换成 8. 
依此类推, 答案正正是 875 * 96. 
你重开电脑, 很快地把新方法输入程式, 并改名为 wise.py. 
    1 def solve(seq,where):
    2   n = len(seq)
    3   seq.sort()
    4   seq.reverse()
    5   table = [ [] for i in range(n) ]
    6   left, right = where, n - where
    7   leftr = long('1'*left)
    8   rightr = long('1'*right)
    9   flag=[]
   10   for item in [ int(x) for x in seq]:
   11     for i in range(left):
   12       table[left-i-1] = (leftr + 10**i) * rightr
   13     for i in range(right):
   14       table[right-i+where-1] = leftr * (rightr + 10**i)
   15     for i in flag:
   16       table[i] = 0
   17     tablesorted = table[:]
   18     tablesorted.sort()
   19     maxindex = table.index(tablesorted[-1])
   20     if maxindex >= where:
   21        rightr = rightr + (item-1) * 10**(right-maxindex+where-1)
   22     else:
   23        leftr = leftr + (item-1) * 10**(left-maxindex-1)
   24     flag.append(maxindex)
   25     #print maxindex, leftr, rightr
   26   return leftr, rightr
   27 
   28 import sys
   29 leftr, rightr = solve(list(sys.argv[1]),int(sys.argv[2]))
   30 print "Maximum at", leftr,rightr, ',product', leftr*rightr
你验算了一下结果, 完全正确! 这时你好奇地再次 time 了一下程式的速度 
$time python permute7.py 123456789 5 
Got 181440 items. 
Maximum at 875319642 ,product 843973902 
 
real    0m7.827s 
user    0m7.650s 
sys     0m0.180s 
 
$ time python wise2.py 123456789 5 
Maximum at 87531 9642 ,product 843973902 
 
real    0m0.042s 
user    0m0.010s 
sys     0m0.030s 
哇! 快了近两百倍! 当然了. 如果算更多位的排列会快更多, 因为 wise.py 跳离了 n! 的限制. 
你现在觉得舒服多了. 你真的解了这个问题. 你不再怕有人会写出更快 10 倍的程式了. 你既有了"聪明"的答案 (软解) 来对付阿凡提和他的驴子, 而在硬解方面, 你也自信有世界第一流的排列产生器. 你完全满足了, 你不再感到疲累, 心中疑犹一扫而空. 这时你身体感到一阵震栗但心中却喜乐无穷, 你第一次感受到了编程之道的洗礼. 并且, 你学会了所有程式大师都有的态度: 我没法用中文来形容, 这种态度叫做 "to hack". 你知道只要你熟练并保持这种态度来面对生命中的难题, 你很快就可以满师出山了. 
你最后一次浏览了一下你的程式码, 发现在 wise.py 中, 其实每一个循环完成后, 最重要的位置和最次要的位子都是不容争议的, 因此大可放心地替换两个数字而不是一个, 那程式可以再快一倍. 不过你觉得现在己经很够了, 你颇有禅机地自言自语道: "我已经找到明月,再纠缠只下去只是妄执於指月的手而已." 你熟练地登出系统并关上电脑, 你知道这次你可以真正安心地睡一觉了. 
哎哟! 天已亮了, 今天是礼拜一, 你要上班的. 喔! 又要被老板说上班一条虫, 下班一条龙...... 惨....... 
全篇完. 
课后检讨:
一) 在上面的故事中,我们看到了解决编程问题的五个方法. 
1. 把问题规范成一个普遍的形式,这样更容易和别人交流以及找相关资料. 
2. 自己尝试找答案. 
3. 在网上搜寻更好的答案. 
4. 想一个方法来打败这个更好的答案. 
5. 翻查教科书或是文献,从基本开始思考有没有最好的解.这些书能被选成教本一定有它的原因. 
6. 研究问题的特殊情况, 也许会有别出心裁的巧妙方法. 
二) 故事中每个程式都只有二三十行大小,说明 Python 语言表达力强且语意很浓缩, 做为快速开发或是测算自己的想法都是非常好的. 
三) Python 程式浓缩之余,它的语言也异常的清晰.回看上面的程式,你会发现它们全都不难明白.这说明 Python 程式更加容易维护. 
四) 在故事中,我们有很大的篇幅是在讨论方法而只有小部份是在描述 Python 的语言特性.这证明 Python 更适合用来教授编程的概念. 事实上, Python 的作者 Guido 和很多人都认为 Python 是电脑教育的首选语言. 教师可以让学生静静地思考,学通运算的法则; 而不是上来就疯狂地敲打键盘,并要记住一大堆电脑语言的古怪特徵. 
五) 整个故事围绕於算法的改进而较少碰到 Python 程式的优化问题. 也许在续集中(如果有的话), 我们要尝试一下在固定的算法及尽量少改动程式码的条件下, 提高 Python 程式的效率. 我暂时想到的方法包括: 
1. 利用较新和较快的语法. 如 yield, generator. 
2. 用 Python 的自带优化选项以及内建模组. 
3. 用第三方的扩展模组, 如 Numpy, Scipy. 
4. 用编译方式代替解释, 如 freeze, py2exe. 
5. 用 JIT 类的方法, 如 Psyco. 
6. 用 Thread, 在多 CPU 的机器上平行运算. 
7. 最后一样要大改程式了, 用 C 来做扩展. 
8. 更有 'to hack' 感觉的, 修改 Python 主干程式, 加入像 string.reverse() 这样的辅助函数. 
六) 文中所用的测试硬件: 
CPU: Pentium III 866 RAM: 128 MB 
文中所用的测试软件: 
Slackware Linux: 9.0 Linux Kernel: 2.4.2 GCC: 3.2.2 Python: 修改过的 2.1.3 
七) 啃凉馒头对脑筋有帮助. 
八) 如果你能想到更好的方法, 欢迎联络本人: glace_at_chinesepython.org