正文

hdu1207汉诺塔ii（递推）

午夜的行人  午夜的行人  2022-09-13  503

关键词：

经典的汉诺塔问题经常作为一个递归的经典例题存在。可能有人并不知道汉诺塔问题的典故。汉诺塔来源于印度传说的一个故事，上帝创造世界时作了三根金刚石柱子，在一根柱子上从下往上按大小顺序摞着64片黄金圆盘。上帝命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一回只能移动一个圆盘。有预言说，这件事完成时宇宙会在一瞬间闪电式毁灭。也有人相信婆罗门至今仍在一刻不停地搬动着圆盘。恩，当然这个传说并不可信，如今汉诺塔更多的是作为一个玩具存在。Gardon就收到了一个汉诺塔玩具作为生日礼物。
　　Gardon是个怕麻烦的人（恩，就是爱偷懒的人），很显然将64个圆盘逐一搬动直到所有的盘子都到达第三个柱子上很困难，所以Gardon决定作个小弊，他又找来了一根一模一样的柱子，通过这个柱子来更快的把所有的盘子移到第三个柱子上。下面的问题就是：当Gardon在一次游戏中使用了N个盘子时，他需要多少次移动才能把他们都移到第三个柱子上？很显然，在没有第四个柱子时，问题的解是2^N-1，但现在有了这个柱子的帮助，又该是多少呢？

Input包含多组数据，每个数据一行，是盘子的数目N(1<=N<=64)。
Output对于每组数据，输出一个数，到达目标需要的最少的移动数。
Sample Input

1
3
12

Sample Output

1
5
81

变体汉诺塔

问题描述：在经典汉诺塔的基础上加一个条件，即，如果再加一根柱子（即现在有四根柱子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]的最小值。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cmath>
 5 using namespace std;
 6 const int INF=99999999;
 7 int f[65];
 8 void Init(){
 9     f[1]=1; f[2]=3;
10     for(int i=3;i<65;i++){
11         int minx=INF;
12         for(int x=1;x<i;x++)
13             if(2*f[x]+pow(2,i-x)-1<minx)
14                 minx=2*f[x]+pow(2,i-x)-1;
15         f[i]=minx;
16     }
17 }
18 int main(){
19     int n;
20     Init();
21     while(~scanf("%d",&n)){
22         printf("%d
",f[n]);
23     }
24     return 0;
25 }

hdu1207汉诺塔ii（递推）

经典的汉诺塔问题经常作为一个递归的经典例题存在。可能有人并不知道汉诺塔问题的典故。汉诺塔来源于印度传说的一个故事，上帝创造世界时作了三根金刚石柱子，在一根柱子上从下往上按大小顺序摞着64片黄金圆盘。上帝... 查看详情

hdu1207汉诺塔ii

汉诺塔IITimeLimit:2000/1000MS(Java/Others) MemoryLimit:65536/32768K(Java/Others)TotalSubmission(s):8433 AcceptedSubmission(s):4162ProblemDescription经典的汉诺塔问题经查看详情

hdu1207汉诺塔ii(简单dp)

题意：中文题。析：在没有第四个柱子时，把n个盘子搬到第3个柱子时，那么2^n-1次，由于多了一根，不知道搬到第四个柱子多少根时是最优的，所以dp[i]表示搬到第4个柱子i个盘子时，步数最少，dp[i]=min{dp[j]+(1<<i-j)-1}。也可... 查看详情

hdu2175汉诺塔ix（递推）

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=21751,2,...,n表示n个盘子．数字大盘子就大．n个盘子放在第１根柱子上．大盘不能放在小盘上．在第１根柱子上的盘子是a[1],a[2],...,a[n].a[1]=n,a[2]=n-1,...,a[n]=1.即a[1]是最下面的盘子... 查看详情

hdu2064汉诺塔iii（递推）

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2064约19世纪末，在欧州的商店中出售一种智力玩具，在一块铜板上有三根杆，最左边的杆上自上而下、由小到大顺序串着由64个圆盘构成的塔。目的是将最左边杆上的盘全部移到右边的... 查看详情

汉诺塔系列问题(代码片段)

HDU-1207汉诺塔II题目链接https://vjudge.net/problem/HDU-1207题面Description经典的汉诺塔问题经常作为一个递归的经典例题存在。可能有人并不知道汉诺塔问题的典故。汉诺塔来源于印度传说的一个故事，上帝创造世界时作了三根金刚石柱... 查看详情

acwing-96-奇怪的汉诺塔(递推)(代码片段)

链接:https://www.acwing.com/problem/content/description/98/题意:汉诺塔问题，条件如下：1、这里有A、B、C和D四座塔。2、这里有n个圆盘，n的数量是恒定的。3、每个圆盘的尺寸都不相同。4、所有的圆盘在开始时都堆叠在塔A上，且圆盘尺寸... 查看详情

递推问题之汉诺塔问题

汉诺塔问题设3根柱子分别为A、B、C，圆盘数目为n。1:如果A有一个圆盘，则直接移动至c。 2:如果A有2个圆盘，则A->B,A->C,B->C。好了这个时候已经可以解决问题了，结束条件为n==1；假设当我们在数目为n-1的... 查看详情

bzoj.1019.[shoi2008]汉诺塔(递推)

...目链接按照优先级移动，操作序列显然是唯一的。普通的汉诺塔是将n-1个盘子移到中间柱，再将第n个盘子移到目标柱，再将n-1个移到目标柱上的递归过程。对于本题移动方法还是基本一样的。考虑递推，从i-1个盘子推i个盘子。p... 查看详情

hdu1995汉诺塔v

...个盘子，称为1号盘，2号盘,...。号数大盘子就大。经典的汉诺塔问题经常作为一个递归的经典例题存在。可能有人并不知道汉诺塔问题的典故。汉诺塔来源于印度传说的一个故事，上帝创造世界时作了三根金刚石柱子，... 查看详情

递归与递推新汉诺塔

题目描述设有n个大小不等的中空圆盘，按从小到大的顺序从1到n编号。将这n个圆盘任意的迭套在三根立柱上，立柱的编号分别为A、B、C，这个状态称为初始状态。现在要求找到一种步数最少的移动方案，使得从初始状态转变为... 查看详情

hdu1995汉诺塔v(代码片段)

题目：http://acm.hdu.edu.cn/showproblem.php?pid=1995题意：经典汉诺塔题型，输出第k个盘子移动的次数。解法：首先：由于比k小的盘子移动不会牵扯k移动，所以问题被简化成n-k+1阶汉诺塔中第一个盘子的移动次数。再观察汉诺塔的移动策... 查看详情

水题第四站hdu汉诺塔vii

先来回忆一下汉诺塔A，B，C，三个塔将A塔上的n块砖转移到C塔，首先将(n-1)块砖转移到B塔，将第n块砖转移到C塔，再将B塔上的(n-1)块砖转移到C塔，所以函数为借助B塔，将A塔的砖转移到C塔，首先是借助C塔，将A塔的砖转移到B塔，... 查看详情

hdu1996汉诺塔vi

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1996n个盘子的汉诺塔问题的最少移动次数是2^n-1,即在移动过程中会产生2^n个系列。由于发生错移产生的系列就增加了，这种错误是放错了柱子，并不会把大盘放到小盘上，即各柱&nbs... 查看详情

题解报告：hdu1996汉诺塔vi

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1996解题思路：每个盘子有3种选择，故系列总数为3^n。（水题！！！）AC代码：1#include<bits/stdc++.h>2usingnamespacestd;3typedeflonglongLL;4intmain()5{6intT,N;7LLa[30]={0};8a[0]=1;9fo 查看详情

hdu1996汉诺塔vi(排列组合)

题意：。。。析：每次都是有三种放法，1，2，3，根柱子，所以就是3^n次方。代码如下：#pragmacomment(linker,"/STACK:1024000000,1024000000")#include<cstdio>#include<string>#include<cstdlib>#include<cmath>#include<iost 查看详情

题解报告：hdu1995汉诺塔v

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1995解题思路：求第k号盘子至少需要移动的次数,实际上是求n-k（认作是前g-1个盘子移动的总次数）个盘子（还欠一个）至少需要移动的次数再加上第（n-k+1）（认作是第g个盘子）个盘子... 查看详情

poj1958-汉诺四塔问题（三种方法）(代码片段)

链接：http://poj.org/problem?id=1958大意：汉诺塔升级版，四根柱子，n个盘子，求最少移动次数；两种方法递推or递归（当然还有思路3——打表）思路1：递推（或者DP?)把四塔转换为三塔进行思考假设当前要移动n个盘子，那么就不如... 查看详情