递归算法介绍和【题解】——数楼梯

1.递推算法介绍

    有些目标是宏大的，比如如果你想找到一个好工作，需要先把面试通过。要把面试通过，就需要在大学努力学习。如果想听懂大学的课，就需要先听懂中学的课。想要听懂中学的课，又需要在小学好好听讲……

    在小学好好听讲->听懂中学的课->在大学努力学习->通过面试绩->找到好工作

    像这样，将一个很大的任务分解成规模小一些的子任务，子任务分成更小的子任务，直到遇到初始条件整理归纳解决大任务就是递推和递归思想。

2.数楼梯

通往洛谷的传送门

题目描述

楼梯有 $N$ 阶，上楼可以一步上一阶，也可以一步上二阶。

编一个程序，计算共有多少种不同的走法。

输入格式

一个数字，楼梯数。

输出格式

输出走的方式总数。

输入输出样例

输入 #1

4

输出 #1

5

提示

• 对于 $60\%$ 的数据，$N\le 50$；
• 对于 $100\%$ 的数据，$1\le N\le 5000$。

1.思路解析

    想要模拟每一种到最后一阶的方法然后累加是不行的，需要花费的时间太长了。

    不过可以发现，想要走到第$i$阶，就需要先走到第$i-1$阶或$i-2$阶。那么走到第$i$阶的方法数就是走到第$i-1$阶和走到第$i-2$阶的方法数之和。

    因此，我们定义一个f数组，f[i]表示走到第i阶的方法数。接下来只要迭代计算f[i]=f[i-1]+f[i-2]就行了。递推中，像f[i]=f[i-1]+f[i-2]这样的式子就叫做递推式。（其实可以发现，它和斐波那契数列有着异曲同工之妙。）

    不过要注意，当i=1或i=2时，只需要一步就可以跨上去了。所以需要初始化f[1]=f[2]=1;。像这样的条件就叫做递推边界。

    最后，由于数字比较大，需要使用高精度数存储。详见这一篇文章

2.AC代码

#include<bits/stdc++.h>
using namespace std;
struct bigint//定义高精度整形 
{
	int a[100],len;//调试的时候数组大小定小一点,不然会导致栈空间溢出 
	bigint(int x=0)
	{
		memset(a,0,sizeof(a));
		if(x==0)
		{
			len=1;
			return;
		}
		for(len=1;x;len++)
		    a[len]=x%10,x/=10;
		len--;
	}
	int &operator[](int i)
	{
		return a[i];
	}
	void print()
	{
		for(int i=len;i>=1;i--)
		    cout<<a[i];
	}
	void flatten(int L)
	{
		len=L;
		for(int i=1;i<=len;i++)
		    a[i+1]+=a[i]/10,a[i]%=10;
		while(!a[len])
		    len--;
	}
	friend bigint operator+(bigint a,bigint b)//只需要实现高精度加法 
	{
		bigint c;
		int _len=max(a.len,b.len);
		for(int i=1;i<=_len;i++)
		    c[i]+=a[i]+b[i];
		c.flatten(_len+1);
		return c;
	}
};
int main()
{
    int n;
	bigint f[5010];//f[i]代表上到第i个台阶的方法数 
    cin>>n;
    f[1]=bigint(1);//初始条件,上到第一个台阶只有1种方案 
	f[2]=bigint(2);//初始条件,上到第二个台阶只有2种方案 
    for(int i=3;i<=n;i++)//从第三个台阶开始循环 
        f[i]=f[i-1]+f[i-2];//递推式 
    f[n].print();
	return 0;
}

喜欢就订阅此专辑吧！

【蓝胖子编程教育简介】
蓝胖子编程教育，是一家面向青少年的编程教育平台。平台为全国青少年提供最专业的编程教育服务，包括提供最新最详细的编程相关资讯、最专业的竞赛指导、最合理的课程规划等。本平台利用趣味性和互动性强的教学方式，旨在激发孩子们对编程的兴趣，培养他们的逻辑思维能力和创造力，让孩子们在轻松愉快的氛围中掌握编程知识，为未来科技人才的培养奠定坚实基础。

欢迎扫码关注蓝胖子编程教育