首页 > ACM题库 > HDU-杭电 > hdu 1997 汉诺塔VII-递归和分治-[解题报告]C++
2013
12-26

hdu 1997 汉诺塔VII-递归和分治-[解题报告]C++

汉诺塔VII

问题描述 :

n个盘子的汉诺塔问题的最少移动次数是2^n-1,即在移动过程中会产生2^n个系列。由于发生错移产生的系列就增加了,这种错误是放错了柱子,并不会把大盘放到小盘上,即各柱子从下往上的大小仍保持如下关系 :
n=m+p+q
a1>a2>…>am
b1>b2>…>bp
c1>c2>…>cq
ai是A柱上的盘的盘号系列,bi是B柱上的盘的盘号系列, ci是C柱上的盘的盘号系列,最初目标是将A柱上的n个盘子移到C盘. 给出1个系列,判断它是否是在正确的移动中产生的系列.
例1:n=3
3
2
1
是正确的
例2:n=3
3
1
2
是不正确的。
注:对于例2如果目标是将A柱上的n个盘子移到B盘. 则是正确的.

输入:

包含多组数据,首先输入T,表示有T组数据.每组数据4行,第1行N是盘子的数目N<=64.
后3行如下
m a1 a2 …am
p b1 b2 …bp
q c1 c2 …cq
N=m+p+q,0<=m<=N,0<=p<=N,0<=q<=N,

输出:

包含多组数据,首先输入T,表示有T组数据.每组数据4行,第1行N是盘子的数目N<=64.
后3行如下
m a1 a2 …am
p b1 b2 …bp
q c1 c2 …cq
N=m+p+q,0<=m<=N,0<=p<=N,0<=q<=N,

样例输入:

6
3
1 3
1 2
1 1
3
1 3
1 1
1 2
6
3 6 5 4
1 1
2 3 2
6
3 6 5 4
2 3 2
1 1
3
1 3
1 2
1 1
20
2 20 17
2 19 18
16 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1

样例输出:

true
false
false
false
true
true

题目大意:这一个是汉诺塔问题的另一个版本。之前的一个版本关注的是"将n个盘子从a移到c所需要的步数"。而现在的这个版本可以概括的描述为"判断将n跟盘子从a移到c的过程中所产生的移动序列是否正确"…其输入的样例中各个数据的含义如下:

测试用例数

盘子数

柱子a中的盘子数                 盘子的编号

。。b。。。。。。。。。

。。c。。。。。。。。。

解题思路:

1)若把n个盘子从柱子a通过柱子b移到柱子c,则先把n-1个盘子从柱子a移动柱子b,再把第n个盘子从a移道c,再把n-1个盘子从b移到a。

所以当判断序列是否符合把n个盘子从a移到c时,第n个只能出现在柱子a的最底部,或柱子c的最底部,否则这个序列错的。

当第n个盘子在a的最底部时,则继续判断剩下的序列是否把n-1个盘子从a移到b。

当第n个盘子在c的最底部时,则继续判断剩下的序列是否把n-1个盘子从b移到c。

2)

现在我们有n个盘子,然后我们想把这些盘子从A上面移到C盘上去,那么第n个盘子应该是最后一次的移动,所以第n个盘子只可能出现在A和C盘上,OK。。那么如果现在你知道了第n个盘子在哪里,能不能确定n-1个盘子不能出现在哪个盘子。

3)

对一个含有n个盘子,从A柱移动到C柱借助B柱的汉诺塔,第n个盘子移动到C柱过程是这样子的:首先将其余的n-1个盘子移动到B柱,然后第n个盘子直接移动到C柱。在这过程中,第n个盘子只出现在A柱和C柱两个柱子上,也即第n个盘子不可能出现在B柱上。因此对于当前移动的盘子,只需检查其所在的柱子是否符合这个要求,如果出现在B柱上,则显然进入了错误移动中。这是本题求解思想精髓所在。汉诺塔是个递归求解过程,假设第n个盘子符合要求,则判别的下一个目标是第n-1个盘子。若第n个盘子在A柱上,此时剩余n-1个盘子必由A柱移动到B柱,经由C柱。此时对第n-1个盘子,C柱就是其不可能出现的位置;若第n个盘子在C住上,这剩余n-1个盘子则是在B柱上,经由A柱,移动到C柱上,因此,A柱就是第n-1个盘子不可能出现的位置。

根据汉诺塔递归求解的过程,对每个移动的盘子,可以用递归求解的方式判断

认真看完以上的解题思路(尽管有些重复),再结合以下的代码理解,应该就能做出来了。。。。

代码如下:

/*
 * 1997_2.cpp
 *
 *  Created on: 2013年8月11日
 *      Author: Administrator
 */

#include <iostream>

using namespace std;

const int maxlen = 70;

bool hanoi(int n , int start[],int end[],int zhongjian[]){
	if(zhongjian[0] == n){
		return 0;
	}else if(start[0] == n){
		return hanoi(n-1,start+1,zhongjian,end);
	}else if(end[0] == n){
		return hanoi(n-1,zhongjian,end+1,start);
	}

	return 1;


}


int main(){

	int t,a[maxlen],b[maxlen],c[maxlen];
	scanf("%d",&t);
	while(t--){
		int n,m,p,q;
		scanf("%d",&n);
		int i;
		scanf("%d",&m);
		for(i = 0 ; i < m ; ++i){
			scanf("%d",&a[i]);
		}

		scanf("%d",&p);
		for(i = 0 ; i < p ; ++i){
			scanf("%d",&b[i]);
		}

		scanf("%d",&q);
		for(i = 0 ; i < q ; ++i){
			scanf("%d",&c[i]);
		}
		a[m]=b[p]=c[q] = -1;



		if(hanoi(n,a,c,b)){
			cout<<"true"<<endl;
		}else{
			cout<<"false"<<endl;
		}


	}
}

解题转自:http://blog.csdn.net/hjd_love_zzt/article/details/9897281


  1. 可以根据二叉排序树的定义进行严格的排序树创建和后序遍历操作。如果形成的排序树相同,其树的前、中、后序遍历是相同的,但在此处不能使用中序遍历,因为,中序遍历的结果就是排序的结果。经在九度测试,运行时间90ms,比楼主的要快。

  2. 我没看懂题目
    2
    5 6 -1 5 4 -7
    7 0 6 -1 1 -6 7 -5
    我觉得第一个应该是5 6 -1 5 4 输出是19 5 4
    第二个是7 0 6 -1 1 -6 7输出是14 7 7
    不知道题目例子是怎么得出来的