一脸懵逼的算法系列之汉诺塔

背景

法国数学家爱德华·卢卡斯曾编写过一个印度的古老传说：在世界中心贝拿勒斯（在印度北部）的圣庙里，一块黄铜板上插着三根宝石针。印度教的主神梵天在创造世界的时候，在其中一根针上从下到上地穿好了由大到小的64片金片，这就是所谓的汉诺塔。不论白天黑夜，总有一个僧侣在按照下面的法则移动这些金片：一次只移动一片，不管在哪根针上，小片必须在大片上面。僧侣们预言，当所有的金片都从梵天穿好的那根针上移到另外一根针上时，世界就将在一声霹雳中消灭，而梵塔、庙宇和众生也都将同归于尽。

2. 递归算法

分为3个步骤：

(1)将前面63个盘子从 X移动到Y

(2) 将第64个盘子，从X移动到Z

此时我们思考一个问题：我们第64个盘子是不是最大？它是不是已经永远不会动了？
所以我们是不是可以直接把这个东西看作没了？给我回答“是”，要不然我讲不下去。

(3) 将63个盘子从Y移动到Z

代码里面的这一步是：hanio(n-1, y , x , z);
我的理解是：现在我们把第64个盘子看做没了，是不是原本的问题变成了63个盘子，和最初的区别是一开始的64个盘子都在x上面，现在都在Y上面，所以我们把Y当成X去处理不就好了呀。
可以观看一下代码的执行：

n=3	n=2
x —> z
x —> y
z —> y
x —> z
y —> x	x —> y
y —> z	x —> z
x —> z	y —> z

发现没？其实n=3时的后面三步，其实和n=2时的步骤是一样的，只不过x变成了y，x变成了y。
这就是代码中的这一步交换位置的原理所在。

问题一：将X上的63个盘子借助Z移动到Y(拆解思维)

将62个盘子从Y移动到X
将第63个盘子移动到Y
将62个盘子移动到Y

问题二：将Y上的63个盘子借助X移动到Z(拆解思维)

将62个盘子从Y移动到X
将第63个盘子移动到Z
将63个盘子移动到Y上

下面贴出代码：

#include<stdio.h>

void hanio(int n, char x ,char y ,char z)
{
    if(n==1)
    	printf("%c  ---> %c \n",x,z);
    else
    {
    	hanio(n-1,x,z,y);
    	printf("%c  ---> %c \n",x,z);
    	hanio(n-1,y,x,z);
    }
} 


int main(int argc, char const *argv[])
{
	int n ;
	scanf("%d",&n);
	hanio(n,'x','y','z');
	return 0;
}

非递归算法

以后弄明白点再讲吧，先看3blue的汉诺塔视频