汉诺塔算法的非递归演示

数据结构课程设计

设计说明书

汉诺塔算法的非递归演示

学生姓名 学班成

号 级 绩

指导教师

题 目 学生姓名 指导教师评语及成绩 汉诺塔算法的非递归演示 学号 成绩： 教师签名： 年 月 日 答辩教师评语及成绩 成绩： 教师签名： 年 月 日 教研室意见 总成绩： 室主任签名： 年 月 日 注：指导教师成绩60%，答辩成绩40%，总成绩合成后按五级制记入

典例子，已经证明其时间复杂度是O(2n),空间复杂度使O（n）, 实际使用时很容易溢出。给出汉诺塔问题的两个非递归算法，解集递推法和解集树法。解集递推法的时间复杂度和空间复杂度都是O (2n)，该算法的时间复杂度很大，无法实际使用，提出该算法的目的是为了引出解集树法，解集树可以计算出指定的任意一步移动步法，时间复杂度和空间复杂度都是O(n * 2n)和O(1),并证明了汉诺塔问题的空间复杂度是O(1)，系统界面清晰，操作简单，易于为用户所接受。

关键字：汉诺塔；非递归算法；栈；移盘

目 录

1 课题描述 ..................................................................................................................................... 1 2 问题分析和任务定义 ................................................................................................................. 2 3 逻辑设计 ..................................................................................................................................... 3 4 详细设计 ..................................................................................................................................... 7 5 程序编码 ..................................................................................................................................... 8 6 程序调试与测试 ........................................................................................................................11 7 结果分析 ................................................................................................................................... 12 8 总结 ........................................................................................................................................... 13 参考文献 ....................................................................................................................................... 14