汉诺塔问题

刺骨的言语ヽ痛彻心扉 2022-08-20 10:14 228阅读 0赞

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

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

代码：

一。递归算法b2\_hannoi.cpp

\#include<iostream>//汉诺塔

\#include<ctime>  
\#include<math.h>

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 <iostream>  
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;  
\}

![汉诺塔问题][690e573948fa190abdc62_690]

固定序列1 2 1 3 1 2 1

[690e573948fa190abdc62_690]: /images/20220731/087dc84af18d4ff5b90c06bc536929a5.png