【剑指offer】面试题10：斐波那契数列

我会带着你远行 2022-06-12 03:13 123阅读 0赞

## 完整代码地址 ##

[完整代码地址][Link 1]

## 题目 ##

求斐波那契数列的第n项（n<=39）  
写一个函数，输入n，求斐波那契(Fibonacci)数列的第n项  
斐波那契数列的定义如下：  
　　　　┌ 0　　　　　　　,　　n = 0  
f(n)=　　├ 1　　　　　　　,　　n = 1  
　　　　└ f(n-1) + f(n-2)　　,　　n > 1

0,1,1,2,3,5,8,13…

## 思路 ##

不要用递归的方式，效率会出问题  
解法：不断往上求解f(n-2)和f(n-1)，思路很简单

## 代码 ##

public static int Fibonacci(int n) {
        if(n <= 0) 
            return 0;
        if(n == 1) 
            return 1;
    
        int min = 0;
        int max = 1;
        int fib = 1;
        for(int i = 2; i <= n; ++i) {
            fib = max + min;
            min = max;
            max = fib;
        }
        return fib;
    }

## 测试 ##

public static void main(String[] args) {
        test1();
        test2();
    }
    
    /**
     * 功能测试 && 边界值测试
     */
    private static void test1() {
        for(int i = 0; i < 10; ++i) {
            System.out.print(_10_Fibonacci.Fibonacci(i) + " ");
        }
        System.out.println();
    }
    
    /**
     * 性能测试
     */
    private static void test2() {
        System.out.println(_10_Fibonacci.Fibonacci(20));
        System.out.println(_10_Fibonacci.Fibonacci(39));
    }

[Link 1]: https://github.com/linpeiyou/CodingInterviews

发表评论取消回复

表情：

评论列表（有 0 条评论，123人围观）

还没有评论，来说两句吧...

相关阅读

相关剑指offer | 10.斐波那契数列

题目内容 > 写一个函数，输入 n ，求斐波那契（Fibonacci）数列的第 n 项。斐波那契数列的定义如下： > > F(0) = 0, F(1) = 1 F(N) =

小咪咪/ 2022年12月22日 06:12/ 0 赞/ 82 阅读

相关剑指offer面试题斐波那契数列

题目描述：写一个函数，输入n，求斐波那契数列的第n项。斐波那契数列的定义如下： ![Center][] 如果用递归方式求解这个问题，会产生大量的重复运算，而且随着n的

淩亂°似流年/ 2022年08月21日 06:55/ 0 赞/ 95 阅读

相关剑指offer_面试题9_斐波那契数列

题目一：写出一个函数，输入n，求斐波那契数列的第n项。题目二：一只青蛙一次可以跳上1级台阶，也可以跳上2级。请求青蛙上一个 n 级的台阶总共有多少种跳法。第二个题目，其

川长思鸟来/ 2022年08月03日 08:21/ 0 赞/ 119 阅读

相关【剑指offer】面试题10：斐波那契数列

完整代码地址 [完整代码地址][Link 1] 题目求斐波那契数列的第n项（n<=39）写一个函数，输入n，求斐波那契(Fibonacci)数列的第n项

我会带着你远行/ 2022年06月12日 03:13/ 0 赞/ 124 阅读

相关剑指offer：斐波那契数列

题目描述大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0）。 n<=39 class Solution {

超、凢脫俗/ 2022年04月14日 05:13/ 0 赞/ 241 阅读

相关【剑指offer】面试题10：斐波那契数列

> 题目1：求斐波那契数列的第n项。写一个函数，输入n，求[斐波那契数列][Link 1]（Fibonacci）数列的第 n 项。斐波那契数列的定义如下： ![f(n)

迈不过友情╰/ 2022年03月31日 09:16/ 0 赞/ 115 阅读

相关【剑指Offer】斐波那契数列

题目链接：[https://www.nowcoder.com/practice/c6c7742f5ba7442aada113136ddea0c3?tpId=13&tqId=11

我不是女神ヾ/ 2022年03月15日 05:08/ 0 赞/ 217 阅读

相关《剑指offer》面试题10-斐波那契数列

一、题目题目：写一个函数，输入n，求斐波那契（Fibonacci）数列的第n项。二、题目分析最简单的方法就是采用递归的方法

不念不忘少年蓝@/ 2022年03月09日 03:54/ 0 赞/ 122 阅读

相关剑指Offer-斐波那契数列

题目描述大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0）。注：n<=39 初步解题思路：一看到斐波那契数列，即F(

系统管理员/ 2022年03月06日 16:56/ 0 赞/ 203 阅读

相关剑指offer-斐波那契数列

首先我们需要知道斐波那契数列是什么东西，其实很容易理解，斐波那契数列的公式是：F(x) = F(x-1) + F(x-2) ，F(0) = 0; F(1) = 1; 所以数列如

绝地灬酷狼/ 2022年02月19日 00:51/ 0 赞/ 215 阅读