汉罗塔c++递归_栈与递归的区别

汉罗塔c++递归_栈与递归的区别汉罗塔问题是一个非常经典的算法,我们首先来研究一下修改的汉罗塔(简化步骤),在后面我们将来讲述经典的汉罗塔问题。题目:修改后的汉罗塔的规则:现在限制不能从最左侧的塔直接移动到最右侧,必需要经过中间;同时从最右侧移动到最左测试,同样必需经过中间;要求移动N层塔时,打印最优移动1、用递归函数实现(从最左移动到最右)分析:-当只有一层塔时,我们先需要将其从左移到中间,再从中间移动到右边,共分为

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE稳定放心使用

汉罗塔问题是一个非常经典的算法,我们首先来研究一下修改的汉罗塔(简化步骤),在后面我们将来讲述经典的汉罗塔问题。

题目:
修改后的汉罗塔的规则:现在限制不能从最左侧的塔直接移动到最右侧,必需要经过中间;同时从最右侧移动到最左测试,同样必需经过中间;要求移动N层塔时,打印最优移动

1、用递归函数实现(从最左移动到最右)

分析:
– 当只有一层塔时,我们先需要将其从左移到中间,再从中间移动到右边,共分为两步;如果它就在中间,那么我们只需要将它移动到左或则右,一步就行;
– 当我们有N 层塔时,我们需要先将1~N-1层塔移动到右边,然后移动第N层塔到中间,再将1~N-1层塔移动到最左边,将N层塔由中间移动右边;这样,第N层塔就移好了
– 接下来重复上述步骤,将1~N-2层塔移到最右边,将第N-1层塔移到最中间……(利用递归函数实现)

代码实现:

void  _HanoiProblem1(int num,string from,string to,int& count)//num代表塔的层数,from代表开始移动的位置(left,mid,right),to 代表要移动到的位置
{
    if(num == 1)//我们只有一层塔
    {
        if(from.compare("mid")==0 || to.compare("mid")==0)//此时只需直接移动
        {
            count++;
            cout<<"move "<<num<<" from "<<from.c_str()<<" to "<<to.c_str()<<endl;
        }
        else
        {
            cout<<"move "<<num<<" from "<<from.c_str()<<" to "<<"mid"<<endl;
            count++;
            cout<<"move "<<num<<" from "<<"mid"<<" to "<<to.c_str()<<endl;
            count++;
        }
    }
    else//我们有多层塔
    {
        if(from.compare("mid")==0 || to.compare("mid")==0)
        {
            string another;
            if(from.compare("left")==0)
                another = "right";
            else
                another = "left";

            _HanoiProblem1(num-1,from,another,count);//例如从左移到中间,先将1~N-1层塔移动到右边,
            cout<<"move "<<num<<" from "<<from.c_str()<<" to "<<to.c_str()<<endl;//再将第N层塔移到中间
            count++;
            _HanoiProblem1(num-1,another,to,count);//再将1~N-1层塔移到中间

        }
        else//从左移到右或从右移到左
        {
            _HanoiProblem1(num-1,from,to,count);//例如从左移到右,先将1~N-1层塔从左移动到右边,
            cout<<"move "<<num<<" from "<<from.c_str()<<" to "<<"mid"<<endl;//再将第N层塔移到中间
            count++;
            _HanoiProblem1(num-1,to,from,count);//再将1~N-1层塔从右移动到左边
            cout<<"move "<<num<<" from "<<"mid"<<" to "<<to.c_str()<<endl;//再将第N层塔从中间移到右边
            count++;
            _HanoiProblem1(num-1,from,to,count);//再将1~N-1层塔从左移动到右边
        }
    }
}
void HanoiProblem1(int num,string from,string to)
{
    int count = 0;
    _HanoiProblem1(num,from,to,count);
    cout<<"count is: "<<count<<endl;
}

测试代码:

void funtest()
{
    HanoiProblem1(2,"left","right");
}

int main()
{
    funtest();
    getchar();
    return 0;
}

结果图
这里写图片描述

2.用栈模拟实现

分析:
我们上面用递归实现,我们已经知道了基本的走法,接下来我们用栈来模拟汉罗塔问题,将塔的移动转换为入栈和出栈的操作,但是,由题我们知道了参数入栈和出栈的两个基本规则

  • 小压大问题,即只有当要入栈的参数小于栈顶元素,这时我们才能入栈
  • 动作不想临,题目要求我们实现最优移动,所以我们从左移动到中间,下一步将它从中间右移动到左边,是没有意义的

满足了以上两条规则,我们现在看移动的过程,一个塔a,只有四中可能的动作,从左到中,从中到右,从右到中,从中到左,但是要满足以上两种规则我们发现它只有一种动作可以走;例如:a在最左边,第一次,它只能从左到中间,第二次,由规则知,从左到中间不行,从中间到左没有意义,那么只剩下从中间到右和从右到中间,我们只需判断就能得到结果。

代码实现:

enum action
{
    No,
    LToM,
    MToL,
    RToM,
    MToR,
};

int fStackToStack(action& record,action preAction,action nowAction,stack<int>& fstack,stack<int>& tstack,string from,string to)
{
    if(record != preAction && fstack.top() < tstack.top())//满足两条准则,动作不可逆和小压大原则
    {
        int data = fstack.top();
        fstack.pop();
        tstack.push(data);
        cout<<"move "<<data<<" from "<<from.c_str()<<" to "<<to.c_str()<<endl;
        record = nowAction;
        return 1;
    }
    return 0;
}

int HanoiProblem2(int num,string left,string mid,string right)
{
    stack<int> ls;
    stack<int> ms;
    stack<int> rs;

    ls.push(INT_MAX);
    ms.push(INT_MAX);
    rs.push(INT_MAX);

    for(int idx=num; idx>0; --idx)
        ls.push(idx);

    action record = No;//记录上一步的动作
    int count = 0;

    while(rs.size() != num+1)
    {
        count += fStackToStack(record,MToL,LToM,ls,ms,left,mid);
        count += fStackToStack(record,LToM,MToL,ms,ls,mid,left);
        count += fStackToStack(record,MToR,RToM,rs,ms,right,mid);
        count += fStackToStack(record,RToM,MToR,ms,rs,mid,right);
    }
    return count;
}

测试代码:

void funtest()
{
    int ret = HanoiProblem2(2,"left","mid","right");
    cout<<ret<<endl;
}

int main()
{
    funtest();
    getchar();
    return 0;
}

结果图:
这里写图片描述

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/183281.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)
blank

相关推荐

  • Struts2知识点小结(三)–值栈与ognl表达式

    Struts2知识点小结(三)–值栈与ognl表达式Struts2知识点小结(三)–值栈与ognl表达式

  • Laravel引入第三方库的方法

    Laravel引入第三方库的方法

    2021年10月25日
  • 使用强类型的Include显式预加载

    使用强类型的Include显式预加载

  • vb学习什么[通俗易懂]

    vb学习什么[通俗易懂]学习几天的vb总结一下实在学习什么,我们看到的vb程序设计这本书中,第一句话就介绍了vb是什么,它是一门面向对象的可视化程序设计语言,而我们用的一个vb6.0其实是一个已经打包的平台,而在这门语言中提到了面向对象,那面向对象是什么,它就是书中提到的三要素:属性、事件、方法。属性是指对象的特征,描述对象的数据,在生活中可以理解为你看到一个人或者一个事物给你的外在表象,不同的事物具有…

  • 再来利用java学学javaweb——–html+css+ JavaScript[通俗易懂]

    再来利用java学学javaweb——–html+css+ JavaScript[通俗易懂]今日内容1.web概念概述2.HTMLweb概念概述*JavaWeb: *使用Java语言开发基于互联网的项目*软件架构: 1.C/S:Client/Server客户端/服务器端 *在用户本地有一个客户端程序,在远程有一个服务器端程序 *如:QQ,迅雷… *优点: 1.用户体验好 *缺点: 1.开发、安装,部署,维护麻烦 2.B/S:Browser/Server浏览器/服务器端 *只需要一个浏览器,用户通过不同的网

  • 女生做java开发最多做几年,附赠复习资料

    女生做java开发最多做几年,附赠复习资料前言疫情过去,真正的春暖花开又回来了,时不时的可以和朋友约个饭,感慨今年的工作竞争压力很大,工作很不好找。作为一个开发人员,你是否面上了理想的公司,拿到了理想中的薪资?作为程序员,跳槽就是最好的涨薪方式。前提当然是你有足够实力,而不是只会纸上谈兵。面试准备不充分,就是浪费时间,更是对自己不负责任。今天给大家分享一份由粉丝投稿,我精心整理出来的一份1200页Java架构面试专题(文末见面试答案),绝大部分都是一线大厂的面试真题,可以根据这份面试专题查漏补缺,希望能够帮助你尽快找到工作!kafka面试基

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号