Hanio 算法个人理解

Hanio 算法——分治策略

Hanio 问题是源于印度一个古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。

问题描述

今有 A、B、C 三个塔座，最初在塔座A上有 n 个圆盘，其中这n个圆盘的堆叠顺序是按照大小由大到小、从下到上进行排序。先将 A 上的n个圆盘移动到 C 上。
移动规则：

1. 每次只移动一个圆盘
2. 不允许将大圆盘放在小圆盘上
3. 在满足1、2的情况下，可将圆盘任意移动到A、B、C上。

设计思路

我们先声明Hanio的算法函数，并暂时将此函数看做是一个黑箱。

// 输入：塔盘A、 塔盘B、 圆盘个数n
// 功能：将塔盘A中n个元素按原始顺序移动到塔盘B上
void Hanio(A,B,n);

这是一道典型的 分治策略 算法：
我们先回顾一下 分治策略 的 设计思想 ：

1. 将原问题划分或归结为规模较小的子问题
2. 递归或迭代求解每个子问题
3. 将子问题的解综合得到原问题的解

在划分为子问题的过程中一般有 对半划分 和 等差划分 方式。我们再看Hanio这个问题，对半划分将n个问题划分为2个 n/2 子问题不合适，而在每次递归或迭代中将n个问题划分成 n - 1 个和 1 个子问题则可巧妙地设计出Hanio问题的解决途径。

如图，在初始状态下，我们将 塔盘A 中的 n 个圆盘化为 n - 1 和 1 两个部分，最底层的圆盘为 1 个子问题，而上面的 n - 1 个圆盘构成 n - 1 个子问题。

将n-1个子问题看成一个整体后，此时就相当于A盘上仅有两个盘，我们很容易就能找出解决的方法。

1. 第一步：将A中的n-1个圆盘（n-1个子问题）整体移动到B上；
2. 第二步：将A中最后的一个圆盘（1个子问题）移动到C上；
3. 第三步：最后再将B中的n-1个圆盘（n-1个子问题）移动到C上。

这样就将A中的圆盘按原来的顺序移动到了C上。
前面我们已经定义了函数 Hanio(A, C, n) 的功能: 将塔盘A中n个元素按原始顺序移动到塔盘B上。
现在可用函数来表示上面的步骤：

1. void Hanio(A, C, n)

2. 	Hanio(A, B, n-1)			将A中的n-1个圆盘（n-1个子问题）整体移动到B上
   

3. 	Move(A, C)					将A中的一个圆盘移动到C上
   

4. 	Hanio(B,C)					将B中的n-1个圆盘（n-1个子问题）移动到C上
   

而n - 1个子问题又会继续归约，将原问题归结为n-2的4个子问题，继续……当子问题规模为1时，也就是只有一个圆盘时，此时不能再继续划分子问题，归约截止，而对于一个圆盘只需直接移动到目标塔盘即可，即直接使用移动函数 Move(A, C) 。

	// 截止条件
	if (n == 1)		Move(A, C);

最终回归的过程中规模1 到 n-1 陆续组合两个子问题的解，直到规模为n。
我用栈stack来实现塔盘。

#include <stack>
#include <iostream>
using namespace std;

static stack<int> B;	// 辅助塔盘

// 移动，将A的栈顶元素移动到C
void Move(stack<int>& A, stack<int>& C)
{ 
   
	C.push(A.top());
	A.pop();		// 出栈
}

// Hanio 算法，将A中的元素按原来的顺序移动到C
void Hanio(stack<int>& A, stack<int>& C, int n)
{ 
   
	if (n == 1)		// 截止条件
		Move(A, C);
	else { 
   
		Hanio(A, B, n - 1);
		Move(A, C);
		Hanio(B, C, n - 1);
	}
}
// 从栈顶至栈底打印元素信息
void StackPrint(stack<int> s)
{ 
   
	while (!s.empty()) { 
   
		cout << s.top() << ends;
		s.pop();
	}
	cout <<  endl;
}

int main()
{ 
   
	stack<int> A;	// 初始盘 
	stack<int> C;	// 目标盘
	// 初始化盘A为5,4,3,2,1
	for (int i = 5; i > 0; --i)
		A.push(i);

	Hanio(A, C, A.size());

	StackPrint(C);
	return 0;
}

我们将A初始化为：1,2,3,4,5（由栈顶到栈底）
最终我们输出C的结果也为：1,2,3,4,5

总结

设 n 个盘子的移动次数为 T(n)

1. T(n) = 2 T(n-1) + 1
2. T(1) = 1
3. 可得：T(n) = 2ⁿ - 1

深入理解分治策略的中心思想：

1. 原问题可以划分或归约为规模较小的子问题
2. 子问题规模足够小时可以直接求解
3. 递归或迭代实现