游客 注册 | 登录
中文 | En

2038 - 汉诺塔

通过次数

0

提交次数

0

时间限制 : 1 秒 内存限制 : 128 MB

汉诺塔是根据一个传说形成的一个问题：
有三根杆子A，B，C。A杆上有N个(N>1)穿孔圆盘，盘的尺寸由下到上依次变小。要求按下列规则将所有圆盘移至C杆：
1.每次只能移动一个圆盘；
2.大盘不能叠在小盘上面。
提示：可将圆盘临时置于B杆，也可将从A杆移出的圆盘重新移回A杆，但都必须遵循上述两条规则。
问：如何移，最少要移动多少次？

MiaoWu玩三根杆子移动圆盘玩腻了。于是，它从寝室偷了m-3根杆子，想用这m根杆子来移动盘子，问n个盘子从起始盘移动到目标盘，至少需要移动多少步？

题目输入

输入m,n到文件末尾结束（3<=m<=20 , 0<=n<=1000）

题目输出

输出最小移动步数

输入/输出样例

输入格式

3 3
3 4
3 5
4 1
4 12

输出格式

7
15
31
1
81

C++解答

#include<stdio.h>
#include<string.h>
#include<ctime>
#include<vector>
#include<algorithm>
using namespace std;

#define N 1000000000
inline vector<int> change(int val)
{
    vector<int>ans;
    while(val)
    {
        ans.push_back(val%N);
        val/=N;
    }
    return ans;
}
inline vector<int> equ(vector<int> a)
{
    vector<int>ans;
    for(int i=0;i<a.size();i++)
        ans.push_back(a[i]);
    return ans;
}
inline vector<int> Min(vector<int> a,vector<int> b)
{
    if(a.size()>b.size()) return b;
    else if(a.size()<b.size()) return a;
    else
    {
        for(int i=a.size()-1;i>=0;i--)
        {
            if(a[i]<b[i]) return a;
            else if(a[i]>b[i]) return b;
        }
        return a;
    }
}
inline vector<int> add(vector<int>a,vector<int>b)
{
    vector<int>ans;
    int l1=a.size(),l2=b.size(),l=0;
    int m=0;
    while(l<min(l1,l2))
    {
        int p=a[l]+b[l]+m;
        m=p/N;
        ans.push_back(p%N);
        l++;
    }
    while(l<l1)
    {
        int p=a[l]+m;
        m=p/N;
        ans.push_back(p%N);
        l++;
    }
    while(l<l2)
    {
        int p=b[l]+m;
        m=p/N;
        ans.push_back(p%N);
        l++;
    }
    if(m!=0) ans.push_back(m);
    return ans;
}
inline void Print(vector<int> a)
{
    for(int i=a.size()-1;i>=0;i--)
    {
        printf("%d",a[i]);
    }
    printf("\n");
}

vector<int>dp[21][1001];
inline void init()
{
    for(int i=3;i<=20;i++)
        dp[i][1].push_back(1);
    for(int i=3;i<=20;i++)
        dp[i][2].push_back(3);
    for(int i=3;i<=1000;i++)
    {
        dp[3][i]=add(dp[3][1],add(dp[3][i-1],dp[3][i-1]));//dp[3][1]);
    }
    for(int i=4;i<=20;i++)
        for(int j=3;j<=1000;j++)
    {        dp[i][j]=add(dp[i-1][1],add(dp[i][j-1],dp[i][j-1]));//,dp[i-1][1]);
        for(int k=2;k<=j;k++)
        {
            dp[i][j]=Min(dp[i][j],add(dp[i-1][k],add(dp[i][j-k],dp[i][j-k])));//dp[i-1][k]));
        }
    }
}

int main()
{
    int m,n;
    init();
    //printf("zz\n");
    while(~scanf("%d%d",&m,&n))
    {
        if(n==0)
            printf("0\n");
        else
            Print(dp[m][n]);
    }
}

Java解答

import java.math.BigDecimal;
import java.math.BigInteger;
import java.util.Scanner;

public class Main
{
    public static BigInteger min(BigInteger a,BigInteger b)
    {
        if(a.compareTo(b)<0)
            return a;
        return b;
    }
    public static void main(String args[])
    {
        Scanner cin=new Scanner(System.in);
        int maxn=1100;
        BigInteger dp[][]=new BigInteger[21][maxn];
        for(int i=0;i<maxn;i++)
        {
            dp[2][i]=BigInteger.ZERO;
            dp[3][i]=BigInteger.valueOf(2).pow(i).subtract(BigInteger.ONE);
        }
        dp[2][1]=BigInteger.ONE;
        for(int i=4;i<21;i++)
        {
            dp[i][0]=BigInteger.ZERO;
            for(int j=1;j<maxn;j++)
            {
                dp[i][j]=dp[i-1][j];
                for(int k=0;k<=j;k++)
                    dp[i][j]=min(dp[i][j],dp[i][j-k].multiply(BigInteger.valueOf(2)).add(dp[i-1][k]));
            }
        }
        while(cin.hasNext())
        {
            int m=cin.nextInt();
            int n=cin.nextInt();
            System.out.println(dp[m][n]);
        }
    }

}
请先登陆