点击打开链接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;
}
分享到:
相关推荐
测试数据
UVA109的题解,经测试完全正确,还附有题解。
uva272
有uva刘汝佳文件夹的50道题解,从数据结构开始,以后慢慢上传
包含UVA在线OJ系统的绝大部分的示例代码,并都已AC,可在刷题时参考
UVa在我看来是比较全的一个题解,希望能帮助大家。欢迎下载。
uva最全ac代码
uva531最长公共子序列问题水题,应用简单的dp即可ac有更快速的方法欢迎讨论
uva10755 ac 代码,可以随意更改下载
uva357的栈实现版本
UVA 题目,不是很难,试试吧
《算法竞赛入门经典》UVa配套题目pdf版完整
1.Uva_base的编译 在编译球队时,则需要在当前球队文件夹下打开终端输入执行以下命令(以下命令都是在root下执行的): ./configure make clean make 如果运行Uva_base后,出现球员越界或掉线的情况,就重新...
世界著名大学UVA OJ平台上的题目部分分类,分的不好请原谅。
这是一支完整的uva球队,包含所有基本模块,初者可在上修改得到自己的球队
uva_trilearn2002 源代码
主要是uvaoj习题相关题目 练习题目
这里面全部为在Uva Online Judge上面的部分题目的解答,里面提供了解答使用的源代码。
PDF试题
开源项目-codingsince1985-UVa.zip,Been solving UVa Online Judge Problems in Golang for one year (and counting)