Fibonacci數(shù)列的遞推公式：Fn=Fn-1 + Fn-2，其中F1=F2=1

SimonMa 發(fā)布于2019-08-23 16:18 / 2036人閱讀

摘要：問題描述數(shù)列的遞推公式為，其中。當(dāng)比較大時，也非常大，現(xiàn)在我們想知道，除以的余數(shù)是多少。輸出格式輸出一行，包含一個整數(shù)，表示除以的余數(shù)。樣例輸入樣例輸出樣例輸入樣例輸出語言實現(xiàn)或者實現(xiàn)斐波那契的遞歸函數(shù)

問題描述

Fibonacci數(shù)列的遞推公式為：Fn=Fn-1+Fn-2，其中F1=F2=1。

當(dāng)n比較大時，F(xiàn)n也非常大，現(xiàn)在我們想知道，F(xiàn)n除以10007的余數(shù)是多少。

輸入格式

輸入包含一個整數(shù)n。

輸出格式

輸出一行，包含一個整數(shù)，表示Fn除以10007的余數(shù)。
說明：在本題中，答案是要求Fn除以10007的余數(shù)，因此我們只要能算出這個余數(shù)即可，而不需要先計算出Fn的準(zhǔn)確值，再將計算的結(jié)果除以10007取余數(shù)，直接計算余數(shù)往往比先算出原數(shù)再取余簡單。

樣例輸入

樣例輸出

樣例輸入

樣例輸出

7704

C語言實現(xiàn)

int Fbi(int i)
{
    if(i<2)
        return i==0 ? 0:1;
    return Fbi(i-1) + Fbi(i-2);
}

int main()
{
 int i,j;
 scanf("%d",&i);
 j = Fbi(i) % 10007;
     printf("%d
",j);
 return 0;
}

或者

#include 
#include 
#define MOD 10007
#define MAXN 1000001
int n, i, F[MAXN];
int main()
{
    scanf("%d", &n);
    F[1] = 1;
    F[2] = 1;
    for (i = 3; i <= n; ++i)
        F[i] = (F[i-1] + F[i-2]) % MOD;
    printf("%d
", F[n]);
    return 0;
}

JS實現(xiàn)

//斐波那契的遞歸函數(shù)
function Fbi(i) {
var i;
if(i<2){
   return i == 0 ? 0 : 1;
} else {
return Fbi(i-1) + Fbi(i-2); 
 }
}

var n=prompt(n);
var j;
j = Fbi(n) % 10007;
console.log(j);

GPU云服務(wù)器云服務(wù)器 fibonacci數(shù)列支配點遞推關(guān)系 f2c域名 Fibonacci

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

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

相關(guān)文章

JS專題之memoization

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

zhisheng 2019-08-23 15:08 評論0 收藏0
使用js實現(xiàn)斐波那契數(shù)列

摘要：前言前幾天面試被問到了斐波那契數(shù)列的實現(xiàn)以及優(yōu)化的問題，當(dāng)時現(xiàn)場卡了挺久的，現(xiàn)在進行一下總結(jié)使用實現(xiàn)。題目介紹斐波那契數(shù)列又被稱為黃金分割數(shù)列，指的是這樣的一個數(shù)列，它有如下遞推的方法定義是正整數(shù)，請使用實現(xiàn)斐波那契函數(shù)。前言前幾天面試被問到了斐波那契數(shù)列的實現(xiàn)以及優(yōu)化的問題，當(dāng)時現(xiàn)場卡了挺久的，現(xiàn)在進行一下總結(jié)（使用js實現(xiàn)）。題目介紹 ??斐波那契數(shù)列又被稱為黃金分割數(shù)列，指...

alexnevsky 2019-08-26 13:36 評論0 收藏0
斐波那契數(shù)列（求fibonacci的第N項的值）

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

Fundebug 2019-08-16 12:35 評論0 收藏0
【Algorithm · fourth edition】均值、方差的遞推公式

摘要：來源算法第四版當(dāng)向累加器中新加入一個時，不需要和原來的一起重新算一遍均值和方差，而是可以根據(jù)之前已經(jīng)算出來的均值和方差，利用遞推公式直接得到新的結(jié)果，這里就關(guān)注這個遞推公式推導(dǎo)過程來源：《算法·第四版》1.2 Data AbstractionCreative Problems · 1.2.18Source Code: /** * Adds the specified data va...

MrZONT 2019-08-16 18:34 評論0 收藏0
Generator 詳解（使用場景，babel 轉(zhuǎn)譯，協(xié)程，異步，上層應(yīng)用，async/await）

摘要：不需要多線程的鎖機制線程由系統(tǒng)控制切換，協(xié)程是由用戶控制切換。協(xié)程的中斷實際上是掛起的概念協(xié)程發(fā)起異步操作意味著該協(xié)程將會被掛起，為了保證喚醒時能正常運行，需要正確保存并恢復(fù)其運行時的上下文。博客 github 地址： https://github.com/HCThink/h-blog/blob/master/js/syncAndAsync/generator/readme.md ...

raise_yang 2019-08-23 14:03 評論0 收藏0