一切从游戏开始python.docx
- 文档编号:10797878
- 上传时间:2023-05-27
- 格式:DOCX
- 页数:31
- 大小:34.56KB
一切从游戏开始python.docx
《一切从游戏开始python.docx》由会员分享,可在线阅读,更多相关《一切从游戏开始python.docx(31页珍藏版)》请在冰点文库上搜索。
一切从游戏开始python
一切从游戏开始-完整的一个pythontohack实例收藏
Hello,
引自:
ChinesePythonWiki中蟒大杂院
http:
//www.chinesepython.org/cgi_bin/moingb.cgi/_d2_bb_c7_d0_b4_d3_d3_ce_cf_b7_bf_aa_ca_bc
----------------------------------------------------------------------
完整的一个tohack实例!
吾靠玩的最高境界!
对glace的仰慕如涛涛江水连绵不断!
。
。
。
----------------------------------------------------------------------
一切从游戏开始:
第二天:
守夜人:
终篇:
课后检讨:
一切从游戏开始:
故事虚构,是从一个真的游戏再综合新闻组的内容而来.
缘起:
这是一个晴朗的星期六下午,你悠闲地在网上浏览.忽然间你看到一个留言板上的小游戏.它很简单,
问题是:
把五个数字56789,放到[][][]*[][],令结果最大.
你最先对自己说:
"这有什么难,把最大的放到最大位数那里就行了."你再心算了一下,也许不对.每个结果要看其他位置上放了什么数才行.你开始觉得有些兴趣了,反正你正在学一种好玩的编程语言,何不练习一下呢?
於是你开出你心爱的Python,开始思考:
"其实我要的是一个程式,我给它各种数字的组合,然后它自动帮我出最大的一个.如果我传入1,1,1,1,1和1,1,1,1,2,它会知道要算111*11和111*12,并求出较大的是111*12并输出这个组合以及其乘积.这个程式并不难嘛."
1#calc.py
2defcalc(seq):
3maximum=0
4max_item=[]
5foriinseq:
6product=(i[0]*100+i[1]*10+i[2])*(i[3]*10+i[4])
7ifproduct>maximum:
8maximum=product
9max_item=i
10elifproduct==maximum:
11max_item+=','+i
12returnmax_item,maximum
13
14seq=[[5,6,7,8,9],[5,6,7,9,8]]
15max_item,maximum=calc(seq)
16print"Maximumat",max_item,",product",maximum
你试了一下,
$pythoncalc.py
Maximumat[5,6,7,9,8],product90160
没问题.现在你只要给出所有的排列即可.你打了几行,觉得[5,6,8,7,9]这样打太辛苦了,而且用i[0]*100+i[1]*10...的方法好像太难看了,因此你有必要做一次修改.好,用字串吧."56789",这样输入时较快,而且int("567")*int("89")要好看得多,而且也应该快些.另外你也把程式改得更短,看起来像是个有经验人所写.
1#calc.py
2defcalc(seq,where):
3maximum,max_item=0,[]
4foriinseq:
5product=int(i[:
where])*int(i[where:
])
6ifproduct>maximum:
7maximum,max_item=product,i
8elifproduct==maximum:
9max_item+=','+i
10print"Maximumat",max_item,",product",maximum
11
12if__name__=="__main__":
13seq=["56789","56798"]
14where=3
15calc(seq,where)
嗯,好些了.那句if__name__=="__main__"是为了将来你把calc.py做为模组来用时而设的.在别的程式中用importcalc的话那几行就不会运行了.
现在你可以随自己的意来解更普遍的问题,比如123放在[]*[][],或是1234567放在[][][][]*[][][]这样的问法.现在你开始输入排列了."56789","56798","56879","56897",..........没多久你又觉得自己太愚蠢了,为什么不叫电脑程式自动产生这些无聊的排列呢?
56789一共有5!
也就是120种排列方法呢!
如果你想算123456789的话,用手输入可能要用去一生的时间!
!
於是你开始想如何产生排列的算法了.用循环就可以了,不过循环会产生重覆的组合,譬如55555.但我们可以加些条件式进去把重覆项拿走.於是你有了第一个程式解.
1#permute1.py
2defpermute(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]))
13returnresult
14
15seq=list("56789")
16where=3
17thelist=permute(seq)
18importcalc
19calc.calc(thelist,where)
你小心地记著用''.join()的方法产生字串要比用a+b+c+d快,同时也认为用importcalc的方式会让你更容易为不同的地方做些速度的微调.你开始运行程式了,你得到
%pythonpermute1.py
Maxmumat87596,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.py
2defpermute(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)
12returnres
13
14seq=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.py
2defpermute(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)
15returnres
16
17seq=list("12345")
18thelist=permute(seq)
19thelist=[''.join(x)forxinthelist]
20printthelist
现在你可以正式测试了.你把permute3.py改了一下,以便可以从命令行取得数字以及分割方法.程式变成下面的样子,同时你也对permute2.py做了相同的修改.
1#permute3.py
2defpermute(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)
15returnres
16
17importsys,calc
18seq=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.py567893
Got120items.
Maximumat87596,product84000
real0m0.057s
user0m0.050s
sys0m0.000s
$timepythonpermute3.py567893
Got120items.
Maximumat87596,product84000
real0m0.040s
user0m0.030s
sys0m0.010s
呵,不错.修改了的就是快些.到了这个地步,你开始觉得好奇了.像求排列这样一个常见的问题,不知道别人都是怎样做的呢.也许应该到网上去找找看,或者有一两个已经写好的程式片断可以抄的.你可不想弄错一个原来己经有标准答案的问题.把permute2.py贴上留言板或者会令自己看起来像一个三流的程式设计员,这可是你最不想见到的.於是你在网上到处搜寻.不过似乎都是以递归算法为主的,直至用了一些时间,你终於在ASPN:
的网上程式码收集站上看到了这一个片断:
1#permute4.py
2defpermute(seq,index):
3seqc=seq[:
]
4seqn=[seqc.pop()]
5divider=2
6whileseqc:
7index,new_index=divmod(index,divider)
8seqn.insert(new_index,seqc.pop())
9divider+=1
10return''.join(seqn)
作者声称这个算法的量级是O(n)的.你觉得难以置信,但不妨一试.由於你理解到这个函数每次只传回排列中的某一项,因此你写了个小程式去验算它.
1#test.py
2frompermute4.pyimportpermute
3
4seq=list("1234")
5foriinrange(30):
6printpermute(seq,i),
试验一下:
$pythontest.py
1234124313241423134214322134214331244123314241322314
2413321442133412431223412431324142313421432112341243
1324142313421432
测试显示这个函数没问题.但它怎样做到的呢?
你研究了一下,每个不同的index值都传回唯一的排列,而且大过n!
的index会从头来算起.而且divider每次都要增加一,而列表的排法又是按商余数来重整.唉,不得要领.嗨!
管它呢.反正能用就行了.於是你修改permute4.py,加入一个新的函数求factorial,这样就可以调用permute得到所有的排列.并进行计时.你用了更多的数字,以便速度的差别更明显些.
1#permute4.py
2defpermute(seq,index):
3seqc=seq[:
]
4seqn=[seqc.pop()]
5divider=2
6whileseqc:
7index,new_index=divmod(index,divider)
8seqn.insert(new_index,seqc.pop())
9divider+=1
10return''.join(seqn)
11
12deffact(x):
13f=1
14foriinrange(1,x+1):
15f*=i
16returnf
17
18importsys,calc
19seq=list(sys.argv[1])
20where=int(sys.argv[2])
21n=fact(len(seq))
22thelist=[permute(seq,i)foriinrange(n)]
23print'Got',len(thelist),'items.'
24calc.calc(thelist,where)
$timecpythonpermute3.py12345674
Got5040items.
Maximumat6531742,product4846002
real0m0.461s
user0m0.440s
sys0m0.020s
$timecpythonpermute4.py12345674
Got5040items.
Maximumat6531742,product4846002
real0m0.389s
user0m0.370s
sys0m0.010s
哇!
的确不是盖的.很好,而且现在你知道了别人不知的新答案.就把它贴上去罢.就在你决定的时候按钮之际,你到底犹豫了:
"我对这个算法不是很了,如果别人问起的话怎样解答呢?
这会让我像个东抄西抄的小偷呢!
不,要不我要明白它的原理,不然就自己做一个比它更好的."你觉得壮志无限.
但是现在已经很晚,你要去睡了.无奈你在床上反覆地思考著更好的方法,你整个晚上都没睡好.
待续......
第二天:
你醒来第一件事,洗脸刷牙.编程爱好者并不一定和终日蓬头垢面同义.然后呢,看看电视报纸,做些公益活动,今天是礼拜天嘛.废话少说,终於你在电脑前坐下,登入了你喜爱的lackware/RedHat/Redflag/Mandrake/Debian/WindowsXP/Chinese2000/DOS/Solaris/AIX/Unicos/OSX[作者按:
请依实际情况增删,但千万拜托不要把SCO也加进来],这些都是Python能够运行的平台.
你记起你以前学到递归时听过的话:
任何递归/回溯函数都可以还原成非递归形式的.於是你决定用你自己的方式一试.你默念著求排列的方法,5个数取一个,剩下4个,再取一个,剩下3个....於是你写出一个新的程式,和最初的一个很相像:
1#permute5.py
2defpermute(seq):
3result=[]
4foriinseq:
5seq1=seq[:
]
6seq1.remove(i)
7forjinseq1:
8seq2=seq1[:
]
9seq2.remove(j)
10forlinseq2:
11seq3=seq2[:
]
12seq3.remove(l)
13forminseq3:
14seq4=seq3[:
]
15seq4.remove(m)
16result.append(''.join([i,j,l,m,seq4[0]]))
17returnresult
18
19printpermute(list("12345"))
这个程式依次创建5,4,3,2,1个数的列表,每个都不包括之前被选的数字,然后把5个数合起来完成一种排列.当然,你还有空间做unroll.但现在问题在於,你对程式的要求是事先并不知道要求多少个数字的排列,就是你不知道要写几个for才够.但现在你认为有一个好办法:
既然Python是动态的,它可以执行自己写出来的编码,为什么不叫它自己写个循环程式来完成工作呢?
你觉得这种让程式来为自己写程式的想法很科幻也很妙,而且让你记起了以前听到很多资深程式员爱用的m4宏语言.於是你赶紧试了一个.你认为可以用counter0,counter1,counter2....来代替i,j,l,m...的循环子命名法.
1#permute5.py
2defgenfunc(n):
3head="""
4defpermute(seq0):
5result=[]"""
6boiler="""
7forcounter%iinseq%i:
8seq%i=seq%i[:
]
9seq%i.remove(counter%i)"""
10foriinrange(1,n):
11space=''*i
12head=head+boiler.replace('\n','\n'+space)%(i,i-1,i,i-1,i,i)
13temp=','.join(['counter%i'%(x)forxinrange(1,n)]+["seq%i[0]"%(n-1)])
14head=head+'\n'+space+"result.append(''.join([%s]))"%(temp)
15returnhead+'\nreturnresult\n'
16
17importsys
18functext=genfunc(len(sys.argv[1]))
19printfunctext
20exec(functext)
21printdir()
22thelist=permute(list(sys.argv[1]))
23print'Got',len(thelist),'items.'
运行一下,
sh-2.05b$pythonpermute5.py123453
defpermute(seq0):
result=[]
forcounter1inseq0:
seq1=seq0[:
]
seq1.remove(counter1)
forcounter2inseq
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 一切 游戏 开始 python