发布日期:2016-01-05 17:17 来源: 标签: 编程语言 开发语言 C++入门教程 C++汉诺塔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;
       }
   }
}

相关评论

专题信息
    Visual C++是一个功能强大的可视化软件开发工具,是高等院校计算机及相关专业主要核心课程。 本教程对Visual C++ 的应用与开发进行了详细系统的介绍,内容主要包括:Visual C++程序的建立,菜单、工具栏和状态栏的创建,对话框和常用控件,窗口、文档与视图,图形绘制,数据库应用,多媒体技术等。 本教程以案例教学为主,各章节都附有大量的实例,并且操作步骤详细,有利于引导读者更好的消化、理解和实际应用本章节所学的知识内容,希望大家能多多支持中国站长网络学院!