Chinaunix首页 | 论坛 | 博客
  • 博客访问: 452045
  • 博文数量: 98
  • 博客积分: 6011
  • 博客等级: 准将
  • 技术积分: 1030
  • 用 户 组: 普通用户
  • 注册时间: 2006-11-23 13:19
文章分类

全部博文(98)

文章存档

2011年(2)

2009年(2)

2008年(31)

2007年(35)

2006年(28)

我的朋友

分类:

2007-05-03 13:00:13

变体汉诺塔。
    问题描述:在经典汉诺塔的基础上加一个条件,即,如果再加一根柱子(即现在有四根柱子a,b,c,d),计算将n个盘从第一根柱子(a)全部移到最后一根柱子(d)上所需的最少步数,当然,也不能够出现大的盘子放在小的盘子上面。注:1<=n<=64;
分析:设F[n]为所求的最小步数,显然,当n=1时,F[n]=1;当n=2时,F[n]=3;如同经典汉诺塔一样,我们将移完盘子的任务分为三步:
(1)将x(1<=x<=n)个盘从a柱依靠b,d柱移到c柱,这个过程需要的步数为F[x];
(2)将a柱上剩下的n-x个盘依靠b柱移到d柱(注:此时不能够依靠c柱,因为c柱上的所有盘都比a柱上的盘小)
     些时移动方式相当于是一个经典汉诺塔,即这个过程需要的步数为2^(n-x)-1(证明见再议汉诺塔一);
(3)将c柱上的x个盘依靠a,b柱移到d柱上,这个过程需要的步数为F[x];
第(3)步结束后任务完成。
故完成任务所需要的总的步数F[n]=F[x]+2^(n-x)-1+F[x]=2*F[x]+2^(n-x)-1;但这还没有达到要求,题目中要求的是求最少的步数,易知上式,随着x的不同取值,对于同一个n,也会得出不同的F[n]。即实际该问题的答案应该min{2*F[x]+2^(n-x)-1},其中1<=x<=n;在用高级语言实现该算法的过程中,我们可以用循环的方式,遍历x的各个取值,并用一个标记变量min记录x的各个取值中F[n]的最小值。
用C++实现该算法如下:
#include
using namespace std;
int main()
{
 int n,x,i;
 double min,f[64];//min为标记变量,f[n]如上述分析中的F[n].
 double fang(int n);//该函数用来求2^n;
 f[0]=0;f[1]=1;f[2]=3;
 while(cin>>n)
 {
  for(i=3;i<=n;i++)
  {
   min=4131231321;
   for(x=1;x   {
    f[i]=2*f[x]+fang(i-x)-1;//算法的关键步骤。
    if(f[i]     min=f[i];
    else
     f[i]=min;
   }
   
  }
  cout< }
 return 0;
}
double fang(int t)//求2^t.
{
 double e=1;
 for(int i=1;i<=t;i++)
 {
  e=e*2;
 }
 return e;
}
//////////
一些测试数据:
 
Sample Input
1
3
12
 

Sample Output
1
5
81
//////////
原题见杭电1207题:
当然本题也可以如经典汉诺塔样使用递归算法,并且记录递归过程中对应各个x,递归所需要的步数。但时间复杂度相当高,当盘子的数目较大时,如64个,AMD3000+的CPU要算相当长的时间。。。故这里略去。
 
待续。。。。
 
 
阅读(2378) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~