算法 递推 杭州电子科技大学考研机试题 acwing3643上楼梯

2023-12-28 22:31:18

是什么?

? ? ? ?是一种通过利用已知的初始条件和递推关系,逐步推导出更复杂情况的算法。它通常用于解决数列、数值序列或逻辑问题等。

关键要素

  1. 初始条件:确定初始情况下的解。这是递推算法中的基础情况,通常是已知或容易计算的情况。

  2. 递推关系:确定如何通过已知的解推导出更复杂情况的解。递推关系通常是一个数学公式或算法规则,描述了问题的演进或变化规律。

  3. 终止条件:确定递推的结束条件。一旦终止条件满足,算法就会停止递推,并返回最终的解。

例子

计算斐波那契数列的第n项。递推关系:斐波那契数列的第n项(记作F(n))等于前两项的和,即 F(n) = F(n-1)+ F(n-2),其中 F(1) = 1,F(2) = 1。

杭州电子科技大学考研机试题 acwing3643 上楼梯

一个楼梯共有?n级台阶,每次可以走一级或者两级或者三级,问从第?0?级台阶走到第?n级台阶一共有多少种方案。

输入格式

一个整数?N。

输出格式

一个整数,表示方案总数。

数据范围

1≤N≤20

输入样例:
4
输出样例:
7
代码
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
int a[30]={1,1,2};
int main()
{
	int N;
	cin>>N;
	for(int  i= 3;i<=N;i++)
	{
		a[i]=a[i-1]+a[i-2]+a[i-3];
	}
	cout<<a[N];
	return 0;
}

为什么用递推?

多写几级台阶和对应的方法,i为级数,m=方法数,不难发现

i为0,m=1;

i为1,m=1;

i为2,m=2;

i为3,m=4;

i为4,m=7;

i为5,m=13;推出规律 第i级台阶到达的方法数位前三层方法数之和,代码体现如下

文章来源:https://blog.csdn.net/m0_62793538/article/details/135256789
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。