C++汉诺塔的递归与非递归程序

汉诺塔问题

递归实现

#include <iostream>
using namespace std;


void HanoiMove(int n, char a, char b, char c);

int main()
{
	int n;
	cin >> n;
	HanoiMove(n, 'a', 'b', 'c');

}

void HanoiMove(int n, char a, char b, char c)
{
	if (n == 1)
	{
		printf("%c -> %c\n", a, c);
		return;
	}
	else
	{
		HanoiMove(n - 1, a, c, b);
		printf("%c -> %c\n", a, c);
		HanoiMove(n - 1, b, a, c);
	}
}

下面是堆栈的实现过程。

过程如图所示，注意入栈的顺序和递归的顺序是相反的

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

class node
{
public:
	int n;
	char a, b, c;

	node(int n_,char a_,char b_, char c_):n(n_),a(a_),b(b_),c(c_){}
};

int main()
{
	int n;
	cin >> n;
	stack<node> s;
	s.push(node(n, 'a', 'b', 'c'));
	while (!s.empty())
	{
		node t = s.top();
		s.pop();
		if (t.n == 1)
		{
			printf("%c -> %c\n", t.a, t.c);
		}
		else
		{
			s.push(node(t.n - 1, t.b, t.a, t.c));
			s.push(node(1, t.a, t.b, t.c));
			s.push(node(t.n - 1, t.a, t.c, t.b));
		}
	}

}