汉诺塔问题：

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

　　现在将问题变形为：初识时，n个金盘分散摆放在三根柱子上，并且所有金盘都处于合法状态，将这些分散的金盘全部移动到第三根柱子上，并打印每一次的移动步骤以及移动后三个柱子上金盘的状态。

　　C++实现代码如下：

1 #ifndef _HANOI_H 2 #define _HANOI_H 3 #include 
      
        4 #include 
       
         5 using namespace std; 6 class Hanoi{ 7 private: 8     int plates;                //存放盘子总数; 9     list
        
         * initStatus;    //各个钉子上盘子的个数，存放在一个链表数组中10 public:11     Hanoi();12     Hanoi(int n, int status[]);13     void ShowHanoi();14     int arrang(int n);15     void Move2Last();16     void Move(int n, int src, int buf, int dest);17 18     ~Hanoi();19 };20 #endif
        
       
      

 

 

1 #include 
      
         2 #include 
       
          3 #include 
        
           4 #include "Hanoi.h"  5   6 Hanoi::Hanoi(){  7     plates = 1;  8     initStatus = new list
         
          [3];  9     initStatus[0].push_front(0); 10 } 11 /* 12 功能：构造函数，参数status数组是金盘初识状态；参数n是数组长度，也就是金盘个数 13 说明：    1、status数组中元素必须是0、1或者2 14         2、数组下标表示金盘编号，对应的元素值表示该金盘所在的柱子编号 15         3、例如数组[0, 0, 1, 2]表示：3号金盘在2号柱子上；2号金盘在1号柱子上，0号和1号金盘在0号柱子上 16 */ 17 Hanoi::Hanoi(int n, int status[]){ 18     plates = n; 19     initStatus = new list
          
           [3]; 20     for (int i(0); i
           

::iterator lbegin, lend; 26 for (int i(0); i<3; i++){ 27 cout << "第" << i << "根柱子中金盘从下到上分别是："; 28 if (initStatus[i].empty()){ 29 cout << "空" << endl; 30 } 31 else{ 32 lbegin = initStatus[i].begin(); 33 lend = initStatus[i].end(); 34 while (lbegin != lend) 35 cout << ' ' << *lbegin++; 36 cout << endl; 37 } 38 } 39 } 40 /* 41 功能：将0、1、……、n-1号金盘全部移动到n号金盘所在的柱子上 42 注意1：0、1、……、n-1号金盘已经全部在一根柱子上 43 注意2：因此，如果要将任意状态下的0—n-1号金盘全部移动到n号金盘所在的柱子上，需要循环调用arrang函数其中参数从0到n循环 44 */ 45 int Hanoi::arrang(int n){ 46 int src(-1), dest(-1), buf(-1); 47 for (int i(0); i<3; i++){ 48 list

::iterator temp = find(initStatus[i].begin(), initStatus[i].end(), n); 49 if (temp == initStatus[i].end()) 50 continue; 51 else{ 52 src = i; 53 break; 54 } 55 } 56 if (src >= 0){ 57 for (int i(0); i<3; i++){ 58 list

::iterator temp = find(initStatus[i].begin(), initStatus[i].end(), n + 1); 59 if (temp == initStatus[i].end()) 60 continue; 61 else{ 62 dest = i; 63 break; 64 } 65 } 66 for (int i(0); i<3; i++){ 67 if (i != src && i != dest){ 68 buf = i; 69 break; 70 } 71 } 72 if (dest >= 0 && src != dest) 73 Move(n, src, buf, dest); 74 } 75 return dest; 76 } 77 /* 78 功能：将三根柱子上的金盘全部移动到2号柱子上，其中金盘初识状态为任意合法状态 79 注意：必须对三根柱子上的金盘进行初始化，也就是在调用该函数之前必须调用有参构造函数 80 */ 81 void Hanoi::Move2Last(){ 82 int res; 83 if (find(initStatus[2].begin(), initStatus[2].end(), plates - 1) != initStatus[2].end()) 84 for (int i(0); i < plates - 1; i++) 85 res = arrang(i); 86 else{ 87 int i, little(plates - 2), count(0); 88 for (i = 0; i<2; i++){ 89 if (find(initStatus[i].begin(), initStatus[i].end(), plates - 1) != initStatus[i].end()) 90 break; 91 } 92 while (find(initStatus[i].begin(), initStatus[i].end(), little) != initStatus[i].end()){ 93 little--; 94 count++; 95 } 96 if (little<0){ 97 Move(plates, i, 1 - i, 2); 98 return; 99 }100 for (int j(0); j

= 0){140 Move(n - 1, src, dest, buf);141 initStatus[src].remove(n);142 initStatus[dest].push_back(n);143 cout << "将" << n << "号金盘从" << src << "号柱子移动到" << dest << "号柱子:" << endl;144 ShowHanoi();145 Move(n - 1, buf, src, dest);146 }147 }148 Hanoi::~Hanoi(){149 delete[]initStatus;150 }