Python基于递归算法实现的汉诺塔与Fibonacci数列示例

本文实例讲述了Python基于递归算法实现的汉诺塔与Fibonacci数列。分享给大家供大家参考，具体如下：

这里我们通过2个例子，学习python中递归的使用。

1. 找出Fibonacci数列中，下标为 n 的数（下标从0计数）

Fibonacci数列的形式是这样的：0,1,1,2,3,5,8,13……

① 使用while循环，python2代码如下：

def fib(n):
  a,b=0,1
  count=0
  while count<n:
    a,b=b,a+b
    count=count+1
  print a

运行结果如下：

>>> fib(0)
0
>>> fib(1)
1
>>> fib(2)
1
>>> fib(3)
2
>>> fib(4)
3
>>> fib(5)
5

② 使用递归（递归必须要有边界条件），python2代码如下：

def fib(n):
  if n==0 or n==1:#递归的边界条件
    return n
  else:
    return fib(n-1)+fib(n-2)

运行结果如下：

>>> fib(0)
0
>>> fib(1)
1
>>> fib(2)
1
>>> fib(3)
2
>>> fib(4)
3
>>> fib(5)
5

递归是最能表现计算思维的算法之一，我们以f(4)为例，看一下递归的执行过程：

同一程序，使用递归虽然程序简洁，但递归的执行效率要比循环低，系统的资源消耗比循环大。因为递归是一层一层地往里面调用，结束后又一层一层地返回，所以递归的执行效率并不高。那为什么还要使用递归呢？因为有一些问题，我们找不到非常明显的循环方案，但容易找到明显的递归方案。比如说著名的汉诺塔问题。

2. 汉诺塔

下图是一个简化版的汉诺塔游戏，只有4个盘子：

汉诺塔游戏规则如下：

python2代码如下：

def hanoi(a,b,c,n):
  if n==1:#递归结束条件
    print a,'->',c
  else:
    hanoi(a,c,b,n-1)
    print a,'->',c
    hanoi(b,a,c,n-1)

运行结果：

>>> hanoi('A','B','C',1)
A -> C
>>> hanoi('A','B','C',2)
A -> B
A -> C
B -> C
>>> hanoi('A','B','C',3)
A -> C
A -> B
C -> B
A -> C
B -> A
B -> C
A -> C

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

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

您可能感兴趣的文章:

  • 使用python实现递归版汉诺塔示例(汉诺塔递归算法)
  • python实现汉诺塔递归算法经典案例
  • python装饰器与递归算法详解
  • Python基于递归算法实现的走迷宫问题
  • python实现汉诺塔方法汇总
  • python益智游戏计算汉诺塔问题示例
  • Python递归实现汉诺塔算法示例
  • 用Python实现斐波那契（Fibonacci）函数
  • python求斐波那契数列示例分享
  • python实现斐波那契数列的方法示例
  • Python打印斐波拉契数列实例
赞 (0)

相关推荐

  • Python打印斐波拉契数列实例

    本文实例讲述了Python打印斐波拉契数列的方法.分享给大家供大家参考.具体实现方法如下: #打印斐波拉契数列 #!/usr/bin/python def feibolaqi(n): if n == 0 or n == 1: return n else: return feibolaqi(n-1) + feibolaqi(n-2) num = int(raw_input('please input a int:')) if num >= 0: print 'feibolaqi(%d) is %d

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

    本文实例讲述了Python递归实现汉诺塔算法.分享给大家供大家参考,具体如下: 最近面试题,面试官让我5分钟实现汉诺塔算法(已然忘记汉诺塔是啥). 痛定思痛,回来查了一下汉诺塔的题目和算法.题干与实现如下: A基座有64个盘子,大在下小在上,每次移动一个盘子,每次都需要大在下小在上,全部移动到B基座,C基座为辅助基座. # -*- coding:utf-8 -*- # 汉诺塔回溯递归实现 # 假设参数中初始杆为a,借助杆为c,阶段终止杆为b # 第一步,a状态借助b移动到c # 第二步,a移动到

  • python实现斐波那契数列的方法示例

    python实现斐波那契数列的方法示例

    介绍 斐波那契数列,又称黄金分割数列,指的是这样一个数列:0.1.1.2.3.5.8.13.21.--在数学上,斐波纳契数列以如下递归的方法定义: F(0)=0,F(1)=1,F(n)=F(n-1)+F(n-2)(n≥2,n∈N*) . 1. 元组实现 fibs = [0, 1] for i in range(8): fibs.append(fibs[-2] + fibs[-1]) 这能得到一个在指定范围内的斐波那契数列的列表. 2. 迭代器实现 class Fibs: def __init__

  • python实现汉诺塔方法汇总

    学习python遇到的第一个问题:汉诺塔问题的实现.首先是不知道什么是汉诺塔问题,然后是不知道怎么实现.于是百度了下,结果如下: 汉诺塔:汉诺塔(又称河内塔)问题是源于印度一个古老传说的益智玩具.大梵天创造世界的时候做了三根金刚石柱子,在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘.大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上.并且规定,在小圆盘上不能放大圆盘,在三根柱子之间一次只能移动一个圆盘 方法一: def move(n,a,b,c) # n=2 if n==1 :

  • python益智游戏计算汉诺塔问题示例

    汉诺塔(又称河内塔)问题是源于印度一个古老传说的益智玩具.大梵天创造世界的时候做了三根金刚石柱子,在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘.大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上.并且规定,在小圆盘上不能放大圆盘,在三根柱子之间一次只能移动一个圆盘. 复制代码 代码如下: times = 0def test(num,a,b,c):    globaltimes    ifnum==1:       print (a,b)       times+=1 else

  • 使用python实现递归版汉诺塔示例(汉诺塔递归算法)

    利用python实现的汉诺塔.带有图形演示 复制代码 代码如下: from time import sleep def disp_sym(num, sym):        print(sym*num, end='') #recusiondef hanoi(a, b, c, n, tray_num): if n == 1:  move_tray(a, c)  disp(tray_num)  sleep(0.7) else:  hanoi(a, c, b, n-1, tray_num)  move

  • python求斐波那契数列示例分享

    复制代码 代码如下: def getFibonacci(num): res=[0,1] a=0 b=1 for x in range(0,num):  if x==a+b:   res.append(x)   a,b=b,a+b return res res=getFibonacci(1000)print(res) #递归a=[0,1]qian=0def fibna(num,qian): print(num) he=num+qian if he<1000:  a.append(he)  qian

  • Python基于递归算法实现的走迷宫问题

    本文实例讲述了Python基于递归算法实现的走迷宫问题.分享给大家供大家参考,具体如下: 什么是递归? 简单地理解就是函数调用自身的过程就称之为递归. 什么时候用到递归? 如果一个问题可以表示为更小规模的迭代运算,就可以使用递归算法. 迷宫问题:一个由0或1构成的二维数组中,假设1是可以移动到的点,0是不能移动到的点,如何从数组中间一个值为1的点出发,每一只能朝上下左右四个方向移动一个单位,当移动到二维数组的边缘,即可得到问题的解,类似的问题都可以称为迷宫问题. 在python中可以使用list

  • python装饰器与递归算法详解

    1.python装饰器 刚刚接触python的装饰器,简直懵逼了,直接不懂什么意思啊有木有,自己都忘了走了多少遍Debug,查了多少遍资料,猜有点点开始明白了.总结了一下解释得比较好的,通俗易懂的来说明一下: 小P闲来无事,随便翻看自己以前写的一些函数,忽然对一个最最最基础的函数起了兴趣: def sum1(): sum = 1 + 2 print(sum) sum1() 此时小P想看看这个函数执行用了多长时间,所以写了几句代码插进去了: import time def sum1(): star

  • 用Python实现斐波那契（Fibonacci）函数

    Fibonacci斐波那契数列,很简单,就是一个递归嘛,学任何编程语言可能都会做一下这个. 最近在玩Python,在粗略的看了一下Learning Python和Core Python之后,偶然发现网上有个帖子Python程序员的进化写的很有意思.于是打算仿照一篇,那篇帖子用了十余种方法完成一个阶乘函数,我在这里会用九种不同的风格写出一个Fibonacci函数. 要求很简单,输入n,输出第n个Fibonacci数,n为正整数 下面是这九种不同的风格: 1)第一次写程序的Python程序员: de

  • python实现汉诺塔递归算法经典案例

    python实现汉诺塔递归算法经典案例

    学到递归的时候有个汉诺塔的练习,汉诺塔应该是学习计算机递归算法的经典入门案例了,所以本人觉得可以写篇博客来表达一下自己的见解.这markdown编辑器还不怎么会用,可能写的有点格式有点丑啦,各位看官多多见谅. 网上找了一张汉诺塔的图片,汉诺塔就是利用用中间的柱子把最左边的柱子上的圆盘依次从大到小叠上去,说白了就是c要跟原来的a一样 废话少说,先亮代码 def move(n, a, buffer, c): if(n == 1): print(a,"->",c) return mov

随机推荐