C语言实现青蛙跳台阶问题【图解】-阿里云开发者社区

C语言实现青蛙跳台阶问题【图解】

2023-06-19 341

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： C语言实现青蛙跳台阶问题，两种思考方向

编辑

问题分析方法1：找规律
问题分析方法2：递归
两种方法的代码

题目

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

编辑

问题分析方法1：找规律

当n=1时，显然，青蛙只有一种跳法

当n=2时，青蛙可以跳两次一级台阶，也可以直接跳两节台阶，有两种跳法 编辑

当n=3时，青蛙可以跳三次一级台阶

可以直接跳一次两节台阶，再跳一次一级台阶

也可以先跳一次一级台阶，再跳一次二级台阶有三种跳法

编辑

当n=4时......一共有5种跳法 编辑

以此类推，找规律：

n=3时的总次数为n=1和n=2的次数总和

n=4时的总次数为n=2和n=3的次数总和

......

第N次的总次数等于n=n-1和n=n-2的次数总和

则题目的递推性质规律已经显而易见了，典型的斐波那契数列问题

F(n) = F(n-1) + F(n-2)

我们可以直接使用求解斐波那契数列的方法

将第一项值赋为1，第二项值赋为2，然后一直向后循环直到n即可

问题分析方法2：递归

使用递归的思想：

当青蛙要上n阶台阶的时候，首先它要先上n-1阶台阶，然后再上一次一阶台阶

或者它要先上n-2阶台阶，然后再上一次二阶台阶

当青蛙要上n-1阶台阶的时候，首先它要先上n-2阶台阶，然后再上一次一阶台阶

或者它要先上n-3阶台阶，然后再上一次二阶台阶

......以此类推

那么它上n阶台阶的总次数就是上n-1阶台阶的总次数加它上n-2阶台阶的总次数

依然可以总结为

F(n) = F(n-1) + F(n-2)

两种方法的代码

//循环
#include<stdio.h>
int main()
{
  int i = 1;
  int j = 2;
  int ret = 0;
  int n = 0;
  int z = 0;
  scanf("%d", &n);
  for (ret = 3; ret <= n; ret++)
  {
    z = i + j;
    i = j;
    j = z;
  }
  if (n == 1)
    z = 1;
  if (n == 2)
    z = 2;
  printf("%d", z);
  return 0;
}
//递归
#include<stdio.h>
int Fib(int x)//第一个和第二个斐波那契数都是1
{
  if (x == 1)
    return 1;
  else if (x == 2)
    return 2;
  else
    return Fib(x - 1) + Fib(x - 2);
}
int main()
{
  int n = 0;
  scanf("%d", &n);
  int ret = Fib(n);
  printf("%d", ret);
  return 0;
}