习题：使用栈解决汉诺塔问题

问题1：汉诺塔

汉诺塔是递归算法的经典题目啦，想清楚递归的实质之后其实很简单的，函数就是三行代码

void towersOfHanoi(int n, int x, int y, int z) {
	if (n > 0) {
		towersOfHanoi(n - 1, x, z, y);
		cout << "把" << x << "顶的元素移到" << y << endl;
		towersOfHanoi(n - 1, z, y, x); 
	}
}

用栈并不能给算法带来什么优化，因为这个递归算法就是汉诺塔问题的实质了，没有更优解法了，用栈只不过是更好模拟移动的过程，能让我们知道每一步三个杆子上分别是哪几个圈。这里只实现了移动的是几号盘，如果要每步输出 三个杆子上分别是哪几个圈，需要在栈的定义处写一个输出所有元素的函数。

#include <iostream>
#include "stack.h"
using namespace std;
void towersOfHanoi(int n, int x, int y, int z);
void moveAndShow(int, int, int, int);
void solve_hanoi(int n);

arrayStack<int> tower[4];
int main()
{
	solve_hanoi(4);
}

void moveAndShow(int n, int x, int y, int z) {
	if(n > 0){
		moveAndShow(n - 1, x, z, y);
		int d = tower[x].top();
		tower[x].pop();
		tower[y].push(d);
		cout << "把塔" << x << "的" << d << "号盘移到了塔" << y << endl;
		moveAndShow(n - 1, z, y, x);
	}
}

void solve_hanoi(int n) {
	for (int d = n; d > 0; d--) {//初始化一号塔
		tower[1].push(d);
	}
	moveAndShow(n, 1, 2, 3);
}