习题6_42汉诺塔问题

//汉诺塔问题
//1、2、3共三个直杆，初始时有NUMBER个盘子按照从大到小的顺序
//在1上从底向上摆放，要求将这些盘子按照次序摆放到3杆
//比如1->2表示将1上的最上面一个盘子放到2上，

//汉诺塔问题是2的n次幂级别的时间复杂度啊

//下面给出的是利用六个函数相互之间直接或者间接递归，
//如何利用一个包含有四个参数的函数实现递归？？？
#include <iostream>
#define NUMBER 5
using namespace std;

void H1to2(int);//将1上的所有盘子按照从大到小自底向上的顺序放到2上
void H1to3(int);//将1上的所有盘子按照从大到小自底向上的顺序放到3上
void H2to1(int);//将2上的所有盘子按照从大到小自底向上的顺序放到1上
void H2to3(int);//将2上的所有盘子按照从大到小自底向上的顺序放到3上
void H3to1(int);//将3上的所有盘子按照从大到小自底向上的顺序放到1上
void H3to2(int);//将3上的所有盘子按照从大到小自底向上的顺序放到2上

int count = 0;//记录盘子转移的次数

int main()
{
	cout << NUMBER << "个盘子的汉诺塔问题解决方法如下：" << endl;
	H1to3(NUMBER);
	cout << "转移盘子的次数为：" << count << endl;
	system("pause >> cout");
	return 0;
}

//将1上的所有盘子按照从大到小自底向上的顺序放到2上
void H1to2(int n1to2)
{
	if(n1to2 == 1)
	{
		cout << " 1 -> 2 " << endl;
		count++;
	}
	else 
	{
		H1to3(n1to2-1);
		H1to2(1);
		H3to2(n1to2-1);
	}
}

//将1上的所有盘子按照从大到小自底向上的顺序放到3上
void H1to3(int n1to3)
{
	if(n1to3 == 1)
	{
		cout << " 1 -> 3 " << endl;
		count++;
	}
	else
	{
		H1to2(n1to3 - 1);
		H1to3(1);
		H2to3(n1to3 - 1);
	}
}

//将2上的所有盘子按照从大到小自底向上的顺序放到1上
void H2to1(int n2to1)
{
	if(n2to1 == 1)
	{
		cout << " 2 -> 1 " << endl;
		count++;
	}
	else
	{
		H2to3(n2to1 - 1);
		H2to1(1);
		H3to1(n2to1 - 1);
	}
}

//将2上的所有盘子按照从大到小自底向上的顺序放到3上
void H2to3(int n2to3)
{
	if(n2to3 == 1)
	{
		cout << " 2 -> 3 " << endl;
		count++;
	}
	else
	{
		H2to1(n2to3 - 1);
		H2to3(1);
		H1to3(n2to3 - 1);
	}
}

//将3上的所有盘子按照从大到小自底向上的顺序放到1上
void H3to1(int n3to1)
{
	if(n3to1 == 1)
	{
		cout << " 3 -> 1 " << endl;
		count++;
	}
	else
	{
		H3to2(n3to1 - 1);
		H3to1(1);
		H2to1(n3to1 - 1);
	}
}

//将3上的所有盘子按照从大到小自底向上的顺序放到2上
void H3to2(int n3to2)
{
	if(n3to2 == 1)
	{
		cout << " 3 -> 2 " << endl;
		count++;
	}
	else
	{
		H3to1(n3to2 - 1);
		H3to2(1);
		H1to2(n3to2 - 1);
	}
}

 这上面的就是渣呀，怎么会有这种奇葩的思维

#include <iostream>
using namespace std;

/*递归函数
   从左到右的参数分别为准备移动的盘子数，最初放置这些盘子的桩
   作为临时存放点的桩，最终放置这些盘子的桩*/
void hanoi(int ,char ,char ,char);

int count;//统计进行多少次的转移
int main()
{
	int number;//盘子个数
	cout << "请输入汉诺塔问题中的盘子个数：";
	cin >> number;
	hanoi(number,'A','B','C');
	system("pause >> cout");
	return 0;
}


//将number个盘子从a桩借助b桩转移到c桩
void hanoi(int number,char a,char b,char c)
{
	if(number == 1)
		cout << a << " -> " << c << endl;
	else
	{
		hanoi(number-1,a,c,b);
		cout << a << " -> " << c << endl;
		hanoi(number-1,b,a,c);
	}
}