算法記錄 >> 斐波那契數(shù)列

robin 發(fā)布于2019-08-16 17:52 / 2514人閱讀

摘要：今天去面試筆試題斐波那契數(shù)列實(shí)現(xiàn)，雖然很簡(jiǎn)單。回來(lái)想想既然算法這么重要那就從這個(gè)開(kāi)始來(lái)記錄自己的算法庫(kù)吧。在數(shù)學(xué)上，斐波納契數(shù)列以如下被以遞歸的方法定義，，。斐波拉契算法規(guī)律很簡(jiǎn)單，，觀察下數(shù)列值就很容易總結(jié)出來(lái)了。

一、寫在前面

算法這塊對(duì)于大多數(shù)程序員（包括我）來(lái)說(shuō)可能都是一個(gè)薄弱的地方，如何彌補(bǔ)尼？每個(gè)人都知道那就是學(xué)習(xí)、特別是算法沒(méi)有任何捷徑可走。

在這記錄平時(shí)自己工作和生活中遇到的一些算法，以便來(lái)自己來(lái)溫故。

今天去面試筆試題斐波那契數(shù)列實(shí)現(xiàn)，雖然很簡(jiǎn)單。回來(lái)想想既然算法這么重要那就從這個(gè)開(kāi)始來(lái)記錄自己的算法庫(kù)吧。

二、簡(jiǎn)介

斐波那契數(shù)列（Fibonacci sequence）的定義：斐波拉契數(shù)列是指這樣的一組數(shù)據(jù) 0、1、1、2、3、5、8、13、21……這個(gè)數(shù)列其實(shí)很容易找到規(guī)律的從第三項(xiàng)開(kāi)始每一項(xiàng)值都等于前兩項(xiàng)之和（fn = f(n-1) + f(n-2)）

斐波那契數(shù)列又稱黃金分割數(shù)列、因數(shù)學(xué)家列昂納多·斐波那契（Leonardoda Fibonacci）以兔子繁殖為例子而引入，故又稱為“兔子數(shù)列”。在數(shù)學(xué)上，斐波納契數(shù)列以如下被以遞歸的方法定義：F(0)=0，F(xiàn)(1)=1, F(n)=F(n-1)+F(n-2)（n>=2，n∈N*）。

算法基本概念很好理解，下面我們來(lái)看看用代碼來(lái)實(shí)現(xiàn)下。

實(shí)現(xiàn)

其實(shí)數(shù)學(xué)公式已經(jīng)有了，F(xiàn)(0)=0，F(xiàn)(1)=1, F(n)=F(n-1)+F(n-2) 那我們就用遞歸來(lái)實(shí)現(xiàn)下

public class PrintFib {
    
    //建立一個(gè)函數(shù)，用于計(jì)算數(shù)列中的每一項(xiàng)
    public static int fib(int num) {
        if(num <= 0 ){
            return 0;
        }
        if(num == 1 || num == 2) {
            return 1;
        }
            //循環(huán)調(diào)用本函數(shù)
        return fib(num - 2) + fib(num - 1);
        }
    
    
    //主函數(shù)（程序入口）
    public static void main(String[] args) {
        
        //建立一個(gè)for循環(huán)，用于打印第一個(gè)至第十個(gè)數(shù)字
        for(int i = 1;i <= 10;i++) {
            //調(diào)用函數(shù)進(jìn)行打印
            System.out.print(fib(i) + "	");
        }    
    }
    
}

實(shí)現(xiàn)很簡(jiǎn)單，結(jié)果我就不答應(yīng)了，感興趣的同學(xué)可以自己試一下。

總結(jié)

算法的學(xué)習(xí)是一個(gè)很枯燥的過(guò)程，但是當(dāng)你征服一個(gè)算法也會(huì)給你帶來(lái)很大愉悅感。

在學(xué)習(xí)算法時(shí)，我們首先要搞明白其產(chǎn)生的原因，是為了解決什么問(wèn)題，再去學(xué)習(xí)起數(shù)學(xué)公式，最后在以coding的方式去實(shí)現(xiàn)就比較簡(jiǎn)單了。

斐波拉契算法規(guī)律很簡(jiǎn)單，F(xiàn)(0)=0，F(xiàn)(1)=1, F(n)=F(n-1)+F(n-2) 觀察下數(shù)列值就很容易總結(jié)出來(lái)了。

當(dāng)你總結(jié)出規(guī)律后使用代碼實(shí)現(xiàn)起來(lái)就比較簡(jiǎn)單了。