汉诺塔问题的递归算法和非递归算法分析

汉诺塔问题的递归算法和非递归算法分析

不想看文字的可以在B站看详细的讲解,点击蓝字->汉诺塔问题的递归和非递归算法

问题描述

相传在古印度圣庙中,有一种被称为汉诺塔(Hanoi)的游戏。该游戏是在一块铜板装置上,有三根杆(编号A、B、C),在A杆自下而上、由大到小按顺序放置n个金盘(依次标号1到n)。游戏的目标:把A杆上的金盘全部移到C杆上,并仍保持原有顺序叠好。操作规则:每次只能移动一个盘子,并且在移动过程中三根杆上都始终保持大盘在下,小盘在上,操作过程中盘子可以置于A、B、C任一杆上。

问题分析(递归算法)

如果A杆上只有一个盘子,则直接将盘子从A杆移至C杆即可。
汉诺塔问题的递归算法和非递归算法分析_第1张图片
如果A上有2个盘子,则需要先把1号盘子挪到辅助杆B上,再把2号盘挪到目标杆C上,最后把B杆上的1号盘挪到C杆上即可完成。
汉诺塔问题的递归算法和非递归算法分析_第2张图片A杆上的盘子数目逐渐增加到n,我们无法直观的得到结果。于是想到将n个盘子看做两部分,一个部分为上层的(n-1)个盘子,另一个部分为最底下的一个盘子。

于是,三步就可以完成移动:
①借助C杆将(n-1)个盘子从A杆移动到B杆;
汉诺塔问题的递归算法和非递归算法分析_第3张图片
在这里插入图片描述
②把n号盘子从A杆移到C杆
汉诺塔问题的递归算法和非递归算法分析_第4张图片在这里插入图片描述
③借助A杆把(n-1)个盘子从B杆移到C杆
汉诺塔问题的递归算法和非递归算法分析_第5张图片
在这里插入图片描述

递归算法:
#include 
using namespace std;	

void hanoi( char A, char B, char C, int n){
	if(n>0)
	{
		hanoi(A, C, B, n - 1);	//将(n-1)个盘子从A移至B
		cout <<n<<" from "<< A << " to " << C << endl;	//将最底下的一个盘子从A移到C
		hanoi(B, A, C, n - 1);	//把(n-1)个从B移至C
	}
}

int main()
{
	int n;
	char a='A',b='B',c='C';
	cin>>n;
	hanoi(a,b,c,n);
}
时间复杂度分析

当规模为n时时间函数为T(n),在代码中,两次调用规模为(n-1)的汉诺塔函数,还有一次输出语句,运算时间为常数n,所以时间函数为T(n)=2*T(n-1)+1。
汉诺塔问题的递归算法和非递归算法分析_第6张图片
汉诺塔问题的递归算法和非递归算法分析_第7张图片
最后求得递归算法的时间复杂度为O(2n)。

问题分析(非递归算法)

汉诺塔问题的递归算法和非递归算法分析_第8张图片
举个例子,当n=3时。因为是奇数,所以杆的摆放顺序为ACB。之后循环进行两步操作。如下图所示:
汉诺塔问题的递归算法和非递归算法分析_第9张图片
图片右上角是用这种规律移动的步骤,可验证与用递归算法移动的步骤完全相同。

代码实现
#include
#include 
using namespace std;
 
char s[4] = { '0','A','B','C'};
stack<int> a[4];

void move(int now,int next){ //用来移动的函数 
		a[next].push(a[now].top());
		printf("%d from %c to %c\n", a[now].top(),s[now], s[next]);
		a[now].pop();
}

int main() {
	int  n;
	cin >> n;
	for (int i = 0; i < n; i++)
		a[1].push(n - i);//把盘子从大到小入栈 
	if (n%2 == 1) {//如果n为奇数则杆的排列顺序为ACB 
		s[2] = 'C'; 
		s[3] = 'B';
	}
	while (1) {
		int next;//用来记录第一步中的下一个杆; 
		for(int i=1;i<=3;i++)//将最小圆盘移动到下一个杆上
			if(!a[i].empty()){
				if(a[i].top()==1){
					if(i==3) next=1;
					else next=i+1;
					move(i,next);//移动 
					break;
				}
			}
			
		if(a[2].size()==n || a[3].size()==n) break;
		
		int other1,other2;//记录第二步中的另外两个杆 
		switch(next){
			case 1:{other1=2;other2=3;break;}
			case 2:{other1=3;other2=1;break;}
			case 3:{other1=1;other2=2;break;}
		}
		if(a[other1].empty())//移动到空杆 
			move(other2,other1);	
		else if(a[other2].empty())
			move(other1,other2);
		else
		{
			if(a[other1].top()<a[other2].top())// 把较小的那个圆盘移动到较大的那个圆盘上
				move(other1,other2);
			else move(other2,other1);	
		}
	}
}

可证明非递归算法的时间复杂度也是O(2n),再次证明了汉诺塔问题的递归算法和非递归算法其实是一回事。
但是严格的证明应该采用数学归纳法,我不会,就不说了。
汉诺塔问题的递归和非递归算法

你可能感兴趣的