汉诺塔问题-蒲公英云

汉诺塔问题

1.汉诺塔问题：如果将n个盘子（由小到大）从a通过b，搬到c，搬运过程中不能出现小盘子在大盘子下面的情况。

分析：这个一个递归问题。只要将n-1个盘子从a通过c（没有中间点肯定不行）搬到b，再将第n个盘子从a搬到c，最后将n-1个盘子从b通过a搬到c。

代码：

一。递归算法b2_hannoi.cpp

#include//汉诺塔

#include
#include

using namespace std;

void move(char x,char y)

{
cout<<x<<”—>”<<y<<endl;
}

void hanoi(int n,char one,char two,char three) //将one上的盘子，借助two搬到three上  
\{  
     if(n==1)  
     move(one,three);  
     else
    \{
       hanoi(n-1,one,three,two);  
       move(one,three);  
       hanoi(n-1,two,one,three);  //类似于函数名的作用，即将这n-1个盘子从two搬到three上  
     \}  
 \}

int main()
{
clock_t start, finish;
double totaltime;
unsigned int n; //都不为负，可增加表示范围
while(1)
{
start=clock();
srand((unsigned)time(0));
n=rand()%10+1;
cout<<”The steps of moving “<<n<<” disks:”<<endl;
hanoi(n,’A’,’B’,’C’);
finish=clock();
totaltime=(double)(finish-start);
cout<<n<<”个盘子的运行时间为”<<totaltime<<”毫秒！”<<endl;
system(“pause”);
}
return 0;
}

1。根据递归算法，设f(n)为n个盘子要移动的次数。那么显然 f(n + 1) = 2*f(n) + 1 -> [f(n + 1) + 1]= 2*[f(n) + 1] f(1) = 1,-> f(n) + 1 = (1 + 1)^n -> f(n) = 2^n - 1。

f(64)= 2^64-1=18446744073709551615 　　

假如每秒钟一次，共需多长时间呢？一年大约有 31536926 秒，计算表明移完这些金片需要5800多亿年，比地球寿命还要长，事实上，世界、梵塔、庙宇和众生都已经灰飞烟灭。

2。在屏幕上是否输出对程序执行时间影响很大，输出时的几个结果10->171 14->2797, 15->5484, 16->11031 毫秒。不输出结果只进行空转30个盘子需要48750毫秒，那么40个盘子需要49921072毫秒，大约13小时

3。在执行递归程序时，cpu运行基本保持在50%

二。非递归算法

非递归算法：

定义从小到大的盘子序号分别为1，2，……n。

可以用一个1到2^n - 1的2进制序列可以模拟出n个盘子的汉诺塔过程中被移动的盘子的序号序列。

即给定一个n，我们通过0到2^n - 1序列可以判断出任意一步应该移动那个盘子。

判断方法：第m步移动的盘子序号是m用二进制表示的最低位bit为1的位置。

证明略。

下面讨论第m步应该移动对应的盘子从哪到哪？

定义顺序为 A->B->C->A, 逆序为C->B->A->C。

性质对n个盘子的汉诺塔,任意一个盘子k(k <= n)k在整个汉诺塔的移动过程中要么一直顺序的，要么一直逆序的。而且如果k在n个盘子移动过程的顺序和k - 1(如果k > 1)以及k + 1(如果k < n)的顺序是反序。

比如：n = 3

1 A->C

2 A->B

1 C->B

3 A->C

1 B->A

2 B->C

1 A->C

其中1的轨迹A->C->B->A>C逆序，2的轨迹A->B->C顺序，3的轨迹A->C逆序

代码：b2_hanoi3.cpp

#include
using namespace std;

int main()
{
int n;
cin >> n;
char order[2][256];
char pos[64];
order[0][‘A’] = ‘B’;
order[0][‘B’] = ‘C’;
order[0][‘C’] = ‘A’;
order[1][‘A’] = ‘C’;
order[1][‘B’] = ‘A’;
order[1][‘C’] = ‘B’; //0是顺序 1是逆序

int index[64]; //确定轨迹的顺序还是逆序
int i, j, m;
for(i = n; i > 0; i -= 2)
index[i] = 1;
for(i = n - 1; i > 0; i -= 2)
index[i] = 0;
memset(pos, ‘A’, sizeof(pos)); //将pos的每个元素置为A

for(i = 1; i < (1 << n); i ++)
{
for(m = 1, j = i; j%2 == 0; j/=2, m ++); //单独一句，怎么就能构造出1 2 1 3 1 2 这样的序列？？
cout << m <<” : “<< pos[m] <<” —> “ << order[index[m]][pos[m]] << endl;
pos[m] = order[index[m]][pos[m]];
}
return 0;
}

汉诺塔问题