MyException - 我的异常网
当前位置:我的异常网» 编程 » 汉诺塔系列有关问题: 汉诺塔II、汉诺塔III、汉诺塔

汉诺塔系列有关问题: 汉诺塔II、汉诺塔III、汉诺塔IV、汉诺塔V、汉诺塔VI、汉诺塔VII

www.MyException.Cn  网友分享于:2014-07-11  浏览:0次
汉诺塔系列问题: 汉诺塔II、汉诺塔III、汉诺塔IV、汉诺塔V、汉诺塔VI、汉诺塔VII

 汉诺塔II:(hdu1207)

/先说汉若塔I(经典汉若塔问题),有三塔,A塔从小到大从上至下放有N个盘子,现在要搬到目标C上,

规则小的必需放在大的上面,每次搬一个,求最小步数。这个问题简单,DP:a[n]=a[n-1]+1+a[n-1],先把

上面的n-1个放在B上,把最大的放在目标C上,再把N-1个放回到C上即可。

</pre><p></p>现在是汉若塔II,改为四个塔,开始方程想简单了,不是最优的。给出网上的一种最优解法如下:(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]的最小值。方法很容易理解,但是还有其他摆法(如第一步未必先要把所有X个放到一个非目标底座上),目前无法证<p>明其最优性,证明还需求路过大神指导。</p><p></p><pre name="code" class="cpp">#include<iostream>
#include<cmath>
using namespace std;
unsigned long long a[65];
 const unsigned long long one=1;
int main()
{
    a[1]=1;a[2]=3;
    for(int i=3;i<65;i++)
    {
       unsigned long long min=(one<<(i-1))-1+2*a[1];
        for(int j=2;j<i;j++)
        {
            if(2*a[j]+(one<<(i-j))-1<min)
             min=2*a[j]+(one<<(i-j))-1;
        }
        a[i]=min;
    }
    int n;
    while(cin>>n)
    {
        cout<<a[n]<<endl;
    }
    return 0;
}


汉若塔III  hdu2064

在经典汉若塔问题的条件改为,每次只能移动到附近塔上,求把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<iostream>
#include<cmath>
using namespace std;
unsigned long long a[65];
int main()
{
    a[1]=2;
    for(int i=2;i<36;i++)
    {
        a[i]=3*a[i-1]+2;
    }
    int n;
    while(cin>>n)
    {
        cout<<a[n]<<endl;
    }
    return 0;
}


汉若塔IV HDU 2077

在汉若塔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 HDU1995
在经典汉若塔问题上附加问题:求出N个盘子时,第K号盘子的移动次数。
思路,一想就是二维DP,DP[n][i]=dp[n-1][i]*2(1=<i<n),dp[n][n]=1;
最大盘只移动一次,上面盘子先移到B塔,一次,最后由B到目标C又一次,思路清晰,分分钟KO。

#include<iostream>
#include<cmath>
using namespace std;
unsigned long long dp[62][62];
int main()
{
    dp[1][1]=1;dp[2][1]=2;dp[2][2]=1;
    for(int i=3;i<61;i++)
    {
       for(int j=1;j<i;j++)
       {
           dp[i][j]=2*dp[i-1][j];
       }
       dp[i][i]=1;
    }
    int t;
    int n,m;
    cin>>t;
    while(t--)
    {
        cin>>n>>m;
        cout<<dp[n][m]<<endl;
    }
    return 0;
}


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

其他巧妙方法:每个盘从小到大每个都有3种选择,共3^n。


#include<iostream>
using namespace std;
unsigned long long a[32];
long long C(int m,int n)  //M>=N
{
    if(m==0||n==0)return 1;
       int i;
       long long c=1,s=1;
       if(n>m-n)
       {
                n=m-n;
       }
       for(i=m;i>=m-n+1;i--)
       {
           c=c*i;
       }
       for(i=n;i>1;i--)
       {
             s*=i;
        }

       c=c/s;
       return c;
}
int main()
{
    for(int i=1;i<30;i++)
    {
       for(int k1=0;k1<=i;k1++)
       {
          for(int k2=0;k2<=i-k1;k2++)
             {
                 a[i]+=C(i,k1)*C(i-k1,k2);
             }
       }
    }
    int t;
    int n,m;
    cin>>t;
    while(t--)
    {
        cin>>n;
        cout<<a[n]<<endl;
    }
    return 0;
}



汉诺塔VII hdu1997 在经典汉若塔问题上,给出任意一个状态(移到过程中),判断该状态是否在正确的(最小移到情况)状态
中。
思路:做到这题,汉若塔就很清晰了,有几步、几个状态、状态的正确性、每个盘子的移到情况,都了如指掌。说说该题思路:
n号塔必然是A->C,那么N-1号塔, 若n在A,则n-1 在A或B,

见图:


#include<iostream>
using namespace std;
char get[68];           //保存I号盘子在哪个塔
bool over=0; bool tf=1;  //是否结束,true_or_false是否为假
void dfs(char fl,char fr, char cur,int now)  // dfs ,上面一层(now)左边和右边的塔,已经从哪个塔“下来的”(上面一层是哪个塔)
{
    if(over)return;
    if(now==1){over=1;return;}  //出口
    int temp;
    if(fl=='A'&&fr=='B'||fl=='B'&&fr=='A')temp='C';
    else if(fl=='A'&&fr=='C'||fl=='C'&&fr=='A')temp='B';
    else temp='A';
    now--;
    if(cur==fl)   //若上一层是左边的塔
    {
        if(get[now]==fr){over=1;tf=0;return;}  //不可能是fr
        else
        {
            dfs(fl,temp,get[now],now);  
        }
    }
    else if(cur==fr)
    {
        if(get[now]==fl){over=1;tf=0;return;}
        else
        {
            dfs(temp,fr,get[now],now);
        }
    }
}
int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        int n,m,p,q,tx;
        cin>>n;
        cin>>m;
        for(int i=0;i<m;i++)
        {
            cin>>tx;get[tx]='A';
        }
        cin>>p;
        for(int i=0;i<p;i++)
        {
            cin>>tx;get[tx]='B';
        }
        cin>>q;
        for(int i=0;i<q;i++)
        {
            cin>>tx;get[tx]='C';
        }
        tf=1;
        over=0;
        if(get[n]=='B')
        {
            cout<<"false"<<endl;continue;
        }
        dfs('A','C',get[n],n);
        if(tf==1)cout<<"true"<<endl;
        else cout<<"false"<<endl;
    }
    return 0;
}



文章评论

Google伦敦新总部 犹如星级庄园
Google伦敦新总部 犹如星级庄园
2013年美国开发者薪资调查报告
2013年美国开发者薪资调查报告
“肮脏的”IT工作排行榜
“肮脏的”IT工作排行榜
程序猿的崛起——Growth Hacker
程序猿的崛起——Growth Hacker
团队中“技术大拿”并非越多越好
团队中“技术大拿”并非越多越好
 程序员的样子
程序员的样子
程序员应该关注的一些事儿
程序员应该关注的一些事儿
初级 vs 高级开发者 哪个性价比更高?
初级 vs 高级开发者 哪个性价比更高?
程序员的一天:一寸光阴一寸金
程序员的一天:一寸光阴一寸金
为啥Android手机总会越用越慢?
为啥Android手机总会越用越慢?
老美怎么看待阿里赴美上市
老美怎么看待阿里赴美上市
我的丈夫是个程序员
我的丈夫是个程序员
程序员最害怕的5件事 你中招了吗?
程序员最害怕的5件事 你中招了吗?
代码女神横空出世
代码女神横空出世
程序员的鄙视链
程序员的鄙视链
那些性感的让人尖叫的程序员
那些性感的让人尖叫的程序员
要嫁就嫁程序猿—钱多话少死的早
要嫁就嫁程序猿—钱多话少死的早
写给自己也写给你 自己到底该何去何从
写给自己也写给你 自己到底该何去何从
5款最佳正则表达式编辑调试器
5款最佳正则表达式编辑调试器
Java 与 .NET 的平台发展之争
Java 与 .NET 的平台发展之争
中美印日四国程序员比较
中美印日四国程序员比较
亲爱的项目经理,我恨你
亲爱的项目经理,我恨你
总结2014中国互联网十大段子
总结2014中国互联网十大段子
那些争议最大的编程观点
那些争议最大的编程观点
当下全球最炙手可热的八位少年创业者
当下全球最炙手可热的八位少年创业者
我是如何打败拖延症的
我是如何打败拖延症的
Java程序员必看电影
Java程序员必看电影
旅行,写作,编程
旅行,写作,编程
程序员和编码员之间的区别
程序员和编码员之间的区别
做程序猿的老婆应该注意的一些事情
做程序猿的老婆应该注意的一些事情
鲜为人知的编程真相
鲜为人知的编程真相
聊聊HTTPS和SSL/TLS协议
聊聊HTTPS和SSL/TLS协议
我跳槽是因为他们的显示器更大
我跳槽是因为他们的显示器更大
如何成为一名黑客
如何成为一名黑客
Web开发者需具备的8个好习惯
Web开发者需具备的8个好习惯
10个调试和排错的小建议
10个调试和排错的小建议
科技史上最臭名昭著的13大罪犯
科技史上最臭名昭著的13大罪犯
“懒”出效率是程序员的美德
“懒”出效率是程序员的美德
为什么程序员都是夜猫子
为什么程序员都是夜猫子
看13位CEO、创始人和高管如何提高工作效率
看13位CEO、创始人和高管如何提高工作效率
编程语言是女人
编程语言是女人
每天工作4小时的程序员
每天工作4小时的程序员
2013年中国软件开发者薪资调查报告
2013年中国软件开发者薪资调查报告
程序员都该阅读的书
程序员都该阅读的书
60个开发者不容错过的免费资源库
60个开发者不容错过的免费资源库
十大编程算法助程序员走上高手之路
十大编程算法助程序员走上高手之路
Web开发人员为什么越来越懒了?
Web开发人员为什么越来越懒了?
一个程序员的时间管理
一个程序员的时间管理
程序员周末都喜欢做什么?
程序员周末都喜欢做什么?
软件开发程序错误异常ExceptionCopyright © 2009-2015 MyException 版权所有