首页 > ACM题库 > HDU-杭电 > hdu 2064 汉诺塔III-动态规划-[解题报告]C++
2013
12-29

hdu 2064 汉诺塔III-动态规划-[解题报告]C++

汉诺塔III

问题描述 :

约19世纪末,在欧州的商店中出售一种智力玩具,在一块铜板上有三根杆,最左边的杆上自上而下、由小到大顺序串着由64个圆盘构成的塔。目的是将最左边杆上的盘全部移到右边的杆上,条件是一次只能移动一个盘,且不允许大盘放在小盘的上面。
现在我们改变游戏的玩法,不允许直接从最左(右)边移到最右(左)边(每次移动一定是移到中间杆或从中间移出),也不允许大盘放到下盘的上面。
Daisy已经做过原来的汉诺塔问题和汉诺塔II,但碰到这个问题时,她想了很久都不能解决,现在请你帮助她。现在有N个圆盘,她至少多少次移动才能把这些圆盘从最左边移到最右边?

输入:

包含多组数据,每次输入一个N值(1<=N=35)。

输出:

包含多组数据,每次输入一个N值(1<=N=35)。

样例输入:

1
3
12

样例输出:

2
26
531440

解题报告:

题目大意这里就不说了,这里给出题目链接,http://acm.hdu.edu.cn/showproblem.php?pid=2064

这题首先我们应该知道的是如何将N个圆盘从第一杆全部搬到第二根杆跟全部搬到第三根杆和从第二根杆全部搬到第三根杆需要的次数是一样的,然后搬N根杆的次数就可以有搬N-1根杆的次数得到,这里首先给出地推公式,dp[n]=3*dp[n-1]+2;思想就是假设现在要将N个圆盘搬到第三根杆,现在首先要做的是把N-1根杆全部搬到第三根杆,这样一共需要dp[n-1]次,然后第一根杆上面还剩下一个圆盘,现在我们要把这最后一个圆盘放到第二根杆上面,原因待会再解释,然后现在要做的事就是把这一个最大的圆盘放到第三根杆的最下面,然而第三根杆现在正被N-1个圆盘占用了,所以要将这N-1个圆盘移开全部移到第一根杆上面,所以这样需要的次数是dp[n-1]次,好了,现在第三根杆就完全是空的了,就顺利地把最后一个圆盘放到第三根杆上面了,这时再把N-1个圆盘从第一根杆上面移动到第三根杆上面,这样整个游戏就结束了。现在解释一下为什么第二步要把最大的那个盘移动到第二根杆了,很显然如果这一步不把它移到第二根杆的话,那么第三根杆上面的N-1个盘就必须移动到第二根杆上面,而这时最大的盘还在第一根杆上又不可以把它直接移动到第三根杆上面,又不能移到第二根杆上面,因为大盘不能放小盘上面,所以第二步就只好把最大的盘放到第二根杆上面。

#include<cstdio>
 __int64 dp[40];
 void dabiao() {
     dp[0]=0,dp[1]=2,dp[2]=8;
     for(int i=3;i<=35;++i)
     dp[i]=3*dp[i-1]+2;
 }
 int main() {
     dabiao();
     int n;
     while(scanf("%d",&n)!=EOF)
     printf("%I64d\n",dp[n]);
     return 0;
 }

 

解题转自:http://www.cnblogs.com/xiaxiaosheng/archive/2013/05/30/3109338.html


  1. #include <cstdio>
    #include <cstring>

    const int MAXSIZE=256;
    //char store[MAXSIZE];
    char str1[MAXSIZE];
    /*
    void init(char *store) {
    int i;
    store['A']=’V', store['B']=’W',store['C']=’X',store['D']=’Y',store['E']=’Z';
    for(i=’F';i<=’Z';++i) store =i-5;
    }
    */
    int main() {
    //freopen("input.txt","r",stdin);
    //init(store);
    char *p;
    while(fgets(str1,MAXSIZE,stdin) && strcmp(str1,"STARTn")==0) {
    if(p=fgets(str1,MAXSIZE,stdin)) {
    for(;*p;++p) {
    //*p=store[*p]
    if(*p<’A’ || *p>’Z') continue;
    if(*p>’E') *p=*p-5;
    else *p=*p+21;
    }
    printf("%s",str1);
    }
    fgets(str1,MAXSIZE,stdin);
    }
    return 0;
    }