hanio1.cpp

四柱汉诺塔问题的求解程序.解题思路:如a,b,c,d四柱. 要把a柱第n个盘移到目标柱子(d柱),先把上层 分两为两部份,上半部份移到b柱,下半部分移到c柱,再把第n盘移到 目标柱子,然后,c柱盘

/*--------------------------------------------------
解题思路如下:
  如a,b,c,d四柱. 要把a柱第n个盘移到目标柱子(d柱),先把上层
分两为两部份,上半部份移到b柱,下半部分移到c柱,再把第n盘移到
目标柱子,然后,c柱盘子再移到目标柱子,再把b柱盘子移到目标柱子.
  细节地方:
  上半部份移到b柱时,它的中间变量柱子是有二选一的.而下半部分
移到c柱时,它的中间变量柱子只有一个(因为一个柱子已被上半部份
占了).b,c也移到目标柱子时同理。
  还有一个问题,是把上层怎样划分比例,才能移动步骤最少呢? 
对此,我的做法是穷举分配数目.
---------------------------------------------------*/
#include <iostream.h> 
int count;
int m;
void Hanoi(int n, int a, int b, int c)
{
 if (n==1) 
 {
//  cout<<a<<"->"<<c<<endl;
  count++;
 }
 else if (n>0)
 {
  Hanoi(n-1,a,c,b);
//  cout<<a<<"->"<<c<<endl;
  count++;
  Hanoi(n-1,b,a,c);
 }
}
void Hanoi1(int n, int a, int b, int c, int d)
{
 if (n==1) 
 {
//  cout<<a<<"->"<<d<<endl;
  count++;
 }
 else if (n==2)
 {
  Hanoi(n-1,a,d,c);
//  cout<<a<<"->"<<d<<endl;
  count++;
  Hanoi(n-1,c,a,d);
 }
 else
 {
  int temp;
  int t=count;
  int min=-1;
  for (temp=0; temp<=(n-1); temp++)
  {
   Hanoi1(temp,a,d,c,b);
   Hanoi(n-1-temp,a,d,c);
//   cout<<a<<"->"<<d<<endl;
   count++;
   Hanoi(n-1-temp,c,a,d);
   Hanoi1(temp,b,a,c,d);
   if (count < min || min==-1) min=count;
   count=t;
  }
  count=min;
 }
}
void main()
{
 cout<<"请输入盘子数:";
 cin>>m;

 count=0;
 Hanoi(m,1,2,3);
 cout<<"三塔时最少步骤: "<<count<<endl;

 cout<<endl;
 count=0;
 Hanoi1(m,1,2,3,4);
 cout<<"四塔时的最少步骤: "<<count<<endl;
}