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

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

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

問(wèn)題描述

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

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

輸入格式

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

輸出格式

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

樣例輸入

樣例輸出

樣例輸入

樣例輸出

7704

C語(yǔ)言實(shí)現(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實(shí)現(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);

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

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

轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/102877.html

相關(guān)文章

JS專題之memoization

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

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

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

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

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

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

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

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

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

raise_yang 2019-08-23 14:03 評(píng)論0 收藏0