汉诺塔递归太难理解了_函数定义时可以用递归吗

汉诺塔递归太难理解了_函数定义时可以用递归吗记得我第一次做汉诺塔这道题时,是2017年11月。当时,我坐在山大青岛校区图书馆3楼,不知怎么地,看到了这个题。然后,就思考了一整天,233当然,悲剧就是,我当时花了一天的时间还是没有真正理解这道题递归的思路。如今,我终于懂了,嘿嘿嘿。关于递归:一定不要试图跟踪大型递归的过程!要写出递归,关键就是找出递归的递归方程式:也就是说,要完成最后一步,那么最后一步的前一步要做什…

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

Jetbrains全家桶1年46,售后保障稳定

记得我第一次做汉诺塔这道题时,是2017年11月。当时,我坐在山大青岛校区图书馆3楼,不知怎么地,看到了这个题。

然后,就思考了一整天,233

当然,悲剧就是,我当时花了一天的时间还是没有真正理解这道题递归的思路。

如今,我终于懂了,嘿嘿嘿。

 

关于递归: 一定不要试图跟踪大型递归的过程! 要写出递归,关键就是找出递归的递归方程式: 也就是说,要完成最后一步,那么最后一步的前一步要做什么。

 

关于递归:

(1)在求f(n, other variables)的时候,你就默认f(n -1, other variables)已经被求出来了——至于怎么求的,这个是计算机通过回溯求出来的。

PS:这里用到了一种叫做栈(stack)的先进后出的数据结构,所以递归输出的答案一般是自下而上的。

(2)递归和二叉树是密切相关的。可以尝试通过二叉树的数据结构来理解递归是如何将一个问题拆分成若干子问题,求解再回溯的。这里可以参考以下快速排序(QuickSort)的过程(快速排序的核心思想是分治,分治即分而治之,通过递归将原问题分解为若干容易求解的子问题,再通过递归将这些子问题联系起来并向二叉树的上层回溯,最终求解出原问题)

 

 

递归的关键有两个:

(1)递归的结束条件(不写会死循环,TLE)

(2)递归最后一层和其他有关系的层的关系怎样用非递归函数来表达

比如:斐波纳契亚数列,(1)当n==1和n==2的时候f(n)=1,这就是递归的终止条件。给了终止条件,计算机才能进行求解子问题并回溯,最终求出f(n)

 

对于这个汉诺塔问题,在写递归时,我们只需要确定两个条件:

1.递归何时结束?

2.递归的核心公式是什么?即:

怎样将n个盘子全部移动到C柱上?

即:若使n个盘子全部移动到C柱上,上一步应该做什么?

 

下面正式进入该题:

汉诺塔问题是一个经典的问题。汉诺塔(Hanoi Tower),又称河内塔,源于印度一个古老传说。大梵天创造世界的时候做了三根金刚石柱子,在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定,任何时候,在小圆盘上都不能放大圆盘,且在三根柱子之间一次只能移动一个圆盘。问应该如何操作?

 

下面我们来写递归函数。

首先,题目要求求的是如何操作,那么我们就必须写一个输出操作语句的函数。

这个操作语句必须说明:第几步将哪个盘子从哪个柱子移动到哪个柱子上(这样人类才知道怎样移动盘子嘛)

这里,我们定义这个函数的函数名为move。

接下来,我们来确定这个函数的参数列表。

显然,为了说明第几步将哪个盘子从哪个柱子移动到哪个柱子上,我们参数列表至少应该包含:

id,表示被移动的盘子的序号。

from,表示从哪个柱子上移动这个编号为id的盘子

to,表示移动到哪个柱子上

那么这个函数的函数头就确定了:

void move(int id, char from, char to) // 打印移动方式:编号,从哪个盘子移动到哪个盘子

 

那么函数体呢?

唯一的难点就是如何记录这是操作的第几步。

注意到,每次操作必须输出移动方式且仅能输出一次,那么显然,我们已经printf的当前总数不就是第几次操作了嘛

我们开一个全局变量用于记录printf的次数即可

所以函数体中就只有这一个语句:

printf ("step %d: move %d from %c->%c\n", ++cnt, id, from, to);

Jetbrains全家桶1年46,售后保障稳定

合并起来就是:

void move(int id, char from, char to) // 打印移动方式:编号,从哪个盘子移动到哪个盘子
{
    printf ("step %d: move %d from %c->%c\n", ++cnt, id, from, to);
}

 

敲黑板:

递归函数怎么写呢?

我们先来想一下我们人类应该怎样操作吧。

我们每次操作都会这样问自己:我们需要将哪个柱子上的多少个盘子通过哪个柱子移动到哪个柱子上呢?

我们必须也只能用这么几个参数:

需要移动的盘子的总数,3个柱子。

所以函数头为:

void hanoi(int n, char x, char y, char z)

其中,n代表盘子总数,x,y,z代表柱子

hanoi(n, x, y, z)的意思就是:将n个在x柱子上的盘子通过y这个柱子移动到z这个柱子上。

那不就完了!

hanoi(n, ‘A’, ‘B’, ‘C’)就是这道问题的答案!

 

那么这一步的前一步是什么?

记住了,在求解f(n, other variables)的时候,我们直接默认f(n – 1, other variables)已经完了就可以了!这个在前面已经解释过了,在此不再鳌述。

我们将n-1个盘子当作一个整体:这就是类似于分治求解子问题的思想

那么,前一步也就是f(n – 1, other variables)显然是先将n -1 个在A柱子上的盘子通过C柱移动到B柱上,再将在A柱子上的编号为n的盘子移动到C柱上,再将B柱子上的n-1个盘子通过A柱移动到C柱上,over

 

C++代码如下:

void hanoi(int n, char x, char y, char z)
{
    if (n == 0)
        return;
    hanoi(n - 1, x, z, y);
    move(n, x, z);
    hanoi(n - 1, y, x, z);
}

汉诺塔完整代码:

#include <iostream>
#include <cstdio>
using namespace std;

int cnt;

void move(int id, char from, char to) // 打印移动方式:编号,从哪个盘子移动到哪个盘子
{
    printf ("step %d: move %d from %c->%c\n", ++cnt, id, from, to);
}

void hanoi(int n, char x, char y, char z)
{
    if (n == 0)
        return;
    hanoi(n - 1, x, z, y);
    move(n, x, z);
    hanoi(n - 1, y, x, z);
}

int main()
{
    int n;
    cnt = 0;
    scanf ("%d", &n);
    hanoi(n, 'A', 'B', 'C');
    return 0;
}

 

用户友好版:

#include <iostream>
#include <cstdio>
using namespace std;

int cnt;

void move(int id, char from, char to) // 打印移动方式:编号,从哪个盘子移动到哪个盘子
{
    ++cnt; // 记录走过的步数
    printf ("step %d: move %d from %c->%c\n", cnt, id, from, to);
}

void hanoi(int n, char x, char y, char z)
{
    if (n == 0)
        return;
    hanoi(n - 1, x, z, y);
    move(n, x, z);
    hanoi(n - 1, y, x, z);
}

int main()
{
    int n;
    printf("Please enter the number of the plates:");
    while (~scanf ("%d", &n) && n)
    {
        cnt = 0;
        printf ("The following are the steps for the question\n");
        hanoi(n, '1', '2', '3');
        printf ("There are %d steps in all.\nYou have solved the hanoi problems, congratulations!\n", cnt);
        printf ("Would you like to continue?(y/n)");
        char ch; scanf (" %c", &ch);
        if (ch == 'y' || ch == 'Y')
            printf("Please enter the number of the plates:\n");
        else
        {
            printf ("Here comes the end of the program. Bye\n");
            break;
        }
    }
    return 0;
}

 

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

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

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

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

(0)


相关推荐

  • 【QGIS入门实战精品教程】2.1:初识QGIS软件[通俗易懂]

    【QGIS入门实战精品教程】2.1:初识QGIS软件[通俗易懂]从今天开始,我们一起来学习一款免费开源、对机器要求低、功能强大的GIS软件:QGIS!一、QGIS简介QGIS(原称QuantumGIS)是一个自由软件的桌面GIS软件。它提供数据的显示、编辑和分析功能。QGIS是一个用户界面友好的桌面地理信息系统,可运行在Linux、Unix、MacOSX和Windows等平台之上。QGIS是基于Qt,使用C++开发的一个用户界面友好、跨平台的免费开源版桌面地理信息系统。二、QGIS软件的主要特点支持多种GIS数据文件格式。通过GDAL..

  • 贴片电阻的阻值编码表_贴片电阻怎么看阻值

    贴片电阻的阻值编码表_贴片电阻怎么看阻值

  • ubuntu系统下mysql重置密码和修改密码操作

    ubuntu系统下mysql重置密码和修改密码操作一、忘记密码后想重置密码在介绍修改密码之前,先介绍一个文件/etc/mysql/debian.cnf.其主要内容如下图:里面有一个debian-sys-maint用户,这个用户只有Debian或Ubuntu服务器才有,所以如果您的服务器是Debain或Ubuntu,debian-sys-maint是个Mysql安装之后自带的用户,具体作用是重启及运行mysql服务。所以如果忘了root密码,可以通…

  • 服务器做矿机使用_文件服务器搭建

    服务器做矿机使用_文件服务器搭建云服务器搭建矿机内容精选换一换在专属主机资源上创建云服务器失败,可能由以下原因造成:您所选择的云服务器规格不在您已有的专属主机支持范围内。各类型专属主机支持的云服务器规格请参见概述。各类型专属主机支持的云服务器规格请参见概述。您的专属主机资源不足,无法创建您所选择的云服务器规格。您可以查看专属主机的剩余vCPU和内存数量是否满足您所选择的云服务器规格。如果资源不足,您弹性云服务器(Elastic…

  • 常用资源网站

    常用资源网站排名不分先后(1)https://www.codeproject.com/(2)http://www.codeguru.com/(3)https://www.cnblogs.com

    2021年12月18日
  • Centos7磁盘阵列部署与修复「建议收藏」

    Centos7磁盘阵列部署与修复「建议收藏」Centos7磁盘阵列部署与修复一、部署RAID10#1、虚拟机添加4块20G的硬盘设备#2、mdadm命令,其中-n4代表使用4块磁盘,-l10代表使用RAID10技术mdadm-Cv/dev/md0-ayes-n4-l10/dev/sdb/dev/sdc/dev/sdd/dev/sde#3、制作好的RAID磁盘阵列格式化为ext4mkfs.ext4/dev/md0#4、创建挂载点,进行磁盘设备挂载mkdir/RAIDmount/dev/md0/RA

发表回复

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

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