问题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);
}
Comments NOTHING