递归入门

递归入门

一:什么是递归

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

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

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

我们以阶乘作为:

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)


相关推荐

  • gpio引脚介绍 树莓派3b_树莓派3B+ GPIO 入门

    gpio引脚介绍 树莓派3b_树莓派3B+ GPIO 入门GPIO编号方式GPIO(GeneralPurposeInput/Output)的意思就是通用型输入输出,有三种方法可以对RaspberryPi上的IO引脚进行编号:BOARD编号,这是指RaspberryPi针脚接头上的引脚号。BCM编号,这是指BroadcomSOC的通道号码,需使用通道号所对应的树莓派板上的引脚。wringPi编号,wringPi库使用…

  • mybatis拦截器修改sql_javaweb拦截器是什么

    mybatis拦截器修改sql_javaweb拦截器是什么/***Copyright2009-2016theoriginalauthororauthors.**LicensedundertheApacheLicense,Version2.0(the”License”);*youmaynotusethisfileexceptincompliancewiththeLicense.*…

  • ELK搭建开源日志系统(window版本)—图文详细

    ELK搭建开源日志系统(window版本)—图文详细ELK搭建开源日志系统(window版本)—图文详细日志对于排查错误非常重要,使用linux命令awksedgrepfind等命令查询日志非常麻烦,而且很难做数据分析,使用免费开源的ELK可以支撑大规模的日志检索,本文将一步步教怎么快速搭建一个window版本的ELK日志收集系统。下载elasticsearch、logstash、kibana、filebeat注意同一系列的版本要一样,防止出现版本不兼容问题,本文使用7.16.0版本,在window系统演示下载elasticsearch访问地

  • Android ListView滚动条配置完全解析

    Android ListView滚动条配置完全解析详细介绍ListView中和滚动条相关的所有配置,包括普通滚动条和快速滚动条。

  • HTML5学习笔记之History API

    这系列文章主要是学习Html5相关的知识点,以学习API知识点为入口,由浅入深的引入实例,让大家一步一步的体会"h5"能够做什么,以及在实际项目中如何去合理的运用达到使用自如,完美

    2021年12月28日
  • sql查询序列是否存在_oracle if判断是否为空

    sql查询序列是否存在_oracle if判断是否为空sql如下:selectsequence_namefromuser_sequenceswheresequence_name=’参数’需要注意的是oraclesequence参数必须转换成大写。例子:(这是使用simple框架实现)//判断oraclesequence是否已经存在publicstaticbooleanisSequenceExi…

    2022年10月10日

发表回复

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

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