递归算法求解汉诺塔问题

Hanoi(汉诺)塔问题,这是一个古典的数学问题。古印度有一个梵塔,塔内有3个柱子A,B,C,开始时A柱上套有64个盘子,盘子大的在下,小的在上,有一个老和尚想把盘子从A柱移到C柱,但规定每次只能移动一个盘,且任何时候3个柱子上的盘子都是大盘在下,小盘在上。现在用递归算法来模拟移盘过程。

递归函数的伪算法为如下:
if(n == 1)
直接将A柱子上的圆盘从A移动到C
else
先将A柱子上的n-1个圆盘借助C柱子移动到B柱子上
直接将A柱子上的第n个圆盘移动到C柱子上
最后将B柱子上的n-1个圆盘借助A柱子移动到C柱子上

该递归算法的时间复杂度为O(2的n次方),当有n个圆盘时,需要移动圆盘2的n次方-1次

、、、

include<studio.h>

int main()

、、、

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 原文链接(转载请注明出处)汉诺塔的图解递归算法 起源 汉诺塔(又称河内塔)问题是源于印度一个古老传说的益智玩具。大...
    Dmego阅读 1,601评论 0 0
  • 汉诺塔 汉诺塔问题是递归算法学习的一个经典案例,首先来看下汉诺塔问题的相关描述: 汉诺塔问题起源于一个古老的印度传...
    木人张阅读 1,026评论 0 1
  • 题目描述 在经典汉诺塔问题中,有 3 根柱子及 N 个不同大小的穿孔圆盘,盘子可以滑入任意一根柱子。一开始,所有盘...
    珺王不早朝阅读 884评论 0 0
  • 一、递归算法介绍 这篇文章讲的是一个古老而又经典的汉诺塔问题,他是递归算法的一个很好的应用实例。有关递归函数的介绍...
    IT之旅阅读 1,461评论 0 1
  • 今天感恩节哎,感谢一直在我身边的亲朋好友。感恩相遇!感恩不离不弃。 中午开了第一次的党会,身份的转变要...
    迷月闪星情阅读 10,620评论 0 11