【C++实现】五大常用算法之一：分治算法（实例：汉诺塔）

求解思想：大而化小

1、问题拆分成子问题

2、对子问题求解

在汉诺塔游戏中，有三个分别命名为A、B、C得塔座，几个大小各不相同，从小到大一次编号得圆盘，每个原盘中间有一个小孔。最初，所有得圆盘都在A塔座上，其中最大得圆盘在最下面，然后是第二大，以此类推.

先上代码

#include<iostream>
using namespace std;
class Move
{
public:
	void moveGo(int i, int a, int b, int c);
	void display(int i, int a, int b);
private:
	static int count;
};
int Move::count = 1;
void Move::moveGo(int i, int a, int b, int c)
{
	if (1 == i)
	{
		display(1, a, b);
	}
	else
	{
		moveGo(i - 1, a, c, b);
		display(i, a, b);
		moveGo(i - 1, c, b, a);
	}
}
void Move::display(int i, int a, int b)
{
	printf("第 %d 步：移动第 %d 个塔从 %d 根柱子到 %d 根柱子\n", count,i, a, b);
	count++;
}
int main()
{
	Move mo;
	mo.moveGo(4,1,2,3);
	cout << endl;
	system("pause");
	return 0;
}

核心代码

void Move::moveGo(int i, int a, int b, int c)
{
	if (1 == i)
	{
		display(1, a, b);
	}
	else 
	{
		moveGo(i - 1, a, c, b);
		display(i, a, b);
		moveGo(i - 1, c, b, a);
	}
}

思想：

1. 如果只有1个塔，那么把这个塔直接从a移动到  display(1, a, b);
2. 如果有n个塔，把n-1个从a移动到c                    moveGo(i - 1, a, c, b);
3. 然后把剩下的一个从a移动到b                           display(i, a, b);
4. 最后把n-1个从c移动到b                                    moveGo(i - 1, c, b, a);

这样问题就已经求解完了