/*问题描述：有三个柱子A, B, C. A柱子上叠放有n个盘子，每个盘子都比它下面的盘子要小一点，可以从上到下用1, 2, ..., n编号。要求借助柱子B，把柱子A上的所有的盘子移动到柱子C上。移动条件为：1、一次只能移一个盘子；2、移动过程中大盘子不能放在小盘子上，只能小盘子放在大盘子上。*//*递归的算法相信大多数人都知道，非递归算法也有出现过。如：摘自http://www.programfan.com/club/old_showbbs.asp?id=96548作者：qq590240#include <iostream>#include <stdlib.h> #ifdef _WIN32using namespace std;#endif static void hanoi(int height){    int fromPole, toPole, Disk;    int *BitStr = new int[height],        *Hold   = new int[height];    char Place[]  = {'A', 'B', 'C'};    int i, j, temp;     for (i=0; i < height; i++)    {        BitStr[i] = 0;        Hold[i] = 1;    }    temp = 3 - (height % 2);    int TotalMoves = (1 << height) - 1;    for (i=1; i <= TotalMoves; i++)    {        for (j=0 ; BitStr[j] != 0; j++)        {            BitStr[j] = 0;        }        BitStr[j] = 1;        Disk = j+1;        if (Disk == 1)        {            fromPole = Hold[0];            toPole = 6 - fromPole - temp;            temp = fromPole;        }        else        {            fromPole = Hold[Disk-1];            toPole = 6 - Hold[0] - Hold[Disk-1];        }        cout << "Move disk " << Disk << " from " << Place[fromPole-1]             << " to " << Place[toPole-1] << endl;        Hold[Disk-1] = toPole;    }}   int main(int argc, char *argv[]){    cout << "Towers of Hanoi: " << endl         << "moving a tower of n disks from pole A to pole B by using pole C" << endl;    cout << "Input the height of the original tower: ";    int height;    cin >> height;    hanoi(height);     system("PAUSE");    return EXIT_SUCCESS;} //////////////////////////////////////////////////////////// 我在这里根据《数学营养菜》（谈祥柏 著）提供的一种方法，编了一个程序来实现。*//*算法介绍：首先容易证明，当盘子的个数为n时，移动的次数应等于2^n - 1。一位美国学者发现一种出人意料的方法，只要轮流进行两步操作就可以了。首先把三根柱子按顺序排成品字型，把所有的圆盘按从大到小的顺序放在柱子A上。根据圆盘的数量确定柱子的排放顺序：若n为偶数，按顺时针方向依次摆放 A B C；若n为奇数，按顺时针方向依次摆放 A C B。（1）按顺时针方向把圆盘1从现在的柱子移动到下一根柱子，即当n为偶数时，若圆盘1在柱子A，则把它移动到B；若圆盘1在柱子B，则把它移动到C；若圆盘1在柱子C，则把它移动到A。（2）接着，把另外两根柱子上可以移动的圆盘移动到新的柱子上。即把非空柱子上的圆盘移动到空柱子上，当两根柱子都非空时，移动较小的圆盘这一步没有明确规定移动哪个圆盘，你可能以为会有多种可能性，其实不然，可实施的行动是唯一的。（3）反复进行（1）（2）操作，最后就能按规定完成汉诺塔的移动。*/#include <iostream>using namespace std; const int MAX = 64; //圆盘的个数最多为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^yvoid Creat(st ta[], int n); //给结构数组设置初值void Hannuota(st ta[], long max); //移动汉诺塔的主要函数 int main(void){      int n;      cin >> n; //输入圆盘的个数            st ta[3]; //三根柱子的信息用结构数组存储      Creat(ta, n); //给结构数组设置初值       long max = Pow(2, n) - 1;//动的次数应等于2^n - 1      Hannuota(ta, max);//移动汉诺塔的主要函数       system("pause");      return 0;} void Creat(st ta[], int n){      ta[0].name = 'A';      ta[0].top = n-1;      for (int i=0; i<n; i++) //把所有的圆盘按从大到小的顺序放在柱子A上            ta[0].s[i] = n - i;                  ta[1].top = ta[2].top = 0;//柱子B，C上开始没有没有圆盘      for (int i=0; i<n; i++)            ta[1].s[i] = ta[2].s[i] = 0;                  if (n%2 == 0) //若n为偶数，按顺时针方向依次摆放 A B C      {            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){      int k = 0; //累计移动的次数      int i = 0;      int ch;      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;                  }            }      }}

评论