大白_uva10795_新汉诺塔-白红宇

大白_uva10795_新汉诺塔

阅读量：6096 次

发布时间：2019-06-20

本文共 1052 字，大约阅读时间需要 3 分钟。

题意：给出所有盘子的初态和终态，问最少多少步能从初态走到终态，其余规则和老汉诺塔一样。

思路：

若要把当前最大的盘子m从1移动到3，那么首先必须把剩下的所有盘子1~m-1放到2上，然后把m放到3上。

现在要解决怎样将一个状态s0转移到s（1~k全部放到一个盘子c上面），要放k，那么必须先有一个相似的状态s0,：1~k-1放到一个盘子，然后转移k，然后将1~k-1再放到k上面（原始的汉若塔问题，步数为2^(1<<(k-1)) ），可以看出解决s0和解决s是一个问题，这就得到了状态转移方程了，可以递归了。

由老汉诺塔的公式，将n个在一个柱子上排列好的盘子移动到另一个柱子需要2^n步。

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          using namespace std;#define N 65int st[N];int en[N];long long solve(int *p,int x,int epos){ if(x==0) return 0; if(p[x]==epos) return solve(p,x-1,epos); return solve(p,x-1,6-epos-p[x])+(1LL<<(x-1));}int main(){ int n,cnt=0; while(scanf("%d",&n)!=EOF&&n) { for(int i=1; i<=n; i++) scanf("%d",&st[i]); for(int i=1; i<=n; i++) scanf("%d",&en[i]); int k=n; while(st[k]==en[k]) k--; long long res=0; if(k>0) { int other=6-st[k]-en[k]; res=solve(st,k-1,other)+solve(en,k-1,other)+1; } printf("Case %d: %lld\n",++cnt,res); } return 0;}

转载于:https://www.cnblogs.com/jasonlixuetao/p/5982982.html

你可能感兴趣的文章