猫史档案馆

【作品展示】

 

【作品介绍】

以递归加栈的方式实现汉诺塔算法

 

【作品源代码】

'''
以递归加栈的方式实现汉诺塔算法
微信公众号：学思营  xuesying
网址：http://www.5xstar.com https://xuesiying.stem86.com 
2021-10-23
'''

import turtle as t  # 导入海龟画图并把它重命名为t
import time  # 导入时间模块
#初始化海龟
t.title("递归汉诺塔——学思营http://www.5xstar.com")  # 设置标题
t.setup(500, 500)  # 把窗口初始化
t.screensize(400, 400)  # 画布大小


#数据节点
class Node:
    def __init__(self, value):  # 节点初始化
        self.value = value  # 节点的值
        self.pre = None  # 指向前一个节点的指针

#栈


class Stack:
    def __init__(self, name=None, location=None):  # 栈初始化
        '''     
        @name为栈名
        @location为初始位置
        '''
        self.point = None  # 定义栈顶指针
        self.length = 0  # 栈中节点总数
        self.name = name
        self.location = location

    def push(self, value):  # 向栈中压入数据方法
        node = Node(value)  # 把压入栈中的数据包装成栈节点
        if self.point != None:  # 假如栈顶指针不为空
            node.pre = self.point  # 后压入栈的节点指向前一个节点
            self.point = node  # 栈顶指针指向新压入栈的新节点
        else:  # 假如栈顶指针为空
            self.point = node  # 栈顶指针指向栈中唯一的节点
        self.length += 1  # 栈中总数加1
        add(self, node)  # 加入海龟

    def pop(self):  # 从栈中弹出数据方法
        if self.point != None:  # 假如栈顶指针不为空
            node = self.point  # 获得栈顶指针指向的节点
            self.point = node.pre  # 栈顶指针向前一个节点移动
            node.pre = None  # 把栈顶节点的向前指针置为空
            self.length -= 1  # 栈中节点总数减1
            div(self, node)  # 减一节点
            return node.value  # 返回弹出节点的值
        else:  # 如果栈内没有节点
            return None  # 返回空

    def isNone(self):  # 栈的判空方法
        if self.length > 0:  # 假如栈内节点总数大于0
            return False  # 返回False
        else:  # 假如栈内节点总数等于0
            return True  # 返回True

#加入海龟


def add(stack, node):
    stack.location = stack.location[0], stack.location[1]+25  # y坐标上一台阶
    node.value.st()
    node.value.setpos(stack.location)  # 移动海龟

#减1海龟


def div(stack, node):
    stack.location = stack.location[0], stack.location[1]-25  # y坐标下一台阶
    node.value.ht()


#递归,层层分解
def move(n, s1, s2, s3):
    '''
    @n 塔的层数
    @s1 原塔
    @s2 中间塔
    @s3 目的塔
    '''
    if n != 1:
        move(n-1, s1, s3, s2)  # 把底座上面所有盘子移动到中间柱子上
        move(1, s1, s2, s3)  # 移动底座盘子到目标柱上
        move(n-1, s2, s1, s3)  # 把中间柱子上的盘子移动到目标柱子上
    else:  # 当只剩一个盘子时
        #s1 -> s3
        s3.push(s1.pop())  # 把盘子移动到目标柱子上
        print(s1.name, '=>', s3.name)  # 打印移动盘


t.up()  # 提笔

posA = (-100, -100)  # A塔位置
t.setpos(posA[0], posA[1])  # A塔写上标签A
t.write("A", align="center", font=("黑体", 14, "normal"))  # 居中14号
a = Stack('A', posA)  # 声明1个栈——第1根柱子起名叫A

posB = (0, -100)
t.setpos(posB[0], posB[1])
t.write("B", align="center", font=("黑体", 14, "normal"))
b = Stack('B', posB)  # 声明b柱子
posC = (100, -100)
t.setpos(posC[0], posC[1])
t.write("C", align="center", font=("黑体", 14, "normal"))
c = Stack('C', posC)  # 声明c柱子

t.shape("喵")  # 采用正方形海龟
t.seth(90)  # 海龟朝上
t.speed(3)  # 海龟慢速移动


#print("海龟画图初始化完成，3秒后构建7层汉诺塔。")
#time.sleep(3)  # 暂停3秒

temp = t.clone()  # 克隆海龟 最大的碟子，黑色
temp.shapesize(5, 0.5, 1)  # 横向5倍，同向0.5, 边框1
a.push(temp)  # 加入A栈

temp = t.clone()
temp.shapesize(4.5, 0.5, 1)
temp.fillcolor("#FF0000")  # 填充颜色
temp.pencolor("#FF0000")  # 画笔颜色
a.push(temp)

temp = t.clone()
temp.shapesize(4, 0.5, 1)
temp.fillcolor("#FFFF00")
temp.pencolor("#FFFF00")
a.push(temp)

temp = t.clone()
temp.shapesize(3.5, 0.5, 1)
temp.fillcolor("#00FF00")
temp.pencolor("#00FF00")
a.push(temp)

temp = t.clone()
temp.shapesize(3, 0.5, 1)
temp.fillcolor("#00FFFF")
temp.pencolor("#00FFFF")
a.push(temp)

temp = t.clone()
temp.shapesize(2.5, 0.5, 1)
temp.fillcolor("#0000FF")
temp.pencolor("#0000FF")
a.push(temp)

temp = t.clone()
temp.shapesize(2, 0.5, 1)
temp.fillcolor("#FF00FF")
temp.pencolor("#FF00FF")
a.push(temp)

t.ht()  # 隐藏海龟
print("7层汉诺塔初始化完成，3秒后移动。")
time.sleep(3)

n = a.length
move(n, a, b, c)
t.mainloop()

 

【提示】

部分含有Python第三方库相关内容的作品，在海龟编辑器网页端无法运行哦！如遇到这种情况，可以打开下面的链接，下载海龟编辑器客户端：

https://python.codemao.cn