牛客网——入门练习题——斐波那契数列

 题目来源于牛客网——斐波那契数列_牛客题霸_牛客网 (nowcoder.com)

示例1

输入：

4

复制返回值：

3

复制说明：

根据斐波那契数列的定义可知，fib(1)=1,fib(2)=1,fib(3)=fib(3-1)+fib(3-2)=2,fib(4)=fib(4-1)+fib(4-2)=3，所以答案为3。  

示例2

输入：

1

复制返回值：

1

复制

示例3

输入：

2

复制返回值：

1

复制

 由题目可知：数列的第一项和第二项都是1，且我们要求出后面的项就要知道其前两项之和

/**
 * 
 * @param n int整型 
 * @return int整型
 *
 * C语言声明定义全局变量请加上static，防止重复定义
 */
int Fibonacci(int n ) {
    // write code here
    int a = 1;
    int b = 1;
    int c = 0;  //定义临时变量来存储前两项之和
    if(n <= 2)
    {
        return 1;
    }
    while(n > 2)
    {
        c = a + b;
        a = b;
        b = c;
        n--;
    }
    return c;
    
}

这题也可以用递归的方法实现，但是完全没有必要，虽然不用创建临时变量，但是时间的消耗是上面那种方法的50倍

递归的方法如下：

/**
 * 
 * @param n int整型 
 * @return int整型
 *
 * C语言声明定义全局变量请加上static，防止重复定义
 */
int Fibonacci(int n ) {
    // write code here

    if(n <= 2)
    {
        return 1;
    }
    else
    {
		return Fibonacci(n - 1) + Fibonacci(n- 2);
    }

    
}