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

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

image.gif编辑

目录

    题目

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

    image.gif编辑

    问题分析方法1:找规律

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

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

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

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

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

    image.gif编辑

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

    以此类推,找规律:

     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;
    }

    image.gif

    image.gif编辑只需要将n=1和n=2作为递归的结束条件即可

    本文已收录于C语言学习专题

    如果觉得文章不错,期待你的一键三连,相信优秀的你不会吝啬一个免费的三连的

    欢迎大家与博主讨论问题

    image.gif

    相关文章
    |
    2月前
    |
    存储 编译器 C语言
    爱上C语言:函数递归,青蛙跳台阶图文详解
    爱上C语言:函数递归,青蛙跳台阶图文详解
    |
    8月前
    |
    C语言
    【C语言刷题】青蛙跳台阶
    【C语言刷题】青蛙跳台阶
    109 1
    |
    28天前
    |
    算法 C语言
    C语言实现青蛙跳台阶问题
    C语言实现青蛙跳台阶问题
    26 5
    |
    2月前
    |
    C语言
    C语言递归问题【青蛙跳台阶】和【汉诺塔】
    C语言递归问题【青蛙跳台阶】和【汉诺塔】
    |
    2月前
    |
    C语言
    【C语言】青蛙跳台阶 —— 详解
    【C语言】青蛙跳台阶 —— 详解
    |
    2月前
    |
    C语言 索引
    【C语言】C语言⻘蛙跳台阶问题--递归问题
    【C语言】C语言⻘蛙跳台阶问题--递归问题
    |
    3天前
    |
    存储 缓存 C语言
    【C语言】字符函数,字符串函数,内存函数
    C语言中的字符串函数和内存函数
    9 0
    【C语言】字符函数,字符串函数,内存函数
    |
    10天前
    |
    C语言
    C语言5 字符输出函数和格式输出函数
    C语言5 字符输出函数和格式输出函数
    15 1
    |
    11天前
    |
    算法 编译器 C语言
    深入浅出C语言—【函数】下
    深入浅出C语言—【函数】下
    |
    23天前
    |
    Java C语言 C++
    定义C语言的int main()函数
    定义C语言的int main()函数