汉诺塔非递归算法实现例子

作者：袖梨 2022-06-25

最近的算法课，讲到了递归与分治策略，书上递归的例子是很经典的汉诺塔问题。问题大意是有三个塔座，分别为a，b，c，开始时塔座a上叠有n个圆盘，这些圆盘自上而下，由小到大地叠放在一起，各圆盘从小到大编号为1到n。要求将塔座a上的圆盘移动到塔座b上，并且在移动时每次只能移动一个圆盘，且每个塔座上的圆盘都必须保持自上而下、由小到大的排列顺序。

本文不涉及对非递归算法的数学性证明，若想理解非递归算法的道理，下面的就不用看啦。

递归的解法就不再说了，这里谈一下非递归的解法。教科书上对于非递归解法是这样描述的：

假设塔座a，b，c排成一个三角形，a->b->c->a构成一顺时针循环，在移动圆盘的过程中，若是奇数次移动，则将最小的圆盘移到顺时针方向的下一塔座;若是偶数次移动，则保持最小的圆盘不动，而在其他两个塔座之间，将较小的圆盘移到另一塔座上去。
在这里我们默认塔座a是初始圆盘放置的塔座，塔座b是圆盘需要移到的目标塔座，塔座c是目标塔座，n是初始的圆盘数量。经过个人编码验证，证实书上说的有一点不妥，正确的说法是：

当n是奇数时，塔座按a->b->c->a排列，而当n是偶数时，塔座应该按a->c->b->a排列。

自己编码之前，也上网看过别人写的代码，自己都不是很喜欢，定义了各种复杂的结构体还有函数等，于是自己写了一个c++版本的，只用到了vector这一种数据结构，不过由于都写在一个hanoi函数体内，关于打印信息方面可能处理的不是很好，显得程序有点冗长，但整体结构还是挺清晰的。代码如下：

代码如下

复制代码

void hanoi(int n) {
// the aim is to move plates from A to B
// when n is odd, the tower is placed in order A->B->C
// when n is even, the tower is placed in order A->C->B
vector odd{'A', 'B', 'C'};
vector even{'A', 'C', 'B'};
vector> tower(3, vector());

// initialize
for(int i=n; i>=1; i--)
  tower[0].push_back(i);

// loop begin
int iter = 0;
while(true) {
  // different endings for n
  if(n%2 && tower[0].empty() && tower[2].empty()) break;
  if(n%2==0 && tower[0].empty() && tower[1].empty()) break;

  iter++;

  if(iter % 2) { // odd plate move
      // just move plate1 to next tower
   int min = MAX+1;
   int index;
   for(int i=0; i<3; i++) {
    if(!tower[i].empty() && tower[i].back()      min = tower[i].back();
     index = i;
    }
   }
   tower[index].pop_back();
   tower[(index+1)%3].push_back(min);

   if(n%2) { // different n, different messages
    cout << "Moving plate " << min << " from "
      << odd[index] << " to "
      << odd[(index+1)%3] << endl;
   }
   else {
    cout << "Moving plate " << min << " from "
      << even[index] << " to "
      << even[(index+1)%3] << endl;
   }
  }
  else {   // even plate move
      // move the smallest plate except plate1 to another
   int min = MAX+1;
   int index;
   for(int i=0; i<3; i++) {
    if(!tower[i].empty() && tower[i].back()      min = tower[i].back();
     index = i;
    }
   }
   // get the other two tower whose top is not plate1
   int index1 = (index+1)%3;
   int index2 = (index+2)%3;
   if(tower[index1].empty()) {
    min = tower[index2].back();
    tower[index2].pop_back();
    tower[index1].push_back(min);

    if(n%2) { // different n, different messages
     cout << "Moving plate " << min << " from "
        << odd[index2] << " to "
        << odd[index1] << endl;
    }
    else {
     cout << "Moving plate " << min << " from "
        << even[index2] << " to "
        << even[index1] << endl;
    }
   }
   else if(tower[index2].empty()) {
    min = tower[index1].back();
    tower[index1].pop_back();
    tower[index2].push_back(min);

    if(n%2) { // different n, different messages
     cout << "Moving plate " << min << " from "
        << odd[index1] << " to "
        << odd[index2] << endl;
    }
    else {
     cout << "Moving plate " << min << " from "
        << even[index1] << " to "
        << even[index2] << endl;
    }
   }
   else {
    int index3;
    if(tower[index1].back() < tower[index2].back()) {
     min = tower[index1].back(); index3 = index1;
    }
    else {
     min = tower[index2].back(); index3 = index2;
    }
    tower[index3].pop_back();
    tower[3-index-index3].push_back(min);

    if(n%2) { // different n, different messages
     cout << "Moving plate " << min << " from "
       << odd[index] << " to "
       << odd[(index+1)%3] << endl;
    }
    else {
     cout << "Moving plate " << min << " from "
       << even[index] << " to "
       << even[(index+1)%3] << endl;
    }
   }
  }
}
return;
}

上面代码的5，6两行定义的两个vector是用于打印信息的时候用的，当n是奇数时，就采用odd里面的顺序，n是偶数时，就采用even里面的顺序，所有打印处理信息的时候要考虑到n的奇偶性，显得打印信息那几块地方比较罗嗦。记录每个塔座上的圆盘信息只用了一个二维vector tower，初始化的时候tower[0]，即塔座a上面自下而上从大到小放置了n个圆盘。

然后就进入循环了，由于n的奇偶问题，所以终结循环的判定条件也有两种，在第17、18行。进入循环分成两大块，即判定当前移动次数是奇数次还是偶数次，如果是奇数次，就执行22行开始的代码，将标号为1的圆盘顺时针移动到下一个塔座，要考虑n的奇偶性不同带来的顺时针顺序不同的问题;如果是偶数次，就执行46行开始的代码，保持最小的圆盘不动，移动另外两个塔座上较小的圆盘到另一个塔座，这里要判定一下这两个塔座其中是否不存在圆盘，同样的还是要考虑n的奇偶性带来的顺时针顺序不同的问题。

后面进行一些改进

代码如下

复制代码

#include
#include
using namespace std;

const int MAX = 64;