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

发布时间:2022-08-19 11:58

 题目来源于牛客网——斐波那契数列_牛客题霸_牛客网 (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;
    
}

 牛客网——入门练习题——斐波那契数列_第1张图片

 

这题也可以用递归的方法实现,但是完全没有必要,虽然不用创建临时变量,但是时间的消耗是上面那种方法的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);
    }

    
}

ItVuer - 免责声明 - 关于我们 - 联系我们

本网站信息来源于互联网,如有侵权请联系:561261067@qq.com

桂ICP备16001015号