每日一数——使用函数求Fibonacci数

📙斐波那契数列简介：

• 斐波那契数列（Fibonacci sequence）
• 又称 黄金分割 数列，因数学家莱昂纳多·斐波那契（Leonardo Fibonacci）以兔子繁殖为例子而引入，故又称为“兔子数列”，指的是这样一个数列：1、1、2、3、5、8、13、21、34、……
• 在数学上，斐波那契数列以如下被以递推的方法定义： F (0)=0， F (1)=1, F (n)= F (n - 1)+ F (n - 2)（ n ≥ 2， n ∈ N*）
• 在现代物理在现代物理、准 晶体结构 、化学等领域，斐波那契数列都有直接的应用。

📗斐波那契数列在C语言中的求解：

1.📃常规求解：

• 根据上图，我们可以简单的理解为：斐波那契数列第一二项为1，后面一项则是前两项的和，依次递推下去。
• 所以这里我们采用类似分段函数的方式求解。

#include <stdio.h>
int fib(int n)
{
    int a = 1, b = 1, i = 0;
    int c = 0;
    if (n <= 2)
        return 1;
    else
    {
        for (i = 0; i < n - 2; i++)
        {
            c = a + b;
            a = b;
            b = c;
        }
        return b;
    }
}
int main()
{
    int n;

    scanf("%d", &n);
    printf("%d\n", fib(n));

    return 0;
}

• 领方法常规，计算量相对较少。

2.函数递归法：

• 这种方法就结合了数学递推关系。需要学会函数递归思想才能理解（以后函数会详细讲解）。

#include <stdio.h>
int fib(int n)
{
    if (n > 2)
        return  fib(n - 1) + fib(n - 2);
    else
        return 1;
}
int main()
{
    int n;

    scanf("%d", &n);
    printf("%d\n", fib(n));

    return 0;
}

• 域，斐波那这种方法的弊端也很明显：就是费电脑，如果n的输入值比较大，由于计算量会很大，这种方式1表达不够简单，在做题中容易发生答题超时。

📘青蛙跳问题：

问题概述：

• 一只青蛙要跳上一定数量的台阶，但其一次只能跳一阶或两阶，求这只青蛙跳上n上台阶有多少中跳法？

问题分析：

• 当n=1时，青蛙只能有一种跳法；
• 当n=2时，青蛙可以先跳一阶，在跳一阶；也可以直接跳两阶。共两种跳法；
• 当n=3时，青蛙可以先跳一阶再跳两阶，也可以先跳两阶在跳一阶，还可以一阶一阶的跳，共三种跳法；
  - 这样理解或许有些麻烦，我们还可以采用更快的理解方式。
• 当n=3时，我们可以理解为如果青蛙先跳一阶，这后面我们可以理解为n=2时的跳法，若青蛙先跳两阶，后面可以理解为n=1的跳法。
• 以此类推，当n=m时，跳法总数 = （当n=m-1的跳法总数） + （当n=m-2的跳法总数）。
• 这样递推就类似上面讲的斐波那契数列了，但不完全一样。

#include <stdio.h>
int like_fib(int n)
{
  if (n == 1)
  {
    return 1;
  }
  else if (n == 2)
  {
    return 2;
  }
  else if (n > 2)
  {
    return f(n - 1) + f(n - 2);//递归
  }

}
int main()
{
  printf("青蛙要跳几个台阶=>");
  int a = 0;
  scanf("%d", &a);
  printf("青蛙会有几种跳法=>");
  printf("%d", like_fib(a));

}