斐波那契數(shù)列（求fibonacci的第N項(xiàng)的值）

Fundebug 發(fā)布于2019-08-16 12:35 / 2742人閱讀

摘要：今天在公司實(shí)習(xí)，實(shí)在沒啥活是我能干的，就想著寫一寫算法打發(fā)時(shí)間，正好看到了斐波那契數(shù)列，搞起。這是斐波那契數(shù)列的通項(xiàng)公式以前用遞歸寫過，今天看的時(shí)候書上說遞歸雖然簡單，但其實(shí)內(nèi)部做了很多重復(fù)的計(jì)算，而且尾遞歸都是可以用循環(huán)解決的。

今天在公司實(shí)習(xí)，實(shí)在沒啥活是我能干的，就想著寫一寫算法打發(fā)時(shí)間，正好看到了斐波那契數(shù)列，搞起。

這是斐波那契數(shù)列的通項(xiàng)公式：

以前用遞歸寫過，今天看的時(shí)候書上說遞歸雖然簡單，但其實(shí)內(nèi)部做了很多重復(fù)的計(jì)算，而且尾遞歸都是可以用循環(huán)解決的。而用循環(huán)就可以避免重復(fù)的計(jì)算。

import java.util.Scanner;

public class Jianzhi{

    public static void main (String[] args){
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        n = fibonacci(n) ;
        System.out.println(n) ;
    }
    public static int fibonacci(int n ) {

        int f0 = 0;
        int f1 = 1;
        int fn = 0 ;
        if (n == 0) {
            return f0;
        }
        if (n == 1) {
            return f1;
        } else {
            for (int i = 2; i <= n; i++) {
                fn = f0 + f1;  //當(dāng)前循環(huán)所得的斐波那契數(shù)等于前一個(gè)加上前前個(gè)
                f0 = f1 ;     //當(dāng)前循環(huán)所得的斐波那契數(shù)的前一個(gè)數(shù)，作為下次循環(huán)的前前個(gè)次數(shù)
                f1 = fn ;     //當(dāng)前循環(huán)所得的斐波那契的數(shù)，作為下次循環(huán)的前一個(gè)數(shù)
            }
            return fn;
        }
    }

}

斐波那契數(shù)列的變換：
比如，從前有一只青蛙，它一次可以跳一個(gè)臺階，也可以一次跳兩個(gè)臺階，求一個(gè)N階的臺階他會(huì)用幾種跳法。

那就是假設(shè)就1個(gè)臺階那就只有1種跳法；如果有2個(gè)臺階，那就有2種；以此類推：

完畢。

云服務(wù)器 GPU云服務(wù)器波那契數(shù)列 fibonacci數(shù)列 python求π的值解斐波

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://m.specialneedsforspecialkids.com/yun/71370.html

相關(guān)文章

斐波那契數(shù)列求和的js方案以及優(yōu)化

摘要：在上做了一道斐波那契數(shù)列求和的題目，做完之后做了一些簡單的優(yōu)化和用另一種方法實(shí)現(xiàn)。動(dòng)態(tài)規(guī)劃解決方案斐波那契數(shù)列求和除了可以用遞歸的方法解決，還可以用動(dòng)態(tài)規(guī)劃的方法解決。在codewars上做了一道斐波那契數(shù)列求和的題目，做完之后做了一些簡單的優(yōu)化和用另一種方法實(shí)現(xiàn)。題目 function fibonacci(n) { if(n==0 || n == 1) r...

xinhaip 2019-08-20 11:35 評論0 收藏0
js 實(shí)現(xiàn)斐波那契數(shù)列(數(shù)組緩存、動(dòng)態(tài)規(guī)劃、尾調(diào)用優(yōu)化)

摘要：根據(jù)該規(guī)則，返回第個(gè)斐波那契數(shù)。尾遞歸函數(shù)調(diào)用自身，稱為遞歸。一個(gè)前端眼中的斐波那契數(shù)列解斐波那契數(shù)列的實(shí)用解法調(diào)用棧尾遞歸和手動(dòng)優(yōu)化尾調(diào)用優(yōu)化譯我從用寫斐波那契生成器中學(xué)到的令人驚訝的件事斐波那契數(shù)列是以下一系列數(shù)字： 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, ... 在種子數(shù)字 0 和 1 ...

趙連江 2019-08-23 11:38 評論0 收藏0
JavaScript解斐波那契(Fibonacci)數(shù)列的實(shí)用解法

摘要：下面是一個(gè)可以處理很多類型遞歸函數(shù)的函數(shù)其中第一個(gè)參數(shù)為原有函數(shù)，第二個(gè)參數(shù)為緩存對象，是可選參數(shù)因?yàn)椴⒉皇撬羞f歸函數(shù)都包含初始信息。首先將緩存對象的類型從數(shù)組轉(zhuǎn)換為對象，這樣就可以適用于那些不是返回整數(shù)的遞歸函數(shù)。 JavaScript解斐波那契(Fibonacci)數(shù)列的實(shí)用解法我們經(jīng)常會(huì)在面試題中看到如下題目：輸入n，求斐波那契數(shù)列的第n項(xiàng)，斐波那契數(shù)列的定義如下： F(0)...

zhongmeizhi 2019-08-20 14:50 評論0 收藏0
【刷算法】斐波那契數(shù)列

摘要：題目現(xiàn)在要求輸入一個(gè)整數(shù)，請你輸出斐波那契數(shù)列的第項(xiàng)。遞歸操作時(shí)間復(fù)雜度太高，而且用遞歸會(huì)產(chǎn)生很多重復(fù)的操作。非遞歸操作這種方法就是一次遍歷過去就行，計(jì)算第個(gè)數(shù)時(shí)，使用了兩個(gè)變量存儲第和第個(gè)數(shù)，使時(shí)間復(fù)雜度降低到題目現(xiàn)在要求輸入一個(gè)整數(shù)n，請你輸出斐波那契數(shù)列的第n項(xiàng)。遞歸操作O(2^n) function fibonacci(n) { if(n < 1) ...

IamDLY 2019-08-22 18:09 評論0 收藏0
JS專題之memoization

摘要：前言在計(jì)算機(jī)領(lǐng)域，記憶是主要用于加速程序計(jì)算的一種優(yōu)化技術(shù)，它使得函數(shù)避免重復(fù)演算之前已被處理過的輸入，而返回已緩存的結(jié)果。被執(zhí)行了不是素?cái)?shù)，其他數(shù)字默認(rèn)是素?cái)?shù)。我們可以看出，如果從開始打印斐波那契數(shù)列，函數(shù)被執(zhí)行了次。前言在計(jì)算機(jī)領(lǐng)域，記憶（memoization）是主要用于加速程序計(jì)算的一種優(yōu)化技術(shù)，它使得函數(shù)避免重復(fù)演算之前已被處理過的輸入，而返回已緩存的結(jié)果。 -- wi...

zhisheng 2019-08-23 15:08 評論0 收藏0