🍀【递归】算法设计与分析

• 🍁1406: 数字求和
• • Java题解
• 🌺问题 B: 递归求和
• • Java题解
• 🌲问题 C: 倒序输出
• • Java题解
• 🌼1379: XP的楼梯
• • Java题解
• 🌳问题 E: 蜂房
• • Java题解
• 😫问题 G: 斐波那契数
• • Java题解

程序调用自身的编程技巧称为递归（ recursion）。

构成递归需具备的条件：

1. 子问题须与原始问题为同样的事，且更为简单；

2. 不能无限制地调用本身，须有个出口，化简为非递归状况处理。

递归算法一般用于解决三类问题：

(1)数据的定义是按递归定义的。（Fibonacci函数）

(2)问题解法按递归算法实现。

这类问题虽则本身没有明显的递归结构，但用递归求解比迭代求解更简单，如Hanoi问题。

(3)数据的结构形式是按递归定义的。

如二叉树、广义表等，由于结构本身固有的递归特性，则它们的操作可递归地描述。

递归的缺点：

递归算法解题相对常用的算法如普通循环等，运行效率较低。因此，应该尽量避免使用递归，除非没有更好的算法或者某种特定情况，递归更为适合的时候。在递归调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储。递归次数过多容易造成栈溢出等。

🍁1406: 数字求和

题目描述

使用递归编写一个程序，计算一个正整数中所有数字之和。例如输入234，输出9。

输入

多组输入，每组输入一个正整数。

输出

输出结果，每个结果占一行。

样例输入

234

样例输出

9

Java题解

题目说要用递归，但是我们可以先用习惯的思路的做一做，那就是循环；

//n是输入的整数，ans是各位之和int ans=0;while(n!=0) {    ans+=n%10;    n/=10;}

如何将其改为递归呢，可以做如下比较

1. 循环的结束条件就是递归的退出条件
2. 循环的的输入n和输出ans，就是递归的入参
3. 循环每次n/=10进入下一个循环求其个位，递归也是将n/10作为入参自身调用求其个位

这么一看来，如何不会写递归不妨先想想怎么用循环写，再去尝试如何用递归解决

class Di{int Sum(int n,int ans) {if(n==0) {return ans;}else {return Sum(n/10,ans+n%10);}}}

import java.util.Scanner; public class Main {     public static void main(String[] args) { int n; Di di=new Di(); Scanner scanner=new Scanner(System.in); while(scanner.hasNext()) {     n=scanner.nextInt();     int ans=0;     ans=di.Sum(n, ans);     System.out.println(ans);} scanner.close();    } } class Di{    int Sum(int n,int sum) { if(n==0) {     return sum; }else {     return Sum(n/10,sum+n%10); }    }}

🌺问题 B: 递归求和

题目描述

使用递归编写一个程序，求：
S(n)=1-1/2+1/3-1/4+1/5-1/6+......

输入

多组数据输入，每组输入一个正整数n。

输出

输出S(n)的计算结果（精确到小数点后六位）。

样例输入

1

样例输出

1.000000

Java题解

会了第一道其实这一到也就容易了不就是，偶数位减，奇数位加嘛

import java.util.Scanner;public class Main {public static void main(String[] args) {int n;D1 d1=new D1();Scanner scanner=new Scanner(System.in);while(scanner.hasNext()) {n=scanner.nextInt();double ans=d1.T(n, 0.0);System.out.printf("%.6f\n",ans);}scanner.close();}}class D1{public double T(int n,double ans) { //注意数据类型double i=n;if(n==1) {return ans+=1.0;} //如果是偶数位减去else if((n&1)==0){return T(n-1,ans-=(double)(1/i));} //如果是奇数位加上else {return T(n-1,ans+=(double)(1/i));}}}

🌲问题 C: 倒序输出

题目描述

使用递归编写一个程序，逆序输出一个非负整数。例如输入1234，输出4321(不含前导0)。

输入

多组输入，每组输入一个非负整数。

输出

逆序输出结果，每个结果占一行。

样例输入

1212300

样例输出

213210

Java题解

这道题处理前导0可能会卡一会，不过其实只要在进入递归调用前先乘10，而不是在递归调用类乘10，与第一题有这一点点区别

import java.util.Scanner;public class Main {public static void main(String[] args) {// TODO Auto-generated method stubint n;Dc dc=new Dc();Scanner scanner=new Scanner(System.in);while(scanner.hasNext()) {n=scanner.nextInt();int ans=dc.T(n,0);System.out.println(ans);}scanner.close();}}class Dc{public int T(int n,int ans) {if(n==0) {return ans+=0;}else {ans*=10;     //在返回值前乘10可以巧妙去除前导零/*例如120，第一次调用T（12，ans+=(0)) * 第二次调用T（1，ans+=(2)); * 第二次调用T（0，ans+=(1)); */return T(n/10,ans+=((n%10)));}}}

🌼1379: XP的楼梯

题目描述

XP是个淘气的孩子，他最近迷上了跳楼梯。他可以一次跳一级，也可以一次跳两级，他居然还能够一次跳三级楼梯（危险动作，请勿模仿）。某次，XP在跳完楼梯后突然想到一个问题，如果有n级楼梯，他从第一级开始往上跳，一直跳到第n级共有多少种不同的方案？你能帮他解决这个问题吗？当然，如果只有一级楼梯，很明显他只有一种选择。

输入

单组输入数据 n （0<n<30）

输出

输出一行结果

样例输入

29

样例输出

15902591

Java题解

这道题还是当初才进大学的时候做过，当时根本不知道怎么做，看到输出有这么大人都傻了

现在回头来做，呵呵🙂

斐波那契数列变形题

import java.util.Scanner;public class Main {public static void main(String[] args) {int n;Lou lou=new Lou();Scanner scanner=new Scanner(System.in);n=scanner.nextInt();int ans=lou.T(n);System.out.println(ans);scanner.close();}}class Lou{public int T(int n) {if(n==1) {return 1;}if(n==2) {return 1;}if(n==3) {return 2;}else {return (T(n-3)+T(n-2)+T(n-1));}}}

🌳问题 E: 蜂房

题目描述

有一只经过训练的蜜蜂只能爬向右侧相邻的蜂房，不能反向爬行。请编程计算蜜蜂从蜂房a爬到蜂房b的可能路线数。
其中，蜂房的结构如下所示。

输入

多组数据输入，每组数据包含两个正整数a, b，且 a<b。

输出

蜜蜂从蜂房a爬到蜂房b的可能路线数。

样例输入

1 23 4

样例输出

11

Java题解

这种题就是斐波那契数列的变形题

假设每一次蜜蜂都是从1开始爬

1-2有一种方法

1-3有两种方法

1-4其实就是可以看成从3号蜂房爬过来或者是从2号蜂房爬过来

就是f(4)=f(3)+f(2)

通式就是f(n)=f(n-1)+f(n-2)

import java.util.Scanner;public class Main {public static void main(String[] args) {int n,m;De de=new De();Scanner scanner=new Scanner(System.in);while(scanner.hasNext()) {n=scanner.nextInt();m=scanner.nextInt();//处理3-4蜂房int chazhi=n-1;m=m-chazhi;int ans=de.T(m);System.out.println(ans);}scanner.close();}}class De{public int T(int n) {if(n==1) {return 0;}if(n==2) {return 1;}if(n==3) {return 2;}else {return T(n-1)+T(n-2);}}}

😫问题 G: 斐波那契数

题目描述

Kimi号称自己已经记住了前100000个斐波那契数。
为了考验他，我们随便出一个数n，让他说出第n个斐波那契数。
当然，斐波那契数会很大。
因此，如果第n个斐波那契数不到6位，则说出该数；否则只说出最后6位(无需输出前导0)。

输入

输入有多组数据。每组数据一行，包含一个整数n (1≤n≤100000)。

输出

对应每一组输入，输出第n个斐波那契数的最后6位。

样例输入

1234100000

样例输出

1235537501

Java题解

看着这个数据量就知道不能用递归来做了，肯定会超时的；但我还是用了递归，而且还用了大整数类写，结果写了一节课头都转晕了，还栈爆了，我也不知道对不对，反正先贴出来，说不定下次又遇到了

❌Java大整数类：错误解法

import java.math.BigInteger;import java.util.Scanner;public class Main {public static void main(String[] args) {BigInteger n;Dg dg=new Dg();Scanner scanner=new Scanner(System.in);while(scanner.hasNext()) {n=scanner.nextBigInteger();System.out.println(n);BigInteger ans=dg.T(n);if(ans.toString().length()>=6) {System.out.println(ans);}else {int len=ans.toString().length();String aString=ans.toString().substring(len-7, len-1);System.out.println(aString);}}scanner.close();}}class Dg{public BigInteger T(BigInteger n) {BigInteger a=BigInteger.valueOf(1);BigInteger b=BigInteger.valueOf(2);if(n.equals(1)) {return a;}if(n.equals(2)) {return b;}else {return T(n.subtract(a)).add(T(n.subtract(b)));}}}

我就用数组写吧，先是用java写的，直接存储数组里，呵呵，还是超时

❌时间超限

import java.util.Scanner;public class Main {public static void main(String[] args) {//Vector ve=new Vector();Scanner scanner=new Scanner(System.in);int n;while(scanner.hasNext()) {n=scanner.nextInt();int []num=new int[n+3];     num[0]=1;num[1]=2;     int ans=0;if(n==1) {ans=1;}else if(n==2){ans=2;}else {int i;for(i=2;i<n;i++){num[i]=(num[i-1]+num[i-2])%1000000;}ans=num[i-1];}System.out.println(ans);}scanner.close();}}

换成c/c++来，想着c/c++不是快嘛，说不定用c/c++就过来，我看看到底有多快，考虑到cin和cout读取和输出数据慢，我还特意用了scanf()和printf()；呵呵，还是超时

❌时间超限

#include#includeusing namespace std;int num[100010];int main(){int n;while((scanf("%d",&n))!=EOF) {num[0]=1;num[1]=2;int ans=0;     if(n==1) {ans=1;}else if(n==2){ans=2;}else {int i;for(i=2;i<n;i++){num[i]=(num[i-1]+num[i-2])%1000000;}ans=num[i-1];}printf("%d\n",ans);}}

实在想不出了，我就去问了我们班的OJ大佬，结果犯了一个以前就犯过的错误，而且还学到了时间超限到底是怎么回事

当然栈溢出并不是主要问题了，第三张图才是我的问题根源之处

改了之后立马就过了，其实自己之前做过大整数的题，当时自己就是这样处理的，一年不到就已经重蹈覆辙了，这学期一点要努力刷题👀

✔c/c++:正确题解

#include<iostream>#include<stdio.h>using namespace std;int MaxNum;int Max=1000000;int num[100010];int main(){int n;num[0]=1;num[1]=2;for(int i=2;i<100001;i++){     num[i]=(num[i-1]+num[i-2])%Max; }while((scanf("%d",&n))!=EOF) {int ans=0;ans=num[n-1];printf("%d\n",ans);}}

Java也交了一遍，也是一下子就过了

✔Java题解

import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner scanner=new Scanner(System.in);int n;int []num=new int[100000+1];num[0]=1;num[1]=2;for(int i=2;i<100001;i++){num[i]=(num[i-1]+num[i-2])%1000000;}while(scanner.hasNext()) {n=scanner.nextInt();int ans=num[n-1];System.out.println(ans);}scanner.close();}}

艺术系歌词下载吧