| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 2251 人关注过本帖
标题:汉诺塔实现(非递归)
只看楼主 加入收藏
yangfrancis
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:贵宾
威 望:141
帖 子:1510
专家分:7661
注 册:2014-5-19
结帖率:100%
收藏
 问题点数:0 回复次数:0 
汉诺塔实现(非递归)
教材上对汉诺塔的问题的编程手段大都以递归方式实现,代码通常比较简洁,一目了然。其实不用递归也有不用的优势。很多递归程序在改为迭代或stack之后,代码加长了,但空间复杂度也有一定程度的降低——至少递归调用需要在内存中开辟的函数指针省下来了。
思考过一段时间,发现汉诺塔的递归版经过改写,也可以用栈解决。还是那个特点,代码长一些,空间开支小一些。(没有实际测试,但感觉应该小一些)

#include<iostream>
#include<stack>
using namespace std;
struct status
{
    char from;//来源
    char idle;//中转站
    char to;//去向
    int num;//当前要移动的个数
};
void Move(char a,char b,char c,int n)//b为中转站,从a移动n个盘子到c
{
    stack<status> s;
    status pre,mid,rear;
    status current={a,b,c,n};
    s.push(current);
    while(!s.empty())
    {
        current=s.top();s.pop();
        if(current.num==1)
            cout<<"从"<<current.from<<"柱移一个到"<<current.to<<"柱。\n";
        else/*将弹出的元素分解为三个元素*/
        {
            /*对pre赋值*/
            pre.from=current.from;
            pre.idle=current.to;
            pre.to=current.idle;
            pre.num=current.num-1;
            /*对mid赋值*/
            mid.from=current.from;
            mid.idle=current.idle;
            mid.to=current.to;
            mid.num=1;
            /*对rear赋值*/
            rear.from=current.idle;
            rear.idle=current.from;
            rear.to=current.to;
            rear.num=current.num-1;
            /*入栈*/
            s.push(rear);s.push(mid);s.push(pre);
        }
    }
}
int main()
{
    Move('A','B','C',8);
    return 0;
}
搜索更多相关主题的帖子: include status 中转站 空间 
2017-04-17 10:32
快速回复:汉诺塔实现(非递归)
数据加载中...
 
   



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

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