Jasin Yip

计蒜客【挑战难题】系列讲解(四)简单斐波那契

题目

第4题:简单斐波那契

  斐波那契数列是一种非常有意思的数列,由 0 和 1 开始,之后的斐波那契系数就由之前的两数相加。
  用数学公式定义斐波那契数列则可以看成如下形式:
F0=0
F1=1
Fn=Fn-1+Fn-2
  我们约定Fn表示斐波那契数列的第n项,你能知道斐波那契数量中的任何一项吗?
  输入包括一行,包括一个数字N(0≤N≤50)。
  输出包括一行,包括一个数字,为斐波那契数列的第N项的值。

样例输入

7

样例输出

13

C 实现

#include <stdio.h>  
  
int fib(int N){  
    int i;  
    int arr[50] = {0};  //由于题目说明N的取值范围是(0≤N≤50),故定义数组为50  
      
    arr[1] = 1;   
    for (i = 2; i <= N; i++)  
        arr[i] = arr[i-1] + arr[i-2];  
  
    return arr[N];  //返回结果  
}  
  
int main(){  
    int N = 0;  
    scanf("%d", &N);  
    printf("%d", fib(N));   //输出结果直接调用函数计算  
      
    return 0;  
}  

它如何工作

  这题实际上只是考验对循环的运用,这里我使用了函数去计算结果。

  首先,根据定义,先把arr[

小贴士

  函数的概念其实很简单,我把它比喻为一台计算器,给计算器两个数字,并且加上一个运算符,它就给我返回一个结果。
  这就是函数的概念,调用函数时,只需要明白该函数有什么用。
  像题中的函数,作用就是:我给你N,你返回斐波那契数列的第N项的值给我。
  详细对于函数的学习,请移步至计蒜客C语言基础第35课:什么是函数

  实际上,斐波那契数列是经典的递归题,但我觉得很多时候不一定只靠递归才能解决问题,循环有时也挺方便的。

标签:c语言, 计蒜客, 挑战难题

已有 5 条评论

  1. gli gli

    这段代码是错误的。为什么计蒜客认为是正确的?这边界测试一定不通过。fib结果用int保存会溢出。注意题目给的是[0,50]。

  2. 1 1

    1

  3. wsxxhx wsxxhx

    楼主这里的数组有点突兀,,因为之前的课程并没有讲数组

  4. genius.he genius.he

    O(n)的复杂度,在N特别大的时候还是非常慢,有O(1)的算法(在损失精度的情况下-可容忍)

  5. Very fast shipping ! Love the colors &amp; pattern. Perfect fit for my Nook

添加新评论