做了这一系列题，表示对汉诺塔与这一系列递推理解加深了

经典汉诺塔：1,2,...,n表示n个盘子，数字大盘子就大，n个盘子放在第１根柱子上，按照从上到下 从小到大的顺序排放，过程中每次大盘都不能放在小盘上． 把n个盘子移动到第３根柱子．每次只能移动１个盘子，求把第１根柱子上的盘子全部移动到第3根柱子上需要的最少步数

解法：我们使用dp[n]表示移动前n个盘子从第1根柱子到第3根柱子需要的步数，则我们需要这么做：首先移动前n-1个盘子从1到2，接着移动第n个盘子从1到3，最后我们移动前n-1个盘子从2到3。则我们的步骤就是递推算法：dp[n]=dp[n-1]+1+dp[n-1]，化简就是dp[n]=2^n-1

HDU 1207 汉诺塔II

题意：将基础汉诺塔的三根柱子换成四根，其他不变

题解：http://www.cnblogs.com/fanzhidongyzby/archive/2012/07/28/2613173.html

dp(n)=min(2*dp(n-r)+2^r-1)，（1≤r≤n）

#include<set>

#include<map>

#include<queue>

#include<stack>

#include<cmath>

#include<vector>

#include<string>

#include<cstdio>

#include<cstring>

#include<iomanip>

#include<stdlib.h>

#include<iostream>

#include<algorithm>

using namespace std;

#define eps 1E-8

/*注意可能会有输出-0.000*/

#define Sgn(x) (x<-eps? -1 :x<eps? 0:1)//x为两个浮点数差的比较,注意返回整型

#define Cvs(x) (x > 0.0 ? x+eps : x-eps)//浮点数转化

#define zero(x) (((x)>0?(x):-(x))<eps)//判断是否等于0

#define mul(a,b) (a<<b)

#define dir(a,b) (a>>b)

typedef long long ull;

typedef unsigned long long ll;

const int Inf=<<;

const ll INF=1ll<<;

const double Pi=acos(-1.0);

const int Mod=1e9+;

const int Max=;

ll dp[Max];

ll Mtp(ll num,ll mul)

{

    ll sum=1ll;

    while(mul)

    {

        if(mul&1ll)

            sum*=num;

        num*=num;

        mul>>=1ll;

    }

    return sum;

}

void Init(int n)

{

    dp[]=,dp[]=;

    for(int i=; i<n; ++i)

    {

        dp[i]=2ll*dp[i-]+2ll-1ll;

        for(int j=; j<=i; ++j)

            dp[i]=min(dp[i],2ll*dp[i-j]+Mtp(2ll,(ll)j)-1ll);

    }

    return;

}

int main()

{

    Init();

    int n;

    while(~scanf("%d",&n))

    {

        printf("%llu\n",dp[n]);

    }

    return ;

}

HDU 2064 汉诺塔III

题意：标准汉诺塔，接着不允许直接从最左(右)边移到最右(左)边(每次移动一定是移到中间杆或从中间移出)，输出移动最小的次数

题解：与标准汉诺塔一样移动但有限制，所以就是dp[n]=3dp[n-1]+2

#include<set>

#include<map>

#include<queue>

#include<stack>

#include<cmath>

#include<vector>

#include<string>

#include<cstdio>

#include<cstring>

#include<iomanip>

#include<stdlib.h>

#include<iostream>

#include<algorithm>

using namespace std;

#define eps 1E-8

/*注意可能会有输出-0.000*/

#define Sgn(x) (x<-eps? -1 :x<eps? 0:1)//x为两个浮点数差的比较,注意返回整型

#define Cvs(x) (x > 0.0 ? x+eps : x-eps)//浮点数转化

#define zero(x) (((x)>0?(x):-(x))<eps)//判断是否等于0

#define mul(a,b) (a<<b)

#define dir(a,b) (a>>b)

typedef long long ll;

typedef unsigned long long ull;

const int Inf=<<;

const ll INF=1ll<<;

const double Pi=acos(-1.0);

const int Mod=1e9+;

const int Max=;

ull dp[Max];

void Init(int n)

{

    dp[]=2ull;

    for(int i=;i<n;++i)

    {

        dp[i]=3ull*dp[i-]+;

        //printf("%llu\n",dp[i]);

    }

}

int main()

{

    Init();

    int n;

    while(~scanf("%d",&n))

        printf("%llu\n",dp[n]);

    return ;

}

HDU 2077 汉诺塔IV

题意：在III的基础上，添加了可以将最大的一块放到其他的上面

题解：特判1，接着前n块就是前n-1块再移动第n块的两次就好

#include<set>

#include<map>

#include<queue>

#include<stack>

#include<cmath>

#include<vector>

#include<string>

#include<cstdio>

#include<cstring>

#include<iomanip>

#include<stdlib.h>

#include<iostream>

#include<algorithm>

using namespace std;

#define eps 1E-8

/*注意可能会有输出-0.000*/

#define Sgn(x) (x<-eps? -1 :x<eps? 0:1)//x为两个浮点数差的比较,注意返回整型

#define Cvs(x) (x > 0.0 ? x+eps : x-eps)//浮点数转化

#define zero(x) (((x)>0?(x):-(x))<eps)//判断是否等于0

#define mul(a,b) (a<<b)

#define dir(a,b) (a>>b)

typedef long long ll;

typedef unsigned long long ull;

const int Inf=<<;

const ll INF=1ll<<;

const double Pi=acos(-1.0);

const int Mod=1e9+;

const int Max=;

ull dp[Max];

void Init(int n)

{

    dp[]=2ull;

    for(int i=;i<n;++i)

    {

        dp[i]=3ull*dp[i-]+;

    }

    return;

}

int main()

{

    Init();

    int t,n;

    scanf("%d",&t);

    while(t--)

    {

        scanf("%d",&n);

        if(n==)

            printf("2\n");

        else

        printf("%llu\n",dp[n-]+);

    }

    return ;

}

HDU 1995 汉诺塔V

题意：标准汉诺塔计算n个盘子的第m个盘子移动的次数

题解：打表找规律：2^(n-m)

#include<set>

#include<map>

#include<queue>

#include<stack>

#include<cmath>

#include<vector>

#include<string>

#include<cstdio>

#include<cstring>

#include<iomanip>

#include<stdlib.h>

#include<iostream>

#include<algorithm>

using namespace std;

#define eps 1E-8

/*注意可能会有输出-0.000*/

#define Sgn(x) (x<-eps? -1 :x<eps? 0:1)//x为两个浮点数差的比较,注意返回整型

#define Cvs(x) (x > 0.0 ? x+eps : x-eps)//浮点数转化

#define zero(x) (((x)>0?(x):-(x))<eps)//判断是否等于0

#define mul(a,b) (a<<b)

#define dir(a,b) (a>>b)

typedef long long ll;

typedef unsigned long long ull;

const int Inf=<<;

const ll INF=1ll<<;

const double Pi=acos(-1.0);

const int Mod=1e9+;

const int Max=;

ull dp[Max][Max];

ull Mtp(ull num,ull mul)

{

    ull sum=1ull;

    while(mul)

    {

        if(mul&1ull)

            sum*=num;

        num*=num;

        mul>>=1ull;

    }

    return sum;

}

void Init(int n)

{

    for(int i=;i<n;++i)

    {

        for(int j=i;j>=;--j)

        {

            dp[i][j]=Mtp(2ull,(ull)i-j);

            //printf("%d %d %llu\n",i,j,dp[i][j]);

        }

    }

    return;

}

int main()

{

    Init();

    int t,n,m;

    scanf("%d",&t);

    while(t--)

    {

        scanf("%d %d",&n,&m);

        printf("%llu\n",dp[n][m]);

    }

    return ;

}

HDU 1996 汉诺塔VI

题意：三根柱子上按照汉诺塔的规则放盘子（注意不是最小次数移动的排列数），输出所有可能性的总个数

题解：排列组合：3^n

#include<set>

#include<map>

#include<queue>

#include<stack>

#include<cmath>

#include<vector>

#include<string>

#include<cstdio>

#include<cstring>

#include<iomanip>

#include<stdlib.h>

#include<iostream>

#include<algorithm>

using namespace std;

#define eps 1E-8

/*注意可能会有输出-0.000*/

#define Sgn(x) (x<-eps? -1 :x<eps? 0:1)//x为两个浮点数差的比较,注意返回整型

#define Cvs(x) (x > 0.0 ? x+eps : x-eps)//浮点数转化

#define zero(x) (((x)>0?(x):-(x))<eps)//判断是否等于0

#define mul(a,b) (a<<b)

#define dir(a,b) (a>>b)

typedef long long ll;

typedef unsigned long long ull;

const int Inf=<<;

const ll INF=1ll<<;

const double Pi=acos(-1.0);

const int Mod=1e9+;

const int Max=;

ll dp[Max];

void Init(int n)

{

    dp[]=3ll;

    for(int i=;i<n;++i)

        dp[i]=dp[i-]*3ll;

    return;

}

int main()

{

    Init();

    int n,t;

    scanf("%d",&t);

    while(t--)

    {

        scanf("%d",&n); printf("%lld\n",dp[n]);

    }

    return ;

}

HDU 1997 汉诺塔VII

题意：给定三根柱子上放盘子的顺序，判断是否是最小移动过程中会产生的顺序

题解：我们看汉诺塔移动的规则：n-1个盘子A->B，第n个盘子A->C:这时可看做A,B柱子交换的顺序

因此我们可以看第n个盘子放在哪个柱子上，如果放在B柱子上，则可以判断答是否。

如果放在A柱子上，则交换B,C柱子，如果放在C柱子上，则交换A,B柱子，接着换后再看第n-1个盘子，递归到第1个盘子

#include<set>

#include<map>

#include<queue>

#include<stack>

#include<cmath>

#include<vector>

#include<string>

#include<cstdio>

#include<cstring>

#include<iomanip>

#include<stdlib.h>

#include<iostream>

#include<algorithm>

using namespace std;

#define eps 1E-8

/*注意可能会有输出-0.000*/

#define Sgn(x) (x<-eps? -1 :x<eps? 0:1)//x为两个浮点数差的比较,注意返回整型

#define Cvs(x) (x > 0.0 ? x+eps : x-eps)//浮点数转化

#define zero(x) (((x)>0?(x):-(x))<eps)//判断是否等于0

#define mul(a,b) (a<<b)

#define dir(a,b) (a>>b)

typedef long long ll;

typedef unsigned long long ull;

const int Inf=<<;

const ll INF=1ll<<;

const double Pi=acos(-1.0);

const int Mod=1e9+;

const int Max=;

int x,y,z,flag;

void dfs(int now,int *a,int *b,int *c)//当a或者c的值为now时，可看做a->c,然后b与a柱子交换

{

    if(!now)

        return;

    if(*a==now)

    {

        dfs(now-,a+,c,b);

    }

    else if(*c==now)

    {

        dfs(now-,b,a,c+);

    }

    else

        flag=;

    return;

}

int num[][Max];

int main()

{

    int t,n;

    scanf("%d",&t);

    while(t--)

    {

        scanf("%d",&n);

        scanf("%d",&x);

        for(int i=; i<x; ++i)

        {

            scanf("%d",&num[][i]);

        }

        num[][x]=;

        scanf("%d",&y);

        for(int i=; i<y; ++i)

        {

            scanf("%d",&num[][i]);

        }

        num[][y]=;

        scanf("%d",&z);

        for(int i=; i<z; ++i)

        {

            scanf("%d",&num[][i]);

        }

        num[][z]=;

        flag=;

        dfs(n,num[],num[],num[]);

        if(flag)

            printf("true\n");

        else

            printf("false\n");

    }

    return ;

}

HDU 2184 汉诺塔VIII

题意：汉诺塔移动m次后的情况

题解：找到dp[n],再二分找到第n个盘子放的柱子，接着模拟上一个汉诺塔进行柱子交换

#include<set>

#include<map>

#include<queue>

#include<stack>

#include<cmath>

#include<vector>

#include<string>

#include<cstdio>

#include<cstring>

#include<iomanip>

#include<stdlib.h>

#include<iostream>

#include<algorithm>

using namespace std;

#define eps 1E-8

/*注意可能会有输出-0.000*/

#define Sgn(x) (x<-eps? -1 :x<eps? 0:1)//x为两个浮点数差的比较,注意返回整型

#define Cvs(x) (x > 0.0 ? x+eps : x-eps)//浮点数转化

#define zero(x) (((x)>0?(x):-(x))<eps)//判断是否等于0

#define mul(a,b) (a<<b)

#define dir(a,b) (a>>b)

typedef long long ll;

typedef unsigned long long ull;

const int Inf=<<;

const ll INF=1ll<<;

const double Pi=acos(-1.0);

const int Mod=1e9+;

const int Max=;

void dfs(int now,int *a,int *b,int *c,ll m,ull sum)

{

    if(!now)

        return;

    if(sum/2ull>m)//左边

    {

        *a=now;

        *(a+)=;

        dfs(now-,a+,c,b,m,sum/);

    }

    else

    {

        *c=now;

        *(c+)=;

        dfs(now-,b,a,c+,m-sum/,sum/);

    }

    return;

}

int num[][Max];

ull Mtp(ull dig,ull mul)

{

    ull sum=1ull;

    while(mul)

    {

        if(mul&)

            sum*=dig;

        dig*=dig;

        mul>>=1ull;

    }

    return sum;

}

void Solve(int n,ll m)

{

    int a,b,c;

    ull sum=Mtp(2ull,(ull)n);

    dfs(n,num[],num[],num[],m,sum);

    for(a=; num[][a]; ++a);

    for(b=; num[][b]; ++b);

    for(c=; num[][c]; ++c);

    printf("%d",a);

    for(int i=;i<a;++i)

        printf(" %d",num[][i]);

    printf("\n");

        printf("%d",b);

    for(int i=;i<b;++i)

        printf(" %d",num[][i]);

    printf("\n");

        printf("%d",c);

    for(int i=;i<c;++i)

        printf(" %d",num[][i]);

    printf("\n");

    return ;

}

int main()

{

    int t,n;

    ll m;

    scanf("%d",&t);

    while(t--)

    {

        scanf("%d %I64d",&n,&m);

        Solve(n,m);

    }

    return ;

}

HDU 2077 汉诺塔IX

题意：标准汉诺塔求第m次移动的是那一个盘子

题解：求出移动m-1次后情况与移动m次后的情况，通过三个柱子上最上面的盘子的情况来看

#include<set>

#include<map>

#include<queue>

#include<stack>

#include<cmath>

#include<vector>

#include<string>

#include<cstdio>

#include<cstring>

#include<iomanip>

#include<stdlib.h>

#include<iostream>

#include<algorithm>

using namespace std;

#define eps 1E-8

/*注意可能会有输出-0.000*/

#define Sgn(x) (x<-eps? -1 :x<eps? 0:1)//x为两个浮点数差的比较,注意返回整型

#define Cvs(x) (x > 0.0 ? x+eps : x-eps)//浮点数转化

#define zero(x) (((x)>0?(x):-(x))<eps)//判断是否等于0

#define mul(a,b) (a<<b)

#define dir(a,b) (a>>b)

typedef long long ll;

typedef unsigned long long ull;

const int Inf=<<;

const ll INF=1ll<<;

const double Pi=acos(-1.0);

const int Mod=1e9+;

const int Max=;

void dfs(int now,int *a,int *b,int *c,ull m,ull sum)

{

    if(!now)

        return;

    if(sum/2ull>m)//左边

    {

        *(a+)=now;

        *(a+)=;

        dfs(now-,a+,c,b,m,sum/);

    }

    else

    {

        *(c+)=now;

        *(c+)=;

        dfs(now-,b,a,c+,m-sum/,sum/);

    }

    return;

}

int num[][][Max];

ull Mtp(ull dig,ull mul)

{

    ull sum=1ull;

    while(mul)

    {

        if(mul&)

            sum*=dig;

        dig*=dig;

        mul>>=1ull;

    }

    return sum;

}

int Solve(int n,ull m)

{

    int dig[];

    memset(num,,sizeof(num));

    dfs(n,num[][],num[][],num[][],m-1ull,Mtp(2ull,(ull)n));

    dfs(n,num[][],num[][],num[][],m,Mtp(2ull,(ull)n));

    int a1,a2,b1,b2,c1,c2;

    for(a1=;num[][][a1];++a1);

    for(a2=;num[][][a2];++a2);

    for(b1=;num[][][b1];++b1);

    for(b2=;num[][][b2];++b2);

    for(c1=;num[][][c1];++c1);

    for(c2=;num[][][c2];++c2);

    int coun=;

    if(num[][][a1-]!=num[][][a2-])

    {

        dig[coun++]=num[][][a1-];

        dig[coun++]=num[][][a2-];

    }

    if(num[][][b1-]!=num[][][b2-])

    {

        dig[coun++]=num[][][b1-];

        dig[coun++]=num[][][b2-];

    }

    if(num[][][c1-]!=num[][][c2-])

    {

        dig[coun++]=num[][][c1-];

        dig[coun++]=num[][][c2-];

    }

        sort(dig,dig+coun);

    for(int i=;i<coun-;++i)

    {

        if(dig[i]==dig[i+]&&dig[i])

        {

                return dig[i];

        }

    }

}

int main()

{

    std::ios::sync_with_stdio(false);

    int n;

    ull m;

    while(cin >> n >> m)

    {

        if(!n&&n==0ull)

            break;

            cout << Solve(n,m) << endl;

    }

    return ;

}

HDU  2511 汉诺塔X

题意：标准汉诺塔求第m次移动的是那一个盘子，并且求出是从哪个柱子移到哪个柱子

题解：与前一个汉诺塔一样

#include<set>

#include<map>

#include<queue>

#include<stack>

#include<cmath>

#include<vector>

#include<string>

#include<cstdio>

#include<cstring>

#include<iomanip>

#include<stdlib.h>

#include<iostream>

#include<algorithm>

using namespace std;

#define eps 1E-8

/*注意可能会有输出-0.000*/

#define Sgn(x) (x<-eps? -1 :x<eps? 0:1)//x为两个浮点数差的比较,注意返回整型

#define Cvs(x) (x > 0.0 ? x+eps : x-eps)//浮点数转化

#define zero(x) (((x)>0?(x):-(x))<eps)//判断是否等于0

#define mul(a,b) (a<<b)

#define dir(a,b) (a>>b)

typedef long long ll;

typedef unsigned long long ull;

const int Inf=<<;

const ll INF=1ll<<;

const double Pi=acos(-1.0);

const int Mod=1e9+;

const int Max=;

void dfs(int now,int *a,int *b,int *c,ull m,ull sum)

{

    if(!now)

        return;

    if(sum/2ull>m)//左边

    {

        *(a+)=now;

        *(a+)=;

        dfs(now-,a+,c,b,m,sum/);

    }

    else

    {

        *(c+)=now;

        *(c+)=;

        dfs(now-,b,a,c+,m-sum/,sum/);

    }

    return;

}

int num[][][Max];

ull Mtp(ull dig,ull mul)

{

    ull sum=1ull;

    while(mul)

    {

        if(mul&)

            sum*=dig;

        dig*=dig;

        mul>>=1ull;

    }

    return sum;

}

void Solve(int n,ull m)

{

    int dig[];

    memset(num,,sizeof(num));

    dfs(n,num[][],num[][],num[][],m-1ull,Mtp(2ull,(ull)n));

    dfs(n,num[][],num[][],num[][],m,Mtp(2ull,(ull)n));

    int a1,a2,b1,b2,c1,c2;

    for(a1=;num[][][a1];++a1);

    for(a2=;num[][][a2];++a2);

    for(b1=;num[][][b1];++b1);

    for(b2=;num[][][b2];++b2);

    for(c1=;num[][][c1];++c1);

    for(c2=;num[][][c2];++c2);

    int coun=;

    if(num[][][a1-]!=num[][][a2-])

    {

        dig[coun++]=num[][][a1-];

        dig[coun++]=num[][][a2-];

    }

    if(num[][][b1-]!=num[][][b2-])

    {

        dig[coun++]=num[][][b1-];

        dig[coun++]=num[][][b2-];

    }

    if(num[][][c1-]!=num[][][c2-])

    {

        dig[coun++]=num[][][c1-];

        dig[coun++]=num[][][c2-];

    }

    int temp;

        sort(dig,dig+coun);

    for(int i=;i<coun-;++i)

    {

        if(dig[i]==dig[i+]&&dig[i])

        {

                cout << dig[i] << " ";

                temp=dig[i];

                break;

        }

    }

    if(num[][][a1-]==temp)

        cout << "1 ";

        if(num[][][b1-]==temp)

        cout << "2 ";

            if(num[][][c1-]==temp)

        cout << "3 ";

        if(num[][][a2-]==temp)

        cout << "" << endl;

        if(num[][][b2-]==temp)

        cout << "" << endl;

            if(num[][][c2-]==temp)

        cout << "" << endl;

    return;

}

int main()

{

    std::ios::sync_with_stdio(false);

    int n,t;

    ull m;

    cin >> t;

    while(t--)

    {

        cin >> n >> m;

            Solve(n,m);;

    }

    return ;

}

最新文章

  1. 利用python的双向队列(Deque)数据结构实现回文检测的算法
  2. PHP 文件与文件夹的创建和删除操作
  3. javascript 技巧
  4. import和from import陷阱二
  5. struts2--表单重复提交
  6. XML 文档和数据
  7. 使用WinDbg调试SQL Server——入门
  8. cmd下常用的一些命令
  9. 从0 开始 WPF MVVM 企业级框架实现与说明 ---- 第三讲 WPF中 DataTemplate
  10. 【BZOJ】【3894】文理分科
  11. 【USACO】【Section1.1】Greedy Gift Givers
  12. 利用C++ RAII技术自动回收堆内存
  13. 移动端js插件分享
  14. Welcome Docker to SUSE Linux Enterprise Server【水平有限，中英对比，求纠错】
  15. MySQL导入乱码解决
  16. C#编写影院售票系统（A project with a higher amount of gold ）（2:相关代码）
  17. Python图片裁剪
  18. XamarinAndroid组件教程设置动画的时长参数
  19. python 文件读写时用open还是codecs.open
  20. [Java初探08]__简单学习Java类和对象

热门文章

  1. [NSDate distantPast]使用
  2. TP表单验证
  3. node.js调用模块
  4. 任务04——对四则运算小程序的进一步改进，并学习 Git 中 Branch 的用法
  5. 控制台程序的中文输出乱码问题（export LC_CTYPE=zh_CN.GBK，或者修改/etc/sysconfig/i18n为zh_CN.GBK。使用setlocale(LC_CTYPE, &quot;&quot;);会使用默认办法。编译器会将源码做转换成Unicode格式，或者指定gcc的输入文件的编码参数-finput-charset=GBK。Linux下应该用wprintf(L&quot;%ls/n&quot;,wstr)）
  6. python的语法规范及for和while
  7. 0102-使用 API 网关构建微服务
  8. 20170524 委外采购的物料BOM
  9. Kafka配置参数说明
  10. 【jenkins】jenkins实时显示python脚本输出