正文 

当前位置： 首页 > java > java教程

hdu1207汉诺塔ii（递推）(代码片段)

caomingpei caomingpei     2022-12-19     546

关键词：

汉诺塔II

Problem Description

经典的汉诺塔问题经常作为一个递归的经典例题存在。可能有人并不知道汉诺塔问题的典故。汉诺塔来源于印度传说的一个故事，上帝创造世界时作了三根金刚石柱子，在一根柱子上从下往上按大小顺序摞着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

# 题解

思路

设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]。即实际该问题的答案应该min2*F[x]+2^(n-x)-1,其中1<=x<=n;

当然由于pow返回的是double，所以使用pow时长度表示可以大于long long，然而其精度只有15-16位左右。

代码

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<string>
#include<vector>
#include<stack>
#include<bitset>
#include<cstdlib>
#include<cmath>
#include<set>
#include<list>
#include<deque>
#include<map>
#include<queue>
using namespace std;
typedef long long ll;
const double PI = acos(-1.0);
const double eps = 1e-6;
const int INF = 0x3f3f3f3f;


int cal[65];
void init()
    cal[1]=1; cal[2]=3;
    for(int i=3;i<65;i++)
        int minx=INF;
        for(int x=1;x<i;x++)
            if(2*cal[x]+pow(2.0,i-x)-1<minx)
                minx=2*cal[x]+pow(2.0,i-x)-1;
            
        
        cal[i]=minx;
    


int main()
    int n;
    init();
    while(~scanf("%d",&n))
        printf("%d
",cal[n]);
    
    return 0;

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}。也可... 查看详情

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

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

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个圆盘构成的塔。目的是将最左边杆上的盘全部移到右边的... 查看详情

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

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

hdu1995汉诺塔v(代码片段)

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

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

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

第一节汉诺塔与栈(代码片段)

1、汉诺塔汉诺塔（又称河内塔）问题是源于印度一个古老传说的益智玩具。大梵天创造世界的时候做了三根柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放... 查看详情

水题第四站hdu汉诺塔vii

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

《算法竞赛进阶指南》-acwing-96.奇怪的汉诺塔-题解(代码片段)

...题目描述问题分析费解的开关传送门题目描述参考正常的汉诺塔问题（3根柱子），现在变成4根。把n个盘子从A移动到D上至少需要多少步？输入：没有输入输出：输出12行，第i行是i个盘子至少需要几步... 查看详情

《算法竞赛进阶指南》-acwing-96.奇怪的汉诺塔-题解(代码片段)

...题目描述问题分析费解的开关传送门题目描述参考正常的汉诺塔问题（3根柱子），现在变成4根。把n个盘子从A移动到D上至少需要多少步？输入：没有输入输出：输出12行，第i行是i个盘子至少需要几步... 查看详情

题解报告：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 查看详情

递推问题之汉诺塔问题

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

hdu1996汉诺塔vi(排列组合)

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

shoi2008汉诺塔(代码片段)

 传送门 我真爱汉诺塔 虽说是道紫题，但仔细想想仍适用于基础版本的汉诺塔的递推思路：对于每个情况中的底盘，必须将其上方所有的盘都先挪走。 转移到这道题上，即将每个底盘上的所有盘全部按当前最高优... 查看详情

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

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