| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 1961 人关注过本帖
标题:[原创]汉罗塔程序可以这样写吗?
只看楼主 加入收藏
wfpb
Rank: 6Rank: 6
等 级:贵宾
威 望:29
帖 子:2188
专家分:0
注 册:2006-4-2
收藏
 问题点数:0 回复次数:18 
[原创]汉罗塔程序可以这样写吗?
以前玩过汉罗塔,现在第一次编写,也没见过算法,所以不知道是不是对的,我这编写的是一个汉罗塔演示程序,即给出层数,演示如何得到结果的过程!帮忙看下,我没编译调试,大家一起帮帮忙,看看,谢谢了
搜索更多相关主题的帖子: 罗塔 
2006-05-21 00:35
wfpb
Rank: 6Rank: 6
等 级:贵宾
威 望:29
帖 子:2188
专家分:0
注 册:2006-4-2
收藏
得分:0 

#include <iostream>
#include <windows.h>
using namespace std;

//-----------函数声明--------------
void Instruct();
void display(int row);
void OtoTw(int n,int row);
void ThtoO(int n,int row);
void ThtoTw(n,int row);
void TwtoTh(int n,int row);
void TwtoO(int n,int row);
void ThtoTw(n,int row);
void TwtoTh(int n,int row);
void TwtoO(int n,int row);
int main()
{
//定义一个字符串类型的容器
vector<string>s(10);
s[0]=" _ ";
s[1]=" ___ ";
s[2]=" _____ ";
s[3]=" _______ ";
s[4]=" _________ ";
s[5]=" ___________ ";
s[6]=" _____________ ";
s[7]=" _______________ ";
s[8]=" _________________ ";
s[9]=" ___________________ ";
string space=" ";
vector<vector<string>>sArr;
//-------------用户界面开始-----------
Instruct();
int row; //用户选择排数
char choice; //用户选择是否继续
do
{
do
{
cout<<"Input the number of HanLuoTa's row:";
cin>>row;
sArr.resize(row);
//-------------初始化汉罗塔----------
//将第3个柱子设置为全部满,第1和2为空(space定义的那样)
for(;row;row--)
{
sArr[row].resize(3);
sArr[row][0]=s[row];
sArr[row][1]=space;
sArr[row][2]=space;
}
if(row<0||row>10){cout<<"***Error***! Out of range! Input again!\n";}
}while(row<0||row>10);
/*因为是递归函数,所以首先返回的肯定是最深层的内容。这样结实够清楚了吧?*/
display(row);
OtoTh(row,row);
cout<<endl<<endl;
cout<<"Go again or exit?\n";
"Press any key without y to come again:";
cin>>choice;if(choice=='y'||choice=='Y')b=0;
}while (b);
system("pause");
return 0;
}
//游戏说明
void Instruct()
{
cout<<"This is an old game being palyed by many years \n"
"which named HanLuoTa ! \n"
"You should just inputed a number to determine how many row \n"
"the HanLuoTa have!\n";
}
void display(int row)
//-----输出汉偌塔目前情景-----
{
for(int i=0;i<row;i++)
for(int j=0;j<3;j++)
cout<<sArr[i][j];
Sleep(1000);
system("cls");
}


row->总层数 n->转移几层
void OtoTh(int n,int row)
//1->3:将第1个柱子上的盘移动n个到第3个上
{
//--------如果移动的排数递归到不是1个盘,执行下面操作---------
if(n!=1)
{
//-----先将n-1个盘从第1个柱子移到第2个柱子上(怎么实现呢?继续下面的递归)
OtoTw(n-1);
//-----再将第n个盘(最下面的盘)移动到第3个柱子上
sArr[row-1][0].swap(sArr[n][2]);//这就是一个字符串交换的过程。
//再将第2个柱子上的n-1个盘移动到第3个柱子上(怎么实现呢?继续下面的递归)
TwtoTh(n-1);
//显示现在情景
}
//--------如果移动的排数递归到只剩1个盘,执行下面操作(直接移动到目标盘上)---------
else sArr[row-1][0].swap(sArr[n][2]);
display(row);
}
void OtoTw(int n,int row)
//1->2:将第1个柱子上的盘移动n个到第2个上
{
//-----先将n-1个盘从第1个柱子移到第3个柱子上(怎么实现呢?继续下面的递归)
OtoTh(n-1);
//-----再将第n个盘(最下面的盘)移动到第2个柱子上
sArr[row-1][0].swap(sArr[n][1]);
//再将第2个柱子上的n-1个盘移动到第3个柱子上(怎么实现呢?继续下面的递归)
ThtoTw(n-1);
//显示现在情景
display(row);
}
//---------下面的跟上面的解释差不多,整体上是一个递归函数--------
void ThtoO(int n,int row)
//3->1
{
ThtoTw(n-1);
sArr[row-1][2].swap(sArr[n][0]);
TwtoO(n-1);
display(row);
}
void ThtoTw(n,int row)
//3->2
{
ThtoO(n-1);
sArr[row-1][2].swap(sArr[n][1]);
OtoTw(n-1);
display(row);
}


void TwtoTh(int n,int row)
//2->3
{
//---------解释同上-------------
if(n!=1)
{
TwtoO(n-1);
sArr[row-1][1].swap(sArr[n][2]);
OtoTh(n-1);
}
else sArr[row-1][1].swap(sArr[n][2]);
display(row);
}
void TwtoO(int n,int row) //2->1
{
TwtoTh(n-1);
sArr[row-1][1].swap(sArr[n][0]);
ThtoO(N-1);
display(row);
}

[此贴子已经被作者于2006-5-22 23:00:02编辑过]


[glow=255,red,2]wfpb的部落格[/glow] 学习成为生活的重要组成部分!
2006-05-21 00:35
kai
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:版主
威 望:52
帖 子:3450
专家分:59
注 册:2004-4-25
收藏
得分:0 
wfpb,
汉诺塔的算法其实是很简单的.
首先你必须清楚什么是汉诺塔问题.
汉诺塔的问题是这样的.
在一块板上竖立着三根柱子, 给这三根柱子做个标记,分别为 A, B, C.
最初, 所有的盘都位于A, 并且是按大小排好序的, 确切讲, 小的盘位于大的盘上面. 现在你的任务是将所有位于A 的盘 移动到 目的柱子上, 假定C为我们的目的柱子. 并且无论如何, 大盘位于小盘上都是不允许的.

那么解法是什么呢? 我不马上告诉你, 我想告诉你的是如何去寻找解法, 知道解决问题的途径比知道解法更为重要, 因为你看到了思维的过程, 而不仅仅是一个结果. 好, 那么如何去发现解法呢? 有一个很重要的方法, 那就是假设法, 然后你要实现自圆其说. 如果你的假设法能够成功, 那么我们可以说,我们找到了一个解法, 至于这个解法是不是唯一的解法,是另外一个话题.

那么关于这个问题, 什么是我们的假设呢? 其实很简单. 我们假设, 已经找到了某个解法, 到目前为止,这个所谓的假设是虚的, 也就是说, 我们并不知道这个解法, 但是没有关系. 我们清楚一个非常重要的一点, 这一点也是游戏规则所决定的, 即大盘不允许放在小盘的上面. 那么好, 如果我们要将所有的盘从A移到C, 必须将那个最大的盘从A移到C, 然后才能将其余的盘放到那个最大的盘上面. 那么这意味着什么? 这意味着, 那个最大的盘的上面的所有盘必须先移到B上面, 这样才能使得那个最大的盘有可能被移到C. 由于我们有了一个假设, 就是我们有能力将所有的盘从A移到C, 那么我们当然有能力将所有除去那个最大盘的盘移到B上面来. 好了, 也就是说, 我们进一步假设, 我们实现了, 将所有最大盘上面的所有盘先移到了B, 然后将那个位于A 最下面的那个最大的盘移到了C, 接着就是实现,将B 上面的所有盘移到C上面了。 这个问题和原问题其实是一回事, 只不过起始柱子现在为B,盘的数目也少掉一个了。那么方法和前面的是一样的。这样一直推理下去, 就逐步变成将5个盘移到目标柱子, 那么你就要先移掉最上面的4个盘,然后将最下面的盘移到目标柱子,然后问题就变成那4个盘移到目标柱子。要移4个盘,当然必须先移掉上面的3个盘,一直这样进行下去,你看一下你是否能够实现移3个盘啊。要移3个盘, 你必须看一下,你能不能移两个盘啊?问题越来越清楚了,我们的假设得到了自圆其说。也就是说,我们可以这样假设的。那么我们就找到了问题的解法了。这就是逆推理的过程。我们设法从目的地回到起点,如果我们能够从目的地回到起点,那么我们当然能够从起点走到目的地啊。

希望上面的解释够清楚了。



自由,民主,平等,博爱,进步.
中华民国,我的祖国,中华民国万岁!中华民国加油!
本人自愿加入中国国民党,为人的自由性,独立性和平等性而奋斗!
2006-05-21 04:09
kai
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:版主
威 望:52
帖 子:3450
专家分:59
注 册:2004-4-25
收藏
得分:0 
wfpb,
如果你进一步对图像化感兴趣,我建议你学习WindowsProgramming,你也可以学习Java。使用JavaSwing 你将很容易实现界面化。

自由,民主,平等,博爱,进步.
中华民国,我的祖国,中华民国万岁!中华民国加油!
本人自愿加入中国国民党,为人的自由性,独立性和平等性而奋斗!
2006-05-21 04:16
俗狼
Rank: 1
等 级:新手上路
帖 子:13
专家分:0
注 册:2006-5-9
收藏
得分:0 

我是个新手,编译通不过啊
还望大哥指导!


天行键,君子以自强不息!
2006-05-21 08:46
wfpb
Rank: 6Rank: 6
等 级:贵宾
威 望:29
帖 子:2188
专家分:0
注 册:2006-4-2
收藏
得分:0 

我现在是在学windows编程.但是我上面的思想就是你说的那样的啊


[glow=255,red,2]wfpb的部落格[/glow] 学习成为生活的重要组成部分!
2006-05-21 11:46
wfpb
Rank: 6Rank: 6
等 级:贵宾
威 望:29
帖 子:2188
专家分:0
注 册:2006-4-2
收藏
得分:0 
我首先假设游戏中有n个盘,那么从第一个柱子移动n-1个盘到第2个柱子,怎么样去完成这呢?那就必须先把n-2个盘移动到第3个柱子,当第n-1个盘被从第一个柱子移动到第2个柱子时,再把第3个柱子上的n-2个盘移动到第2个盘上去,怎么实现呢?就又象刚才这样,递归上去,直到第1和第2个柱子上累计只有一个盘时,只需要将这个盘移动到第3个柱子上就可以了,但是这样深层递归最先输出的将是最后移动到第3个柱子以后的情形,所以我就反过来写,从第三个柱子往第一个柱子上运,这样应该就可以得到答案了,但是你说的算法其实很简单?那我写的思路是复杂咯?

[glow=255,red,2]wfpb的部落格[/glow] 学习成为生活的重要组成部分!
2006-05-21 11:52
wfpb
Rank: 6Rank: 6
等 级:贵宾
威 望:29
帖 子:2188
专家分:0
注 册:2006-4-2
收藏
得分:0 
兄弟们有的进来说句话啊,不要嫌太长啊!一句话,我马上就写注释,只要你们需要

[glow=255,red,2]wfpb的部落格[/glow] 学习成为生活的重要组成部分!
2006-05-21 22:42
tree168
Rank: 1
等 级:新手上路
帖 子:14
专家分:0
注 册:2006-5-18
收藏
得分:0 

写写注释吧,看看都昏了


I believe I can fly,I can touch the sky.
2006-05-22 13:23
song4
Rank: 7Rank: 7Rank: 7
等 级:贵宾
威 望:38
帖 子:1533
专家分:4
注 册:2006-3-25
收藏
得分:0 
呵呵
我一看长代码就晕
你可以用八皇后的方法,什么前掷法?..
叫什么我又忘了

嵌入式 ARM 单片机 驱动 RT操作系统 J2ME LINUX  Symbian C C++ 数据结构 JAVA Oracle 设计模式 软件工程 JSP
2006-05-22 13:28
快速回复:[原创]汉罗塔程序可以这样写吗?
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.018110 second(s), 9 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved