Python递归实现汉诺塔算法示例

yipeiwu_com6年前Python基础

本文实例讲述了Python递归实现汉诺塔算法。分享给大家供大家参考,具体如下:

最近面试题,面试官让我5分钟实现汉诺塔算法(已然忘记汉诺塔是啥)。

痛定思痛,回来查了一下汉诺塔的题目和算法。题干与实现如下:

A基座有64个盘子,大在下小在上,每次移动一个盘子,每次都需要大在下小在上,全部移动到B基座,C基座为辅助基座。

# -*- coding:utf-8 -*-
# 汉诺塔回溯递归实现
# 假设参数中初始杆为a,借助杆为c,阶段终止杆为b
# 第一步,a状态借助b移动到c
# 第二步,a移动到b
# 第三步,c借助a移动到b
class Solution:
  def hanoi(self, n, a, b, c):
    global lishan
    if n > 0:
      Solution.hanoi(self, n-1, a, c, b)
      b.append(lishan[n-1])
      a.remove(lishan[n-1])
      Solution.hanoi(self, n-1, c, b, a)
so = Solution()
n = 3
global lishan
lishan = [x for x in xrange(n)]
A = [x for x in xrange(n)]
B = []
C = []
so.hanoi(3, A, B, C)print B

运行结果:

[2, 1, 0]

回溯递归,设计起来还是很有难度的(在没有背过这个题目的前提下)

更多关于Python相关内容感兴趣的读者可查看本站专题:《Python数据结构与算法教程》、《Python函数使用技巧总结》、《Python字符串操作技巧汇总》、《Python入门与进阶经典教程》及《Python文件与目录操作技巧汇总

希望本文所述对大家Python程序设计有所帮助。

相关文章

python中的for循环

python中的for循环

Python for循环可以遍历任何序列的项目,如一个列表或者一个字符串。 语法: for循环的语法格式如下: for iterating_var in sequence:...

Python的Tornado框架实现异步非阻塞访问数据库的示例

tornado即是一个http非阻塞服务器, 就要用起来, 我们将用到tornado框架 ,mongodb数据库 以及motor(mongodb的异步驱动).来简单实现tornado的非...

Python 实现交换矩阵的行示例

如下所示: # TODO r1 <---> r2 # 直接修改参数矩阵,无返回值 def swapRows(M, r1, r2): M[r1],M[r2] = M[r...

Django自定义分页效果

Django自定义分页效果

分页功能在每个网站都是必要的,对于分页来说,其实就是根据用户的输入计算出应该显示在页面上的数据在数据库表中的起始位置。 确定分页需求: 1. 每页显示的数据条数 2. 每页显示页号链接数...

浅谈Python采集网页时正则表达式匹配换行符的问题

如下所示: p1 = r'(?<=<div class="ds_cr">)(.*?)(?=<div id="pageurl">)...