很难理解并掌握汉诺塔问题？这里有简单易懂的讲解，点进来总没错

2024-07-17 07:56| 来源: 网络整理| 查看: 265

汉诺塔问题 1. 什么是汉诺塔问题2. 如何写递归举例：递归问题之斐波那契数列 3. 汉诺塔问题的递归思路汉诺塔函数的意思第一部分：终止条件第二部分：距离目标的最近逻辑汉诺塔函数的代码c语言Python 最后

1. 什么是汉诺塔问题

在这里插入图片描述

汉诺塔问题就是将A柱上n个圆全部移动到C上，过程中可以借助B柱，但要始终保持小圆在大圆上面

2. 如何写递归

我们都知道汉诺塔问题一般都是用递归来解决，那么递归到底该怎么写？

博主经过总结后，得出结论：写上终止条件，并将距离目标最近的一层逻辑写出来就是递归！

一定要记住，我们不要深入跟进递归内部，只需将最近的一层逻辑写出来即可。

举例：递归问题之斐波那契数列

先看它的函数代码：

int fib(int n) { if(n==1) return 1; else if(n==2) return 1; else return fib(n-1)+fib(n-2); }

这个求斐波那契数列第n项的fib函数就是由两部分组成：

第一部分就是在n等于1或2时返回1，这是终止条件第二部分我们所要求的fib(n)——即第n项的值就等于第n-1项的值加上第n-2项的值（斐波那契数列的定义）；也就是说fib(n)的返回值就是fib(n-1)+fib(n-2)

就这么简单！

3. 汉诺塔问题的递归思路汉诺塔函数的意思

函数声明如下：

void hanoi(int n, char a, char b, char c)

这个函数的意思就是：将a柱上的n个圆经由b柱移动到c柱上（即将第二个参数上的n个圆经由第三个参数移动到第四个参数上）

(汉诺塔问题需要用递归解决，只要是递归就由上面提到的两部分组成，我们先看第一部分)

第一部分：终止条件

如果柱子上的圆的数量n等于0了，自然也就终止了，那么终止条件就是

if(n==0) return; 第二部分：距离目标的最近逻辑

想要实现hanoi(n, 'A', 'B', 'C')，即实现将a柱上的n个圆经由b柱移动到c柱上，那么就要分三步：

先将a柱上的n-1个圆经由c柱移动到b柱再将a柱上剩下的1个圆（也即最下方最大的圆）移动到c上最后将b柱上的n-1个圆经由a柱移动到c柱上

经过这三步就能将a柱上的n个圆经由b柱移动到c柱上

结合上面所说的汉诺塔函数的意思，我们可以得出：

第一步等同于hanoi(n-1,a,c,b)第二部的移动直接打印移动过程即可第三步等同于hanoi(n-1,b,a,c)

大家可能会问：之后怎么办呢？答案当然是交给计算机了！递归的更深层次的逻辑是不需要我们去想，让代码“飞”一会儿就OK了

（正如斐波那契数列的所求项就是由它的前两项相加得到的，其它的不需要在代码上体现，计算机自己就会帮你搞定了！）

汉诺塔函数的代码 c语言 void hanoi(int n, char a, char b, char c) { if(n==0) return; hanoi(n-1,a,c,b); print("%d:%c -> %c",step++,a,c); hanoi(n-1,b,a,c); }

（step表示第几次移动）

Python def hanoi(n, a, b, c): global step if n==0: return hanoi(n-1,a,c,b) print("{}:{} -> {}".format(step,a,c)) step += 1 hanoi(n-1,b,a,c)

（step表示第几次移动）

这样就搞定了!

最后

如果看完了这篇文章觉博主讲解的还不错的话，能不能麻烦您点上一个宝贵的赞呢？十分感谢大家！

【本文地址】

公司简介

联系我们

今日新闻

推荐新闻

专题文章