画星星高手

It nerver rains but it pours.

关于汉诺塔问题的两种解法

先看一波汉诺塔的介绍(来自百度百科)

汉诺塔:汉诺塔(又称河内塔)问题是源于印度一个古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子,在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定,在小圆盘上不能放大圆盘,在三根柱子之间一次只能移动一个圆盘。

如图:

《关于汉诺塔问题的两种解法》

如果是初次接触类似的问题,乍看之下肯定会感觉无从下手。

要把64个圆盘从a柱子移动到c柱子上,第一步应该怎么做?虽然可以肯定,第一步唯一的选择是移动a最上面的那个圆盘,但是应该将其移到b还是c呢?很难确定。因为接下来的第二步、第三步……直到最后一步,看起来都是很难确定的。能立即确定的是最后一步:最后一步的盘子肯定也是a最上面那个圆盘,并且是由a或b移动到c——此前已经将63个圆盘移动到了c上。

也许你会说,管他呢,先随便试着移动一下好了。如果你这么做,你会发现,接下来你会面临越来越多类似的选择,对每一个选择都“试”一下的话,你会偏离正确的道路越来越远,直到你发现你接下来无法进行为止。

如果将这个问题的盘子数量减为10个或更少,就不会有太大的问题了。但盘子数量为64的话,你一共需要移动约1800亿亿步(18,446,744,073,709,551,615),才能最终完成整个过程。这是一个天文数字,没有人能够在有生之年通过手动的方式来完成它。即使借助于计算机,假设计算机每秒能够移动100万步,那么约需要18万亿秒,即58万年。将计算机的速度再提高1000倍,即每秒10亿步,也需要584年才能够完成。

虽然64个盘子超出了人力和现代计算机的能力,但至少对于计算机来说,这不是一个无法完成的任务。

一股脑地考虑每一步如何移动很困难,我们可以换个思路。先假设除最下面的盘子之外,我们已经成功地将上面的63个盘子移到了b柱,此时只要将最下面的盘子由a移动到c即可。如图:

《关于汉诺塔问题的两种解法》

当最大的盘子由a移到c后,b上是余下的63个盘子,a为空。因此现在的目标就变成了将这63个盘子由b移到c。这个问题和原来的问题完全一样,只是由a柱换为了b柱,规模由64变为了63。因此可以采用相同的方法,先将上面的62个盘子由b移到a,再将最下面的盘子移到c……对照下面的过程,试着是否能找到规律:

  • 将b柱子作为辅助,把a上的63个圆盘移动到b上
  • 将a上最后一个圆盘移动到c
  • 将a作为辅助,把b上的62个圆盘移动到a上
  • 将b上的最后一个圆盘移动到c
  • ……

也许你已经发现规律了,即每次都是先将其他圆盘移动到辅助柱子上,并将最底下的圆盘移到c柱子上,然后再把原先的柱子作为辅助柱子,并重复此过程。

这种思路就是第一个汉诺塔问题的第一个解法,递归法。

用伪代码的表示如下:

func:
if n!=0 then            ;预定值
  func(n-1, a, c, b)    ;将n-1个盘子由a移动到b,以c为辅助柱子(注意参数顺序)
  move a[n] to c        ;将a上的最后一个盘子移动到c
  func(n-1, b, a, c)    ;将n-1个盘子由b移动到c,以a为辅助柱子
endif                   ;完成

func中有两个递归调用,它们的规模刚好比n小1。注释说明了每行代码的作用和意图。正如注释里所强调的那样,注意参数的顺序——参数位置不同,其代表的意义也不一样。

第一个递归调用以c作为辅助柱子,这没有问题,因为c柱子的最下面的k个圆盘一定是所有圆盘中最大的k个,因此将其作为辅助柱子不会出现大圆盘在小圆盘之上的情况。

递归法使用C++语言实现如下:

#include <fstream>
#include <iostream>
#include<time.h>
using namespace std;
void Move(int n,char x,char y)
{
   cout<<"把"<<n<<"号从"<<x<<"挪动到"<<y<<endl;
}
void Hannoi(int n,char a,char b,char c)
{
    if(n==1)
        Move(1,a,c);
    else
    {
        Hannoi(n-1,a,c,b);
        Move(n,a,c);
        Hannoi(n-1,b,a,c);
    }
}
int main()
{
    int n;
    cout<<"请输入要求解的汉诺塔的阶数: ";
    cin>>n;
    clock_t start,finish;
    start = clock();
    cout<<"以下是<<n<<层汉诺塔的解法:"<<endl;
    Hannoi(n,'a','b','c');
    cout<<"输出完毕!"<<endl;
    finish = clock();
    printf("解决此 %d 阶汉诺塔所需的时间为:%.2f ms\n",n,(double)(finish-start));
    system("pause");
    return 0;
}

关于程序性能的大概统计

《关于汉诺塔问题的两种解法》

接下来用非递归来实现。

汉诺塔的非递归算法描述如下:

首先容易证明,当盘子的个数为n时,移动的次数应等于2^n – 1。

一位美国学者发现一种出人意料的方法,只要轮流进行两步操作就可以了。

首先把三根柱子按顺序排成品字型,把所有的圆盘按从大到小的顺序放在柱子A上。

根据圆盘的数量确定柱子的排放顺序:若n为偶数,按顺时针方向依次摆放 A B C;

若n为奇数,按顺时针方向依次摆放 A C B。

按顺时针方向把圆盘1从现在的柱子移动到下一根柱子,即当n为偶数时,若圆盘1在柱子A,则把它移动到B;若圆盘1在柱子B,则把它移动到C;若圆盘1在柱子C,则把它移动到A。
接着,把另外两根柱子上可以移动的圆盘移动到新的柱子上。即把非空柱子上的圆盘移动到空柱子上,当两根柱子都非空时,移动较小的圆盘这一步没有明确规定移动哪个圆盘,你可能以为会有多种可能性,其实不然,可实施的行动是唯一的。
反复进行(1)(2)操作,最后就能按规定完成汉诺塔的移动。

该算法的实现代码如下:

#include <iostream>
#include<time.h>
using namespace std;
//圆盘的个数最多为64
const int MAX = 64;
//用来表示每根柱子的信息
struct st{
     int s[MAX]; //柱子上的圆盘存储情况
     int top; //栈顶,用来最上面的圆盘
     char name; //柱子的名字,可以是A,B,C中的一个
     int Top()//取栈顶元素
     {
           return s[top];
     }
     int Pop()//出栈
     {
           return s[top--];
     }
     void Push(int x)//入栈
     {
           s[++top] = x;
     }
} ;

long Pow(int x, int y); //计算x^y
void Creat(st ta[], int n); //给结构数组设置初值
void Hannuota(st ta[], long max); //移动汉诺塔的主要函数
int main(void)
{
     clock_t start,finish;
           int n;
           cout<<"请输入汉诺塔的阶数:";
     cin >> n; //输入圆盘的个数
           start = clock();
     st ta[3]; //三根柱子的信息用结构数组存储
     Creat(ta, n); //给结构数组设置初值
     long max = Pow(2, n) - 1;//动的次数应等于2^n - 1
     Hannuota(ta, max);//移动汉诺塔的主要函数
           finish = clock();
           printf("解决此 %d 阶汉诺塔所需的时间为:%.2f ms\n",n,(double)(finish-start));
     system("pause");
     return 0;
}

void Creat(st ta[], int n)
{
     ta[0].name = 'A';
     ta[0].top = n-1;
    //把所有的圆盘按从大到小的顺序放在柱子A上
     for (int i=0; i<n; i++)
           ta[0].s[i] = n - i;
     //柱子B,C上开始没有没有圆盘
     ta[1].top = ta[2].top = 0;
     for (int i=0; i<n; i++)
           ta[1].s[i] = ta[2].s[i] = 0;
    //若n为偶数,按顺时针方向依次摆放 A B C
     if (n%2 == 0)
     {
           ta[1].name = 'B';
           ta[2].name = 'C';
     }
     else  //若n为奇数,按顺时针方向依次摆放 A C B
     {
           ta[1].name = 'C';
           ta[2].name = 'B';
     }
}

long Pow(int x, int y)
{
     long sum = 1;
     for (int i=0; i<y; i++)
           sum *= x;
     return sum;
}

void Hannuota(st ta[], long max)
{
  intk = 0; //累计移动的次数
  inti = 0;
  intch;
 while (k < max)
  {
   //按顺时针方向把圆盘1从现在的柱子移动到下一根柱子
   ch = ta[i%3].Pop();
  ta[(i+1)%3].Push(ch);
  cout << ++k << ": " <<
        "Move disk " << ch << " from " <<ta[i%3].name <<
        " to " << ta[(i+1)%3].name << endl;
  i++;
   //把另外两根柱子上可以移动的圆盘移动到新的柱子上
   if(k < max)
  {
   //把非空柱子上的圆盘移动到空柱子上,当两根柱子都为空时,移动较小的圆盘
   if (ta[(i+1)%3].Top() == 0 ||
       ta[(i-1)%3].Top() > 0 &&
       ta[(i+1)%3].Top() > ta[(i-1)%3].Top())
   {
       ch =  ta[(i-1)%3].Pop();
       ta[(i+1)%3].Push(ch);
       cout << ++k << ": " << "Move disk"
            << ch << " from " << ta[(i-1)%3].name
            << " to " << ta[(i+1)%3].name << endl;
    }
   else
    {
      ch =  ta[(i+1)%3].Pop();
      ta[(i-1)%3].Push(ch);
      cout << ++k << ": " << "Move disk"
           << ch << " from " << ta[(i+1)%3].name
           << " to " << ta[(i-1)%3].name << endl;
    }
 }
}
}

测试表明,递归法的运行效率要稍微高于非递归法。


我的微信公众号:DealiAxy

《关于汉诺塔问题的两种解法》

It never rains but it pours. 欢迎关注我的公众号:DealiAxy 提供更多技术文章

点赞

发表评论