void Hanoi(int n)
{
 char pole[3][101];
 char pole_id[4] = {"xyz"};
 int  count[3]; // 每个塔上的盘子数
 int  i;

 count[0] = n; // 初始0号塔n个盘子
 count[1] = 0;
 count[2] = 0;

 for(i=1; i<=n; ++i)
 {
  pole[0][i] = n-i+1; 
  pole[1][i] = 0;
  pole[2][i] = 0;
 }

 int  p1   = 0;   // 指向最小盘子所在的塔号
 int  aim1 = n&1?2:1;  // 最小盘子移动的目标塔号
 int  p    = 3 - aim1; // 剩下的塔号
 int  inc  = n&1?-1:1; // 目标塔移动的增量

 while(count[2] < n-1)
 {
  Move(1, pole_id[p1], pole_id[aim1]); // 最小盘子从p1塔移到aim1塔
  --count[p1], ++count[aim1];

  // 除aim1塔（最小盘子刚移到上面）外，剩下两个塔能怎么移动就怎么移动
  if(count[p1] == 0)
  {
   Move(pole[p][count[p]], pole_id[p], pole_id[p1]);
   pole[p1][++count[p1]] = pole[p][count[p]--];
  }
  else if(count[p] == 0)
  {
   Move(pole[p1][count[p1]], pole_id[p1], pole_id[p]);
   pole[p][++count[p]] = pole[p1][count[p1]--];
  }
  else if(pole[p1][count[p1]]>pole[p][count[p]])
  {
   Move(pole[p][count[p]], pole_id[p], pole_id[p1]);
   pole[p1][++count[p1]] = pole[p][count[p]--];
  }
  else
  {
   Move(pole[p1][count[p1]], pole_id[p1], pole_id[p]);
   pole[p][++count[p]] = pole[p1][count[p1]--];
  }

  // 改变最小盘子所在的塔号，目标塔号和剩下塔号
  p1    = aim1;
  aim1 += inc;
  if(aim1 > 2)
   aim1 = 0;
  if(aim1 < 0)
   aim1 = 2;
  p = 3-p1-aim1;
 }

 Move(1, pole_id[p1], pole_id[aim1]);
}

评论