汉诺塔系列问题（hdu)

骑猪看日落 2022-05-06 16:27 175阅读 0赞

*   
 *  1.hdu1995

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

#include<iostream>
    using namespace std;
    int main()
    {
        int t,n,k,i;
        long long s;
        cin>>t;
        while(t--)
        {
            s=1;
            cin>>n>>k;
            for(i=0;i<n-k;i++)
            {
                s*=2;
            } 
                cout<<s<<endl;
                 
        } 
        return 0;
    }

*  2.hdu1996

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  
    //  
    **其实它就是求移动的所有可能，也就是n个盘子摆在三个塔上的任何可能的种数。  
    可以这么思考这个问题：n个盘子分开摆在三个塔上，所有可能的种数（这个和高中  
    时候的一个信封投递到邮箱的问题很类似，那个是4封信投到3个邮箱，求投的种数的）  
    ；n个盘子，每个盘子有3种摆法，所以n个盘子摆在3个塔上的摆法就有3n种。知道  
    这个规律之后，我们的问题就迎刃而解了**。
 *      #include<iostream>
        #include<cmath>
        using namespace std;
        int main()
        {
        	int t,n;
        	long long k;
        	cin>>t;
        	while(t--)
        	{
        		cin>>n;
        		k=pow(3,n);
        		cout<<k<<endl;
        	} 
        	return 0;
        }
    
    3.hdu1207
 *  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\]为所求的最小步数，显然f\[0\]=0,f\[1\]=1,f\[2\]=3,f\[3\]=5;如同经典汉诺塔一样，我们将移完盘子的任务分为三步：  
         （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\];  
          故完成任务所需要的总的步数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\]的最小值。数值不是很大，int完全可以搞定，代码如下:**  
          \*/
 *      #include <iostream>
        #include <cmath>
        using namespace std;
        int main()
        {
            int n,min,f[65];;
            f[1] = 1;
            f[2] = 3;
            for (int i = 3;i < 65;i++)
            {
                min = 99999999;
                for (int x = 1;x < i;x++)
                    if (2*f[x] + pow(2.0,i-x)-1 < min)
                       min = 2*f[x] + (int)pow(2.0,i-x)-1;
                f[i] = min;
            }
            while (cin >> n)
                  cout << f[n] << endl;
            return 0;
        }
    
    4.hdu2077
 *  Problem Description  
    还记得汉诺塔III吗？他的规则是这样的：不允许直接从最左(右)边移到最右(左)边(每次移动一定是移到中间杆或从中间移出)，也不允许大盘放到小盘的上面。xhd在想如果我们允许最大的盘子放到最上面会怎么样呢？（只允许最大的放在最上面）当然最后需要的结果是盘子从小到大排在最右边。  
    Input  
    输入数据的第一行是一个数据T，表示有T组数据。  
    每组数据有一个正整数n(1 <= n <= 20)，表示有n个盘子。  
    Output  
    对于每组输入数据，最少需要的摆放次数。  
    Sample Input  
    2  
    1  
    10  
    Sample Output  
    2  
    19684

#include<iostream>
    #include<cmath>
    using namespace std;
    int main()
    {
        int t,n;
        long long m;
        cin>>t;
        while(t--)
        {
            cin>>n;
            m=pow(3,n-1)+1;
            cout<<m<<endl; 
        }
        return 0;
    }

*  hdu2175
 *  Problem Description  
    1,2,...,n表示n个盘子．数字大盘子就大．n个盘子放在第１根柱子上．大盘不能放在小盘上．   
    在第１根柱子上的盘子是a\[1\],a\[2\],...,a\[n\]. a\[1\]=n,a\[2\]=n-1,...,a\[n\]=1.即a\[1\]是最下   
    面的盘子．把n个盘子移动到第３根柱子．每次只能移动１个盘子，且大盘不能放在小盘上．   
    问第m次移动的是那一个盘子.  
    Input  
    每行2个整数n (1 ≤ n ≤ 63) ,m≤ 2^n-1.n=m=0退出  
    Output  
    输出第m次移动的盘子的号数．  
    Sample Input  
    63 1  
    63 2  
    0 0  
    Sample Output  
    1  
    2
    
        #include<iostream>
        using namespace std;
        int main()
        {
            int n;
            long long m,i,t;
            while(cin>>n>>m&&(n!=0&&m!=0))
            {
                for(i=1;i<=n;i++)
                {
                    t=m%2;
                    if(t==1)
                    {
                        cout<<i<<endl;
                        break;
                    }
                    else
                    m/=2;
                }    
            } 
            return 0;
        }