poj1920 Towers of Hanoi

2024-05-28 11:18
文章标签 hanoi towers poj1920

本文主要是介绍poj1920 Towers of Hanoi,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

关于汉诺塔的递归,记住一个结论是,转移n个盘子至少需要2^n-1步


#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<string>
using namespace std;int two[100005],pos[100005];int main()
{int n,nn[5],i,j,ans,now,end,mid,a;two[0]=1;for(i=1;i<=100000;i++)two[i]=(two[i-1]*2)%1000000;while(~scanf("%d",&n)){scanf("%d%d%d",&nn[1],&nn[2],&nn[3]);for(i=1;i<=3;i++){for(j=1;j<=nn[i];j++){scanf("%d",&a);pos[a]=i;}}ans=0;end=now=pos[n];printf("%d\n",pos[n]);while(n>0){if(end!=now){ans=(ans+two[n-1])%1000000;end=mid;}n--;now=pos[n];mid=6-now-end;}printf("%d\n",ans);}return 0;
}


这篇关于poj1920 Towers of Hanoi的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1010414

相关文章

【UVA】10066-The Twin Towers(最长公共子串问题)

赤裸裸的最长公共子串问题,没什么好说的,注意的是,每组数据后面都有一个空行。 13996019 10066 The Twin Towers Accepted C++ 0.015 2014-08-06 00:34:53 #include<cstdio>#include<cstring>#include<iostream>#include<algorithm>using

汉诺塔hanoi

递归汉诺塔 这个递归的例子已经见过好多次了,但是每次遇到的时候,或多或少都出过bug,现在来总结一下,以便后面会用到 #include <iostream>using namespace std;void hanoi(int n,char here, char temp, char there){if(n == 1){cout << 1 << "从"<<here<<"到"<<there <<

uva 10066 The Twin Towers(动态规划:LCS)

水题一道 代码如下: #include <cstdio>#include <cstring>#include <algorithm>#define MAXN 110using namespace std;int a[MAXN], b[MAXN];int dp[MAXN][MAXN];int main(void) {int len1, len2, t;t = 1;while(sca

Codeforces 392B Tower of Hanoi(递归+记忆化搜索)

题目链接:Codeforces 392B Tower of Hanoi 题目大意:给出一个3*3的矩阵,表示从i移动到j的代价,现在给出n,表示有n个碟子在1柱,需要移动到3柱,要求给出最小的花费。 解题思路:dp[l][r][n],表示的是从l移动n个碟子到r的最小花费,然后总共有两种移动方式: ans1 = solve(l, x, n-1) + solve(x, r, n-1

Codeforces 479B Towers(暴力)

题目链接:Codeforces 479B Towers 题目大意:给定N和K,表示有N堆盘子,K次操作,每次可以将一堆中的顶部的盘子移动到另外一堆上。现在要使得这 N堆盘子中个数最多的减掉个数最少的值要尽量少,输出最小值和移动的步数,以及移动策略。 解题思路:数据量不大,直接枚举即可,每次将从最多的那堆移动一个到最少的那堆。 #include <cstdio>#include <

hanoi双塔

Problem Description 给定a、b、c三根足够长的细柱,在a柱上放有2n(n<=200)个中间有孔的圆盘,共有n个不同的尺寸,每个尺寸都有两个相同的圆盘,注意这两个圆盘是不加区分的。尺寸相同的圆盘在一起。 现在将这些圆盘移动到c柱上,在移动过程中可放在b柱上暂存。要求: (1) 每次只能移动一个圆盘; (2) a、b、c三根细柱上的圆盘都要保持上小下大的顺序。 请问完成

Codeforces Round #230 (Div. 2) C. Blocked Points D. Tower of Hanoi

C. Blocked Points 题意:A点和B点是4-connected,的条件是 the Euclidean distance between A and B is one unit and neither A nor B is blocked; or there is some integral point C, such that A is 4-connected with C,

【影片欣赏】【指环王】【魔戒:双塔奇谋 The Lord of the Rings: The Two Towers】

2003年发行,Special Extended DVD Edition Part One 1. The Foundations of Stone 2. Elven Rope 3. The Taming of Smeagol 4. The Uruk-hai 5. The Three Hunters 6. The Burning of the Westfold 7. Massacre a

227.Mock Hanoi Tower by Stacks-用栈模拟汉诺塔问题(容易题)

用栈模拟汉诺塔问题 题目 在经典的汉诺塔问题中,有 3 个塔和 N 个可用来堆砌成塔的不同大小的盘子。要求盘子必须按照从小到大的顺序从上往下堆 (如,任意一个盘子,其必须堆在比它大的盘子上面)。同时,你必须满足以下限制条件: (1) 每次只能移动一个盘子。 (2) 每个盘子从堆的顶部被移动后,只能置放于下一个堆中。 (3) 每个盘子只能放在比它大的盘子上面。 请写一段程序,实现将第一个堆

【2016-2017 ACM-ICPC (ECNA 2016) G】That's One Hanoi-ed Teacher(思维)

题目链接:http://codeforces.com/gym/101196   题目大意:询问当前状态是否是最优方案中的一种,若是输出剩下还需多少步   题目思路: 汉诺塔的递归函数的写法是 dfs(a,c,b) dfs(b,a,c) 分别是在a以c为辅助去b,在b以a为辅助去c 所以其实它呈现出的是一个二叉树的结构 首先根据汉诺塔的性质,最大的环要么在第一个柱子,要么在第三个