uva 10795 A Different Task

点击打开链接uva 10795

思路：递归
分析：(转载网友，写的不错)

点击打开链接
1  新汉诺塔：标准的汉诺塔上有n个大小各异的盘子。给定一个初始局面，求它到给定目标局面至少需要多少步
2  旧汉诺塔：将A柱子上的n个盘子，移到B柱子上
3  旧汉诺塔 f(n)=f(n-1)+1+f(n-1)=(2^n)-1;f(1)=1;
    首先需要把编号最大的盘子N移到目标柱子上，于是需要有这样的局面：假设N需要从A移到B，A只有N，B是空的，C上面是N-1到1，因此需要将N-1移到C，然后将N移到B，最后将N-1移到B。因此f(n)=2*f(n-1)+1;
4 新汉诺塔问题：首先找最大不在目标柱子上的盘子K，因为如果最大的盘子在目标柱子上它不需要移动，也不碍事。
   因此问题就成了把K移动到目标柱子，把1到(k-1)移动到中转柱子，所以假设K从A移动到B，A只有K，B是空的，C上面是K-1到1，把这个局面称为参考局面。因为移动是对称的，所以从参考局面移到目标局面与目标局面移到参考局面是一样的步数。
   所以问题变成答案=从初始局面移到参考局面步数+目标局面移到参考局面步数+1；
5 需要写一个函数f(P,i,final),表示已知个盘子的初始柱面编号数组为P，把1到i移动到final的步数，本题答案是f(start,k-1,6-start[k]-finish[k])+f(finish,k-1,6-start[k]-finish[k])+1;
6 计算f(P,i,final),若p[i]=final，则f(P,i,final)=f(P,i-1,final);
   否则需要把前i-1个盘子挪到中转盘去，将盘子i移到柱子final去，做后把前i-1个盘子从中转盘移到柱子final.。
   最后一步是把i-1个盘子从一个柱子移到另一个柱子，根据旧汉诺塔问题，这个步骤需要2^(i-1)-1步，加上移动盘子i那一步，一共需要2^(i-1)步。f(P,i,final)=f(P,i-1,6-p[i]-final)+2^(i-1);

代码：

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

typedef long long ll;
const int maxn = 65;
int start[maxn] , final[maxn];
int n;

ll getAns(int *p , int i , int other){
   if(i == 0)//如果没有盘子可以移动那么直接返回
     return 0;
   if(p[i] == other)//如果当前的这个编号最大的盘子刚好在最后的柱子上则不用管
     return getAns(p , i-1 , other);
   return getAns(p , i-1 , 6-p[i]-other) + ((ll)1<<(i-1));//这里1的类型要为long long
}

int main(){
    int Case = 1;
    ll ans;
    while(scanf("%d" , &n) && n){
        for(int i = 1 ; i <= n ; i++)   
            scanf("%d" , &start[i]);
        for(int i = 1 ; i <= n ; i++)   
            scanf("%d" , &final[i]);
        int k = n;
        //找到编号最大的且在开始和结束在不同柱子的盘子
        while(k >= 1 && start[k] == final[k])
            k--;
        ans = 0;
        if(k){
          int other = 6-start[k]-final[k];//找到中转的柱子的编号
          ans = getAns(start , k-1 , other) + getAns(final , k-1 , other) + 1; 
        }
        printf("Case %d: %lld\n" , Case++ , ans); 
    }

    return 0;
}