Fibonacci数列的递推公式：Fn=Fn-1 + Fn-2，其中F1=F2=1

SimonMa 发布于2019-08-23 16:18 / 1934人阅读

摘要：问题描述数列的递推公式为，其中。当比较大时，也非常大，现在我们想知道，除以的余数是多少。输出格式输出一行，包含一个整数，表示除以的余数。样例输入样例输出样例输入样例输出语言实现或者实现斐波那契的递归函数

问题描述

Fibonacci数列的递推公式为：Fn=Fn-1+Fn-2，其中F1=F2=1。

当n比较大时，Fn也非常大，现在我们想知道，Fn除以10007的余数是多少。

输入格式

输入包含一个整数n。

输出格式

输出一行，包含一个整数，表示Fn除以10007的余数。
说明：在本题中，答案是要求Fn除以10007的余数，因此我们只要能算出这个余数即可，而不需要先计算出Fn的准确值，再将计算的结果除以10007取余数，直接计算余数往往比先算出原数再取余简单。

样例输入

样例输出

样例输入

样例输出

7704

C语言实现

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实现

//斐波那契的递归函数
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云服务器云服务器 fibonacci数列支配点递推关系 f2c域名 Fibonacci

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/102877.html

JS专题之memoization

摘要：前言在计算机领域，记忆是主要用于加速程序计算的一种优化技术，它使得函数避免重复演算之前已被处理过的输入，而返回已缓存的结果。被执行了不是素数，其他数字默认是素数。我们可以看出，如果从开始打印斐波那契数列，函数被执行了次。前言在计算机领域，记忆（memoization）是主要用于加速程序计算的一种优化技术，它使得函数避免重复演算之前已被处理过的输入，而返回已缓存的结果。 -- wi...

zhisheng 2019-08-23 15:08 评论0 收藏0
使用js实现斐波那契数列

摘要：前言前几天面试被问到了斐波那契数列的实现以及优化的问题，当时现场卡了挺久的，现在进行一下总结使用实现。题目介绍斐波那契数列又被称为黄金分割数列，指的是这样的一个数列，它有如下递推的方法定义是正整数，请使用实现斐波那契函数。前言前几天面试被问到了斐波那契数列的实现以及优化的问题，当时现场卡了挺久的，现在进行一下总结（使用js实现）。题目介绍斐波那契数列又被称为黄金分割数列，指...

alexnevsky 2019-08-26 13:36 评论0 收藏0
斐波那契数列（求fibonacci的第N项的值）

摘要：今天在公司实习，实在没啥活是我能干的，就想着写一写算法打发时间，正好看到了斐波那契数列，搞起。这是斐波那契数列的通项公式以前用递归写过，今天看的时候书上说递归虽然简单，但其实内部做了很多重复的计算，而且尾递归都是可以用循环解决的。今天在公司实习，实在没啥活是我能干的，就想着写一写算法打发时间，正好看到了斐波那契数列，搞起。这是斐波那契数列的通项公式：showImg(https://...

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

摘要：来源算法第四版当向累加器中新加入一个时，不需要和原来的一起重新算一遍均值和方差，而是可以根据之前已经算出来的均值和方差，利用递推公式直接得到新的结果，这里就关注这个递推公式推导过程来源：《算法·第四版》1.2 Data AbstractionCreative Problems · 1.2.18Source Code: /** * Adds the specified data va...

MrZONT 2019-08-16 18:34 评论0 收藏0
Generator 详解（使用场景，babel 转译，协程，异步，上层应用，async/await）

摘要：不需要多线程的锁机制线程由系统控制切换，协程是由用户控制切换。协程的中断实际上是挂起的概念协程发起异步操作意味着该协程将会被挂起，为了保证唤醒时能正常运行，需要正确保存并恢复其运行时的上下文。博客 github 地址： https://github.com/HCThink/h-blog/blob/master/js/syncAndAsync/generator/readme.md ...

raise_yang 2019-08-23 14:03 评论0 收藏0