Python学习二(生成器和八皇后算法)
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了Python学习二(生成器和八皇后算法)，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含3391字，纯文字阅读大概需要5分钟。
内容图文
看书看到迭代器和生成器了,一般的使用是没什么问题的,不过很多时候并不能用的很习惯
书中例举了经典的八皇后问题,作为一个程序员怎么能够放过做题的机会呢,于是乎先自己来一遍,于是有了下面这个ugly的代码
def
table(m, lst):
‘‘‘
绘制m列的棋盘,每行有个皇后旗子
‘‘‘
head = ‘┌‘ + ‘─┬‘ * (m-1) + ‘─┐‘
row = lambda x: ‘│‘ + ‘ │‘ * x + ‘╳│‘ + ‘ │‘ * (m - x - 1)
trow = ‘├‘ + ‘─┼‘ * (m-1) + ‘─┤‘
tail = ‘└‘ + ‘─┴‘ * (m-1) + ‘─┘‘print(head)
for i, n in zip(range(len(lst)), lst):
print (row(n))
print (trow) if i < len(lst) - 1 elseprint (tail)
queens = [0]*8
def rightqueen(lst, m):
‘‘‘判断lst的所有皇后是否与下一行的m位置皇后干涉,不干涉则返回True‘‘‘for i, n in zip(range(len(lst)), lst):
if(n == m or len(lst) - i == m - n or len(lst) - i == n - m):
return False
return True
def calqueen(lst, n):
‘‘‘求解第n个皇后与之前的皇后不干涉
如果第n行成功则求解n+1行,否则求解n-1行且复位n行‘‘‘for i in range(lst[n], 8):
if rightqueen(lst[:n], i):
lst[n] = i
calqueen.count += 1
print(calqueen.count)
table(8, lst[:n+1])
if n < 7: calqueen(lst, n+1)
breakelse:
#如果遍历8个之后仍然没有解则重新求解上一行
lst[n] = 0
lst[n-1] += 1
print(‘求解上一行‘)
calqueen(lst, n-1)
calqueen.count = 0
calqueen(queens, 0)
前面那个table函数只是用来绘制棋盘的,写完后感觉Python确实是很简洁的语言,当然可以更简洁,现在我的代码风格还保留很强的C语言风格,这个转变估计还需要一段时间
说他ugly倒并不是因为他没有使用迭代器,主要的问题在于函数的两个分支都使用了迭代,只有达到第八层时才会结束迭代,这个代码迭代次数要达到100多次,这样多的迭代其内存占用以及运行效率都是不太好的
因此改进版的代码应该是在失败的时候返回运行结果以便减少迭代次数,调整后的代码如下:
def
table(m, lst):
‘‘‘
绘制m列的棋盘,每行有个皇后旗子
‘‘‘
head = ‘┌‘ + ‘─┬‘ * (m-1) + ‘─┐‘
row = lambda x: ‘│‘ + ‘ │‘ * x + ‘╳│‘ + ‘ │‘ * (m - x - 1)
trow = ‘├‘ + ‘─┼‘ * (m-1) + ‘─┤‘
tail = ‘└‘ + ‘─┴‘ * (m-1) + ‘─┘‘print(head)
for i, n in zip(range(len(lst)), lst):
print (row(n))
print (trow) if i < len(lst) - 1 elseprint (tail)
queens = [0]*8
def rightqueen(lst, m):
‘‘‘判断lst的所有皇后是否与下一行的m位置皇后干涉,不干涉则返回True‘‘‘for i, n in zip(range(len(lst)), lst):
if(n == m or len(lst) - i == m - n or len(lst) - i == n - m):
return False
return True
def calqueen(lst, n):
‘‘‘求解第n个皇后与之前的皇后不干涉
如果第n行成功则求解n+1行,否则求解n-1行且复位n行‘‘‘for i in range(8):
if rightqueen(lst[:n], i):
lst[n] = i
calqueen.count += 1
print(calqueen.count)
table(8, lst[:n+1])
if n < 7:
ifnot calqueen(lst, n+1): continuereturn True
else:
#如果遍历8个之后仍然没有解则重新求解上一行print(‘求解上一行‘)
calqueen.count -= 1
return False
calqueen.count = 0
calqueen(queens, 0)
减少了迭代次数后至少程序是比较合理的了,不过在看过使用生成器,迭代器的代码之后还是觉得我对Python以及迭代器编程的感觉太少了,为了增强感觉,合上书按照自己的理解又盲写了一遍,当然代码跟书上的不太一致了,但思想差不多
def
table(m, lst):
‘‘‘
绘制m列的棋盘,每行有个皇后旗子
‘‘‘
head = ‘┌‘ + ‘─┬‘ * (m-1) + ‘─┐‘
row = lambda x: ‘│‘ + ‘ │‘ * x + ‘╳│‘ + ‘ │‘ * (m - x - 1)
trow = ‘├‘ + ‘─┼‘ * (m-1) + ‘─┤‘
tail = ‘└‘ + ‘─┴‘ * (m-1) + ‘─┘‘print(head)
for i, n in zip(range(len(lst)), lst):
print (row(n))
print (trow) if i < len(lst) - 1 elseprint (tail)
def rightqueen(lst, m):
‘‘‘判断lst的所有皇后是否与下一行的m位置皇后干涉,不干涉则返回True‘‘‘for i, n in zip(range(len(lst)), lst):
if(n - m in (0, len(lst) - i, i - len(lst))):
return False
return True
def calqueen(lst, n):
‘‘‘求解第n个皇后与之前的皇后不干涉
只在第八层提交数据,其余每一层都是把本层的所有可能和后面的所有可能相加‘‘‘for i in range(8):
calqueen.total += 1
if rightqueen(lst, i):
calqueen.count += 1
if n == 7:
calqueen.number += 1
print(calqueen.number, calqueen.count, calqueen.total)
yield lst + [i]
else:
for l in calqueen(lst + [i], n + 1):
yield l
calqueen.total = 0
calqueen.count = 0
calqueen.number = 0
for l in calqueen([], 0):
table(8, l)
事实上两个函数的核心代码只有13行,使用in和元组来替代3个条件判断,用迭代器替代对函数返回值的判断,因为如果迭代器为空,则上层调用函数遍历就会失败,自动解决了我原来算法的问题
而且这个程序能够遍历出92个八皇后的解法,虽然我之前的代码改改应该也能实现,但是不会有这么精简
因为生成器的存在,使得迭代器在使用时非常的方便,后期在处理一些需要循环层进迭代的方法时也应该优先考虑生成器,迭代器的方式.
原文：http://www.cnblogs.com/lancky/p/5432600.html
内容总结
以上是互联网集市为您收集整理的Python学习二(生成器和八皇后算法)全部内容，希望文章能够帮你解决Python学习二(生成器和八皇后算法)所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。