搜索
一切从游戏开始-完整的一个pythontohack实例收藏Hello,引自:ChinesePythonWiki中蟒大杂院完整的一个tohack实例！吾靠玩的最高境界！对glace的仰慕如涛涛江水连绵不断！。。。----------------------------------------------------------------------一切从游戏开始:第二天:守夜人:终篇:课后检讨:一切从游戏开始:故事虚构,是从一个真的游戏再综合新闻组的内容而来.缘起:这是一个晴朗的星期六下午,你悠闲地在网上浏览.忽然间你看到一个留言板上的小游戏.它很简单,问题是:把五个数字56789,放到[][][]*[][],令结果最大.你最先对自己说:这有什么难,把最大的放到最大位数那里就行了.你再心算了一下,也许不对.每个结果要看其他位置上放了什么数才行.你开始觉得有些兴趣了,反正你正在学一种好玩的编程语言,何不练习一下呢?於是你开出你心爱的Python,开始思考:其实我要的是一个程式,我给它各种数字的组合,然后它自动帮我出最大的一个.如果我传入1,1,1,1,1和1,1,1,1,2,它会知道要算111*11和111*12,并求出较大的是111*12并输出这个组合以及其乘积.这个程式并不难嘛.1#calc.py2defcalc(seq):3maximum=04max_item=[]5foriinseq:6product=(i[0]*100+i[1]*10+i[2])*(i[3]*10+i[4])7ifproductmaximum:8maximum=product9max_item=i10elifproduct==maximum:11max_item+=','+i12returnmax_item,maximum1314seq=[[5,6,7,8,9],[5,6,7,9,8]]15max_item,maximum=calc(seq)16printMaximumat,max_item,,product,maximum你试了一下,$pythoncalc.pyMaximumat[5,6,7,9,8],product90160没问题.现在你只要给出所有的排列即可.你打了几行,觉得[5,6,8,7,9]这样打太辛苦了,而且用i[0]*100+i[1]*10...的方法好像太难看了,因此你有必要做一次修改.好,用字串吧.56789,这样输入时较快,而且int(567)*int(89)要好看得多,而且也应该快些.另外你也把程式改得更短,看起来像是个有经验人所写.1#calc.py2defcalc(seq,where):3maximum,max_item=0,[]4foriinseq:5product=int(i[:where])*int(i[where:])6ifproductmaximum:7maximum,max_item=product,i8elifproduct==maximum:9max_item+=','+i10printMaximumat,max_item,,product,maximum1112if__name__==__main__:13seq=[56789,56798]14where=315calc(seq,where)嗯,好些了.那句if__name__==__main__是为了将来你把calc.py做为模组来用时而设的.在别的程式中用importcalc的话那几行就不会运行了.现在你可以随自己的意来解更普遍的问题,比如123放在[]*[][],或是1234567放在[][][][]*[][][]这样的问法.现在你开始输入排列了.56789,56798,56879,56897,..........没多久你又觉得自己太愚蠢了,为什么不叫电脑程式自动产生这些无聊的排列呢?56789一共有5!也就是120种排列方法呢!如果你想算123456789的话,用手输入可能要用去一生的时间!!於是你开始想如何产生排列的算法了.用循环就可以了,不过循环会产生重覆的组合,譬如55555.但我们可以加些条件式进去把重覆项拿走.於是你有了第一个程式解.1#permute1.py2defpermute(seq):3result=[]4forainseq:5forbinseq:6forcinseq:7fordinseq:8foreinseq:9ifa!=banda!=canda!=danda!=eand\10b!=candb!=dandb!=eand\11c!=dandc!=eandd!=e:12result.append(''.join([a,b,c,d,e]))13returnresult1415seq=list(56789)16where=317thelist=permute(seq)18importcalc19calc.calc(thelist,where)你小心地记著用''.join()的方法产生字串要比用a+b+c+d快,同时也认为用importcalc的方式会让你更容易为不同的地方做些速度的微调.你开始运行程式了,你得到%pythonpermute1.pyMaxmumat87596,product84000你成功了.啊哈,你认为可以贴到留言板上去领赏了.经过一些考虑后,你觉得还是要做到更普遍的功能,就是让用户输入排列多少个数字,怎样分割.研究了一下程式,你觉得用循环好像无法达到要求,因为你事前并不知道要排多少个数字,因此你不知道要写多少个循环才够.面对这种情况,你好像只能用递归的方法了.你知道如何求得,例如,5个数字的排列:先挑一个数,有五种选择;当选定了一个数之后挑第二个数时只剩下四个选择,依此类推.因此五个数共有5*4*3*2*1共120个排列.当你面对56789这五个数的排列问题时,你先挑出一个数,例如6,那剩下的便是一个四个数字的排列问题了.就是说,56789的排列可以简化(或是简单复杂化:p)成字头为5的所有排列加上字头为6的所有排列加字头为7的所有排列加字头为8的所有排列再加字头为9的所有排列.想通了这点,你决定用递归函数来写程式,先依次在56789中选出5,然后把剩下的6789当做是一个新的求排列问题再次调用函数,以得到所有以5为字头的排列;再选出6,剩下的5789调用函数.而每次求6789或是5789的排列时再把它简化成另一个求3个数字的排列问题,直到要求的排列只剩下一个数.以下就是你的函数,不过你还不知道它到底是不是正确的,因为写递归函数很易出错,因此你要先试一下.1#permute2.py2defpermute(seq):3l=len(seq)4ifl==1:5return[seq]6else:7res=[]8foriinrange(len(seq)):9rest=seq[:i]+seq[i+1:]10forxinpermute(rest):11res.append(seq[i:i+1]+x)12returnres1314seq=list(1234)15thelist=permute(seq)16thelist=[''.join(x)forxinthelist]17printthelist你运行后得到以下的结果:$pythonpermute2.py['1234','1243','1324','1342','1423','1432','2134','2143','2314','2341','2413','2431','3124','3142','3214','3241','3412','3421','4123','4132','4213','4231','4312','4321']看来是正确的.但有没有办法再快一些呢?你想了半天,终於发现其实你不必等到l=1的时候才有所动作,你可以在l=2的时候就干些事了.因为你知道l=2的话,排列一定是[[0,1],[1,0]]的,这样你起码可以用些力气帮电脑一把.当然如果你把l=3的排列也写出来更好,但写到l=4或以上大可不必了.这种帮它一下的做法在程式优化中的学名是unroll,你隐约记得是学过的.好,现在你有另一个程式了.1#permute3.py2defpermute(seq):3l=len(seq)4ifl=2:5ifl==2:6return[seq,[seq[1],seq[0]]]7else:8return[seq]9else:10res=[]11foriinrange(len(seq)):12rest=seq[:i]+seq[i+1:]13forxinpermute(rest):14res.append(seq[i:i+1]+x)15returnres1617seq=list(12345)18thelist=permute(seq)19thelist=[''.join(x)forxinthelist]20printthelist现在你可以正式测试了.你把permute3.py改了一下,以便可以从命令行取得数字以及分割方法.程式变成下面的样子,同时你也对permute2.py做了相同的修改.1#permute3.py2defpermute(seq):3l=len(seq)4ifl=2:5ifl==2:6return[seq,[seq[1],seq[0]]]7else:8return[seq]9else:10res=[]11foriinrange(len(seq)):12rest=seq[:i]+seq[i+1:]13forxinpermute(rest):14res.append(seq[i:i+1]+x)15returnres1617importsys,calc18seq=list(sys.argv[1])19where=int(sys.argv[2])20thelist=[''.join(x)forxinpermute(seq)]21Print'Got',len(thelist),'items.'22calc.calc(thelist,where)你开始试行了.用time方式来看程式到底运行了多长时间吧.$timepythonpermute2.py567893Got120items.Maximumat87596,product84000real0m0.057suser0m0.050ssys0m0.000s$timepythonpermute3.py567893Got120items.Maximumat87596,product84000real0m0.040suser0m0.030ssys0m0.010s呵,不错.修改了的就是快些.到了这个地步,你开始觉得好奇了.像求排列这样一个常见的问题,不知道别人都是怎样做的呢.也许应该到网上去找找看,或者有一两个已经写好的程式片断可以抄的.你可不想弄错一个原来己经有标准答案的问题.把permute2.py贴上留言板或者会令自己看起来像一个三流的程式设计员,这可是你最不想见到的.於是你在网上到处搜寻.不过似乎都是以递归算法为主的,直至用了一些时间,你终於在ASPN:的网上程式码收集站上看到了这一个片断:1#permute4.py2defpermute(seq,index):3seqc=seq[:]4seqn=[seqc.pop()]5divider=26whileseqc:7index,new_index=divmod(index,divider)8seqn.insert(new_index,seqc.pop())9divider+=110return''.join(seqn)作者声称这个算法的量级是O