利用python实现汉诺塔游戏
作者:howtobecool 发布时间:2021-02-19 03:03:45
标签:python,汉诺塔
本文实例为大家分享了python实现汉诺塔游戏的具体代码,供大家参考,具体内容如下
一.汉诺塔
汉诺塔问题是一个经典的递归问题,对于这个问题,我们可以把它简单的去看成是如何用n-1去表示n。
在A,B,C三个柱子上,我们先假设A柱上只有两个盘子,那么很简单,只需要把最上面的那个盘子移到B柱上,再把A柱上最下面的盘子移到C柱上,最后把B柱的盘子移到C柱就可以了。
假设我们有n个盘子,那么可以把最下面的盘子看成是第n个盘子,而我们要做的是把上面n-1个盘子移到B柱上,再把第n个盘子移到C柱。我们可以把B柱视为主中转站。
在将n-1个盘子移到B柱的过程中,我们需要借助C柱作为分中转站,当完成n-1个盘子的移动时,此时B柱上存在n-1个盘子,而我们接下来要做的,和之前类似,就是借助把n-2个盘子移动到A柱,把第n-1个盘子移动到C柱。在移动n-2个盘子到A柱时,我们同样要借助C作为分中转站。
二.实例代码
import turtle
class Stack:
def __init__(self):
self.items = []
def isEmpty(self):
return len(self.items) == 0
def push(self, item):
self.items.append(item)
def pop(self):
return self.items.pop()
def peek(self):
if not self.isEmpty():
return self.items[len(self.items) - 1]
def size(self):
return len(self.items)
def drawpole_3():#画出汉诺塔的poles
t = turtle.Turtle()
t.hideturtle()
def drawpole_1(k):
t.up()
t.pensize(10)
t.speed(100)
t.goto(400*(k-1), 100)
t.down()
t.goto(400*(k-1), -100)
t.goto(400*(k-1)-20, -100)
t.goto(400*(k-1)+20, -100)
drawpole_1(0)#画出汉诺塔的poles[0]
drawpole_1(1)#画出汉诺塔的poles[1]
drawpole_1(2)#画出汉诺塔的poles[2]
def creat_plates(n):#制造n个盘子
plates=[turtle.Turtle() for i in range(n)]
for i in range(n):
plates[i].up()
plates[i].hideturtle()
plates[i].shape("square")
plates[i].shapesize(1,8-i)
plates[i].goto(-400,-90+20*i)
plates[i].showturtle()
return plates
def pole_stack():#制造poles的栈
poles=[Stack() for i in range(3)]
return poles
def moveDisk(plates,poles,fp,tp):#把poles[fp]顶端的盘子plates[mov]从poles[fp]移到poles[tp]
mov=poles[fp].peek()
plates[mov].goto((fp-1)*400,150)
plates[mov].goto((tp-1)*400,150)
l=poles[tp].size()#确定移动到底部的高度(恰好放在原来最上面的盘子上面)
plates[mov].goto((tp-1)*400,-90+20*l)
def moveTower(plates,poles,height,fromPole, toPole, withPole):#递归放盘子
if height >= 1:
moveTower(plates,poles,height-1,fromPole,withPole,toPole)
moveDisk(plates,poles,fromPole,toPole)
poles[toPole].push(poles[fromPole].pop())
moveTower(plates,poles,height-1,withPole,toPole,fromPole)
myscreen=turtle.Screen()
drawpole_3()
n=int(input("请输入汉诺塔的层数并回车:\n"))
plates=creat_plates(n)
poles=pole_stack()
for i in range(n):
poles[0].push(i)
moveTower(plates,poles,n,0,2,1)
myscreen.exitonclick()
三.结果显示
1.首先,会显示出如下页面:
因此,我们输入汉诺塔层数。
2.turtle库演示结果
来源:https://blog.csdn.net/howtobecool/article/details/88832714
0
投稿
猜你喜欢
- 本文实例讲述了php实现的微信分享到朋友圈并记录分享次数功能。分享给大家供大家参考,具体如下:1.引入JS文件2.通过config接口注入权
- 本文实例讲述了Python有序查找算法之二分法。分享给大家供大家参考,具体如下:二分法是一种快速查找的方法,时间复杂度低,逻辑简单易懂,总的
- 正则表达式,贪婪匹配与非贪婪匹配正则表达式前戏以某app注册页面获取手机号为例. 其有很多校验规则: 国内手机号必须是11位,纯数字,是常规
- 在SQL Server数据库中,有min server memory与max server memory两个内存选项。数据库管理员合理设置这
- Python字典的遍历方法有好几种,其中一种是for...in,这个我就不说明,在Python了几乎随处都可见for...in。下面说的这种
- 与Python标准库模块命名冲突Python的一个优秀的地方在于它提供了丰富的库模块。但是这样的结果是,如果你不下意识的避免,很容易你会遇到
- 本文实例讲述了php+jQuery实现的 * 导航栏下拉菜单显示效果。分享给大家供大家参考,具体如下:首先看看效果图:1.数据配置文件 db.
- 查询一天:select * from table where to_days(column_time) = to_days(now());s
- 本文实例为大家分享了python实现年会抽奖程序的具体代码,供大家参考,具体内容如下发一下自己写的公司抽奖程序。需求:公司年会要一个抽奖程序
- js实现点击掉落特效 先看看效果图 话不多说代码<!DOCTYPE HTML><html><head
- 首先要兼容IE\FF滴然后有一个环境与条件:必须是使用em单位布局。因为这个是利用字号做缩放效果,并且兼容fontSize各项单位,例如px
- 迭代器&生成器在 Python 中,迭代器和生成器都是用来遍历数据集合的工具,可以按需逐个生成或返回数据,从而避免一次性加载整个数据
- 一、 基础使用1.1 logging使用场景日志是什么?这个不用多解释。百分之九十的程序都需要提供日志功能。Python内置的logging
- 初学python,抓取搜狗微信公众号文章存入mysqlmysql表:代码:import requestsimport jsonimport
- 本文实例讲述了Python二叉树的镜像转换实现方法。分享给大家供大家参考,具体如下:问题描述操作给定的二叉树,将其变换为源二叉树的镜像。思路
- 前言这篇文章主要介绍了Go语言使用swagger生成接口文档的方法,希望能够对大家的学习或工作具有一定的帮助,需要的朋友可以参考下。在前后端
- 本文实例讲述了django框架实现模板中获取request 的各种信息。分享给大家供大家参考,具体如下:在做网页程序时,request,re
- 图片轮播滤镜转换效果,只支持ie浏览器<img width="156" height="60"
- lambda 语法lambda 函数的语法只包含一个语句,表现形式如下:lambda [arg1 [,arg2,.....argn]]:ex
- 目录简介Spare data的例子SparseArraySparseDtypeSparse的属性Sparse的计算SparseSeries