Question

汉诺塔问题的递归求解算法,并分析算法的时间复杂性

RT

Answer 1

void Hanoi(int n, char a, char b, char c)
{
if(n==1) //只有一个盘子，直接移动
printf("move %c to %c\n", a, c);
else
{
Hanoi(n-1, a, c, b); //将n-1个盘子从a柱移动到b柱
printf("move %c to %c\n", a, c); //将最后一个盘子从a柱移动到c柱
Hanoi(n-1, b, a, c); //将n-1个盘子从b柱移动到c柱
}
}时间复杂度下限是O(2n)

Answer 2

#include<iostream>
using namespace std;
int sum=0;
void hanoi(int n,char A,char B,char C)
{
if(n==1)
{
cout<<"将第"<<n<<"块"<<"从"<<A<<"塔"<<"移到"<<C<<"塔"<<endl;
sum++;
}
else
{
hanoi(n-1,A,C,B);
cout<<"将第"<<n<<"块"<<"从"<<A<<"塔"<<"移到"<<C<<"塔"<<endl;
sum++;
hanoi(n-1,B,A,C);
}
}
void main()
{
int n;
cin>>n;
hanoi(n,'A','B','C');
cout<<"一共移了"<<sum<<"次"<<endl;
system("pause");

}

时间复杂度O(2^n)