汉诺塔系列

汉诺塔1 :a上面的盘子借助b到c

公式:n = 2^n-1;
# include <iostream>
# include <cstdio>
using namespace std;

void f(int n,char A,char B,char C){

    if(n>=1){
        f(n-1,A,C,B);//n-1个盘子从a-->b借助c
        printf("%c->%c\n",A,C);//第n个盘子直接从a到c 
        f(n-1,B,A,C);//第n个盘子已经从a到c了,剩余的n-1个盘子从b->a借助c,这时把一步做完了
    }

}

int main(){ 

    int n;
    char A='A',B='B',C='C';

    cin>>n;
    f(n,A,B,C);
}

汉诺塔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

思路:
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]的最小值。

# include <iostream>

using namespace std;

int main(){

    int n,i,j;
    double a[66],b[66];//a数组代表每个2的幂次方,b数组代表移动最小盘子的次数

    a[1] = 2;
    for(i=2;i<=64;i++){//2^i 
        a[i] = a[i-1]*2;
    } 

    b[1] = 1;
    b[2] = 3;
    double temp,min; 
    for(i=3;i<=64;i++){//代表当前i个盘子移动到c 
        min = a[i];//目前找一个比较大的值 
        for(j=1;j<i;j++){//寻找最小值 
            temp = 2*b[j] + a[i-j] - 1;
            if(temp<min){
                min = temp;
            }
        }

        b[i] = min;
    }

    while(cin>>n){
        cout<<b[n]<<endl;
    }

    return 0;
}

​​http://acm.hdu.edu.cn/showproblem.php?pid=2064​​

汉诺塔III

Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 12296 Accepted Submission(s): 5608

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

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

Output
对于每组数据，输出移动最小的次数。

Sample Input
1
3
12

Sample Output
2
26
531440

思路:
在经典汉若塔问题的条件改为，每次只能移动到附近塔上，求把A塔所有的移动C塔最小次数。

a[n]=a[n-1]+1+a[n-1]+1+a[n-1]:先把上面的N-1个移动到C(必然有这个状态)，在把最大的移到B，再把N-1移到到A，把最大的移到C，再把N-1个移到C，就上面的方程。分分钟搞定~~~

# include <stdio.h>

int main(){

    long long a[60];
    int i,j,n;

    a[1] = 2;
    a[2] = 8;
    a[3] = 26;
    for(i=4;i<=36;i++){
        a[i] = 3*a[i-1] + 2;

    }

    while(scanf("%d",&n)!=EOF){
        printf("%I64d\n",a[n]);
    }


    return 0;
}

汉诺塔IV

Problem Description
还记得汉诺塔III吗？他的规则是这样的：不允许直接从最左(右)边移到最右(左)边(每次移动一定是移到中间杆或从中间移出)，也不允许大盘放到小盘的上面。xhd在想如果我们允许最大的盘子放到最上面会怎么样呢？（只允许最大的放在最上面）当然最后需要的结果是盘子从小到大排在最右边。

Input
输入数据的第一行是一个数据T，表示有T组数据。
每组数据有一个正整数n(1 <= n <= 20)，表示有n个盘子。

Output
对于每组输入数据，最少需要的摆放次数。

Sample Input
2
1
10

Sample Output
2
19684

思路1:
iii:a[n] = 3*a[n-1] + 2
推到出本题的公式:a[n] = a[n-1]+2
根据n-1移动必须经过中间的盘子移动次数a[n-1],那么第n个盘子只需两步就可以到达c

# include <iostream>

using namespace std;

int main(){

    int n,m,i,j;
    long long a[22];
    a[0] = 0;
    a[1] = 2;
    a[2] = 8;
    for(i=3;i<=20;i++){
        a[i] = 3*a[i-1] + 2;//计算i个盘子从a到c,必须经过b移动的次数
    }

    while(cin>>n){
        while(n--){
            cin>>m;
            cout<<a[m-1]+2<<endl;//根据思路可知
        }
    }

    return 0;
}

解法2:
在汉若塔3的基础上，改条件：允许最大的盘子放到最上面（只允许最大的放在最上面）当然最后需要的结果还是盘子从小到大排在最右边。

A,B,C三个塔，方程：ans[n]=ab[n-1]+1+1+bc[n-1]. (ab表示a到b)

DP思路：先把n-1个搬到b,再用俩步般最大的到C，再把n-1个从B到C。这里又要求出ac[n]和bc[n]：求其递推方程：bc[n]=bc[n-1]+1+ac[n-1]，

会发现bc[]方程和ab[n]一样的。所以总方程ans[n]=2*ab[n-1]+2.

#include<iostream>
#include<cmath>
using namespace std;
unsigned long long ac[23];
unsigned long long bc[23];
unsigned long long ans[23];
int main()
{
    ac[1]=2;bc[1]=1;ans[1]=2;ans[2]=4;
    for(int i=2;i<22;i++)
    {
        ac[i]=3*ac[i-1]+2;
        bc[i]=bc[i-1]+1+ac[i-1];
    }
     for(int i=3;i<22;i++)
    {
        ans[i]=2*bc[i-1]+2;
    }
    int tt,n;
    cin>>tt;

    while(tt--)
    {
        cin>>n;
        cout<<ans[n]<<endl;
    }
    return 0;
}

汉诺塔V

Problem Description
用1,2,…,n表示n个盘子，称为1号盘，2号盘,…。号数大盘子就大。经典的汉诺塔问
题经常作为一个递归的经典例题存在。可能有人并不知道汉诺塔问题的典故。汉诺塔来源于
印度传说的一个故事，上帝创造世界时作了三根金刚石柱子，在一根柱子上从下往上按大小
顺序摞着64片黄金圆盘。上帝命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱
子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一回只能移动一个圆盘。我们
知道最少需要移动2^64-1次.在移动过程中发现，有的圆盘移动次数多，有的少 。 告之盘
子总数和盘号，计算该盘子的移动次数.

Input
包含多组数据，首先输入T,表示有T组数据.每个数据一行，是盘子的数目N(1<=N<=60)和盘
号k(1<=k<=N)。

Output
对于每组数据，输出一个数，到达目标时k号盘需要的最少移动数。

Sample Input
2
60 1
3 1

Sample Output
576460752303423488
4

解法1:
大盘子移动的次数是他上一个移动次数的1/2
总移动次数:2^n-1;

# include <iostream>

using namespace std;

long long f(int n,int i){

    long long sum = 1; 
    int j;
    for(j=n;j>i;j--){//n个盘子第i个盘子 
        sum=sum*2;
    }

    return sum;
}

int main(){

    long long n;
    int m,i,j;

    while(cin>>m){
        while(m--){
            cin>>n>>i; 
            n = f(n,i);
            cout<<n<<endl;
        }
    }
    return 0;
}

动态规划思想:

# include <iostream>

using namespace std;

long long dp[63][63];
/*
    此二维数组记录每个盘子的次数,dp[a][b]：代表当a个盘子的时候,第b(b<=a)个盘子移动的次数 
    一个盘子的时候: a[1][1] = 1;
    两个盘子的时候: a[2][1] = 2, a[2][2] = 1;
    三个盘子的时候: a[3][1] = 4, a[3][2] = 2, a[3][3] = 1； 
    .........，依次类推
    得知；递推公式为:dp[n][i]=dp[n-1][i]*2(1<=i<n),且dp[n][n] = 1; 
           大盘子移动的次数是他上一个移动次数的1/2 
*/
int main(){

    int i,j,n,m;
    dp[1][1] = 1;
    dp[2][1] = 2;
    dp[2][2] = 1;
    for(i=3;i<=61;i++){ //代表有i个盘子 
        for(j=1;j<i;j++){//当i个盘子的时候第j个盘子移动的次数 
            dp[i][j] = dp[i-1][j]*2;
        }
        dp[i][i] = 1;//或dp[i][j] =1; 
    } 


    while(cin>>n){

        while(n--){
            cin>>m>>i;
            cout<<dp[m][i]<<endl;//m个盘子中第i个盘子移动的次数 
        }

    } 


    return 0;
}

汉诺塔VI

Problem Description
n个盘子的汉诺塔问题的最少移动次数是2^n-1,即在移动过程中会产生2^n个系列。由于
发生错移产生的系列就增加了，这种错误是放错了柱子，并不会把大盘放到小盘上，即各柱
子从下往上的大小仍保持如下关系 ：
n=m+p+q
a1>a2>…>am
b1>b2>…>bp
c1>c2>…>cq
计算所有会产生的系列总数.

Input
包含多组数据，首先输入T,表示有T组数据.每个数据一行，是盘子的数
目N<30.

Output
对于每组数据，输出移动过程中所有会产生的系列总数。

Sample Input
3
1
3
29

Sample Output
3
27
68630377364883

代码:
思路:
在经典汉若塔问题上，求一共有多少个状态（包括所有可能移到到的状态），一个排列组合问题，
答案：求和（ C(k1,n)*C(k2,n-k1)）其中n>=k1>=0,n-k1>=K2>=0,从中挑出K1个从小到大放在A塔，再从剩下的
挑出K2个放在B塔，剩余的放在C塔即可。数据非大数。

# include <iostream>

using namespace std;

long long C(int n,int m){//计算C(n,m);n>=m

    if(n==0||m==0){
        return 1;
    }

    if(m<n-m) m = n - m;
    long long ans = 1;
    for(int i=m+1;i<=n;i++){
        ans*=i;
    }
    for(int i=1;i<=n-m;i++){
        ans/=i;
    }

    return ans;
}

long long a[35];
int main(){

    int n,m,i,j,k1,k2;

    for(i=1;i<=31;i++){//当i个盘子的时候
        for(k1=0;k1<=i;k1++){//A柱子k1个 
            for(k2=0;k2<=i-k1;k2++){//B柱子有k2个
                a[i] += C(i,k1)*C(i-k1,k2); //累计
            }
        }
    }

    while(cin>>n){
        while(n--){
            cin>>m;
            cout<<a[m]<<endl;
        }
    }

    return 0;
}