递归入门

递归入门

一:什么是递归

所谓递归,简单点来说,就是一个函数直接或间接调用自身的一种方法,它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解。

我们可以把” 递归 “比喻成 “查字典 “,当你查一个词,发现这个词的解释中某个词仍然不懂,于是你开始查这第二个词。

可惜,第二个词里仍然有不懂的词,于是查第三个词,这样查下去,直到有一个词的解释是你完全能看懂的,那么递归走到了尽头,然后你开始后退,逐个明白之前查过的每一个词,最终,你明白了最开始那个词的意思。(摘自知乎的一个回答)

我们以阶乘作为:

int Factorial(int n){    

      if (n == 0)  return 1;  

      return

      n * Factorial(n - 1);

}

汉诺塔 – 问题起源

法国数学家爱德华·卢卡斯曾编写过一个印度的古老传说:在世界中心贝拿勒斯(在印度北部)的圣庙里,一块黄铜板上插着三根宝石针。印度教的主神梵天在创造世界的时候,在其中一根针上从下到上地穿好了由大到小的64片金片,这就是所谓的汉诺塔。不论白天黑夜,总有一个僧侣在按照下面的法则移动这些金片:一次只移动一片,不管在哪根针上,小片必须在大片上面。僧侣们预言,当所有的金片都从梵天穿好的那根针上移到另外一根针上时,世界就将在一声霹雳中消灭,而梵塔、庙宇和众生也都将同归于尽。

汉诺塔游戏
后来,这个传说就演变为汉诺塔游戏:
1.有三根杆子A,B,C。A杆上有若干碟子
2.每次移动一块碟子,小的只能叠在大的上面
3.把所有碟子从A杆全部移到C杆上

解决思路

A柱子有7块盘子时,可借助B将A柱子的盘子全部移至C柱子,由小到大从上往下摆放

游戏的起始状态,A柱子7块盘子,移至C柱子:

要实现游戏,需将A柱子红色盘子上面的6块借助C移至B柱子,盘子由小到大从上往下摆放,在将最大的红色盘子由A柱子移至C柱子,此时A柱子没有盘子,这个时候是游戏的一个临界状态,最大的红色盘子有序的摆放在C柱子(现在可以不管红色盘子了,因为最大的如果你把它放那不动,则可以无视它的,其他盘子可以在三个柱子上移来移去.它是最大嘛),接着需要将B柱子的6块盘子借助A移动到C柱子,即可完成汉诺塔游戏了。这个过程中,7块盘子的汉诺塔游戏可演变为2个6块盘子的汉诺塔游戏了,2个6块盘子的汉诺塔游戏了演变成4个5块盘子的汉诺塔游戏了……,递归的出口就是只有一块盘子的时候了,直接移动盘子,这就是经典递归思想了

游戏的临界状态,B柱子6块盘子,移动至C柱子

实现的过程:return 有时可以省去,就是不断的调用
函数
#include<stdio.h>

void doTowers(int n,char X,char Y,char Z){
    if(n == 1)
        printf("Dish 1 from %c to %c \n",X,Z);
    else{
        doTowers(n-1,X,Z,Y);   //先将n-1个盘子借助Z从X挪到Y,为了方便将最下面的盘子直接挪到目的针
        printf("Dish %d from %c to %c \n",n,X,Z);   //把最下面的盘子直接从源挪到目的
        doTowers(n-1,Y,X,Z);  //把移到Y针上的n-1个盘子再挪到最终目的针Z上
    }
}
int main(){
    int n;
    printf("Enter the count of dishes: \n");
    scanf("%d",&n);
    printf("The answer is :\n");
    doTowers(n,'X','Y','Z');         //参数分别为:盘子数、源、中介、目标
}

汉诺塔圆盘移动次数
由递归的思路可以知道,我们是先将N-1个圆盘移动从A盘移动到B盘的,再将第N个圆盘移动到C盘的,在将N-1个圆盘从B盘移动到C盘
所以从这里很容易看出N个圆盘的汉诺塔移动次数是2*(N-1)个圆盘的汉诺塔移动的次数+1
实现代码:

int  hanoi (int n){
        if(n==1){
            return 1;
        }
        return 2*hanoi(n-1)+1;
    }

hd2013 蟠桃记在这里插入图片描述

#include<iostream>
#include<stdio.h>
#include<queue>
#include<algorithm>
#include<string.h>
#include<string.h>
#include<math.h>
using  namespace std;
int peach(int n)
{
	    long res = 1;//java中后面才带L我说呢,C语言不需要 
	    
	    //后面两部我就不会 
        while(--n)
            res = 2 * (res + 1);
        return res;
}
int main()
{
	int ans=0;
	int n,a[100];
	while(cin>>n)
	{		
		cout<<peach(n)<<endl;
	}
	
	return 0;
}

参考https://blog.csdn.net/qmdweb/article/details/80537602

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

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

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

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

(0)
blank

相关推荐

  • 网页406错误(网页错误代码1607)

    原因出现网页出现406问一般为一下两种情况 *1、缺失jar包, * *2、如果访问的url的后缀名是以.html结尾的,则服务端不能响应json数据。因为springMVC会误以为.html后缀名的请求,是请求访问某个html文件,则springMVC则无法处理响应json数据 解决方法 *解决方法: * 1、检查所依赖的jar包是否完整 *2、在we…

  • 如何选择开源许可证?

    如何选择开源许可证?

  • SSDP协议_固态硬盘两种协议

    SSDP协议_固态硬盘两种协议SSDP,即简单服务发现协议(SSDP,SimpleServiceDiscoveryProtocol),是一种应用层协议,是构成通用即插即用(UPnP)技术的核心协议之一。 实现简单服务发现协议是在HTTPU和HTTPMU的基础上实现的协议。按照协议的规定,当一个控制点(客户端)接入网络的时候,它可以向一个特定的多播地址的SSDP端口使用M-SEARCH方法发送“ssdp:…

    2022年10月11日
  • debounce实现 js_聊聊lodash的debounce实现

    debounce实现 js_聊聊lodash的debounce实现本文同步自我的Blog前段时间团队内部搞了一个代码训练营,大家组织在一起实现lodash的throttle和debounce,实现起来觉得并不麻烦,但是最后和官方的一对比,发现功能的实现上还是有差距的,为了寻找我的问题,把官方源码阅读了一遍,本文是我阅读完成后的一篇总结。本文只会列出比较核心部分的代码和注释,如果对全部的源码有兴趣的欢迎直接看我的repo:什么是throttle和debo…

  • idea打断点调试_vs断点调试快捷键

    idea打断点调试_vs断点调试快捷键IDEA断点调试–基础篇1前言Debug用来追踪代码的运行流程。我们通常会在程序运行过程中出现异常的时候,启用Debug模式来分析定位异常发生的位置,以及在运行过程中参数的变化。通常我们也可以启用Debug模式来跟踪代码的运行流程去学习三方框架的源码。而IDEA作为我们JAVA开发最常用的工具,所以我们对于IDEA的Debug更应该去了解一下。2断点类型IDEA中对于JAVA的断点进行了分类,有如下的4类:JavaLineBreakpoints:行断

    2022年10月20日
  • 【转载】图说OOP基础(一)

    【转载】图说OOP基础(一)

    2021年11月20日

发表回复

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

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