Frog jumping steps (recursive and non-recursive) ------- Xiaolele walks the steps

小青蛙跳台阶

一、 问题描述

一只青蛙一次可以跳上1级台阶,也可以跳上2级.求该青蛙跳上一个n级的台阶总共有多少种跳法？？？

二、分析问题

当n=1时,有一种跳法
当n=2时,有两种跳法
1.跳一级,跳一级
2.跳两级
当n=3时,There are three jumps
1.跳一级,跳一级,跳一级
2.跳一级,跳两级
3.跳两级,跳一级

先假设f(n)为 n 级台阶的总跳法数;

Then if you choose to skip one level for the first time,剩下的 n-1 The number of jumps for each step is f(n−1).

If you jump two levels for the first time,剩下的 n-2 级台阶的跳法就是f(n−2);

所以,当有nThere are stepsf(n)=f(n-1)+f(n-2)种跳法.

三、代码实现（递归）

#include<stdio.h>
int steps(int x)
{
    
	if (x == 1)
	{
    
		return 1;
	}
	if (x == 2)
	{
    
		return 2;
	}
	return steps(x - 1) + steps(x - 2);
}
int main()
{
    
	int n = 0;
	scanf("%d", &n);
	printf("%d", steps(n));
	return 0;
}

四、代码实现（非递归）

#include<stdio.h>
int steps(int x)
{
    
	if (x < 3)
	{
    
		return x;
	}
	int final1 = 1;//Countdown to the first jump
	int final2 = 2;//The penultimate jump
	int sum = 0;//Count how many in total
	for (int i = 3; i <= x; i++)
	{
    
		sum = final1 + final2;
		final1 = final2;
		final2 = sum;
	}
	return sum;
}
int main()
{
    
	int n = 0;
    scanf("%d", &n);
	printf("%d", steps(n));
	return 0;
}