Java实现Fibonacci(斐波那契)取余的示例代码

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

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

Input
多组测试数据

输入包含一个整数n。1 <= n <= 1,000,000。

Output
每组输出一行，包含一个整数，表示Fn除以10007的余数。

Sample Input
10
22

Sample Output
55
7704

利用余数三大定理：

1.余数的加法定理

a与b的和除以c的余数，等于a,b分别除以c的余数之和，或这个和除以c的余数。

即：(a+b)%c = (a%c+b%c)%c

例如：23，16除以5的余数分别是3和1，所以23+16=39除以5的余数等于4，即两个余数的和3+1.

当余数的和比除数大时，所求的余数等于余数之和再除以c的余数。

例如：23，19除以5的余数分别是3和4，故23+19=42除以5的余数等于3+4=7除以5的余数，即2.

2.余数的乘法定理

a与b的乘积除以c的余数，等于a,b分别除以c的余数的积，或者这个积除以c所得的余数。

即：(a*b)%c = (a%c*b%c)%c

例如：23，16除以5的余数分别是3和1，所以23×16除以5的余数等于3×1=3。

当余数的和比除数大时，所求的余数等于余数之积再除以c的余数。

例如：23，19除以5的余数分别是3和4，所以23×19除以5的余数等于3×4除以5的余数，即2.

3.同余定理

若两个整数a、b被自然数m除有相同的余数，那么称a、b对于模m同余，用式子表示为：a≡b ( mod m )，左边的式子叫做同余式。

同余式读作：a同余于b，模m。由同余的性质，我们可以得到一个非常重要的推论：

若两个数a，b除以同一个数m得到的余数相同，则a，b的差一定能被m整除

用式子表示为：如果有a≡b ( mod m )，那么一定有a－b＝mk,k是整数，即m|(a－b)

那么：如果有mk%m=0，b%m=0,就有（mk+b）%m

package 第八次模拟;

import java.util.Scanner;
public class Demo12Fibonacci {
public static void main(String[] args) {
 Scanner sc = new Scanner(System.in);
 while(sc.hasNext()){

 int n = sc.nextInt();
 int []f = new int [n+2];
 int [] count=new int [n+2];
 f[1]=1;
 f[2]=1;
 for (int i = 3; i <=n; i++) {
 f[i]=(f[i-1]+f[i-2]);
 if(f[i]/10007>=1){
 f[i]%=10007;
 }

 }
 System.out.println(f[n]);

 }
 }
}

到此这篇关于Java实现Fibonacci取余的示例代码的文章就介绍到这了,更多相关Java Fibonacci取余内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！

赞 (0)

相关推荐

  • Java中的相除（/）和取余（%）的实现方法

    取模运算与取余运算两个概念有重叠的部分但又不完全一致.主要的区别在于对负整数进行除法运算时操作不同. 对于整形数a,b来说,取模运算或者求余运算的方法都是: 1.求 整数商 c = a / b: 2.计算模或者余数 r = a - c* b . 取模运算和取余运算在第一步不同: 取余运算在取c值时,向0方向舍入:而取模运算在取c值时,是向负无穷方向舍入 各个环境下运算符%的含义不同,C/C++,Java为取余,python为取模 Java取余运算规则如下: a%b = a - (a/b)*b 让

  • Java别说取余（%）运算简单你真的会吗

    一,直击现场 下面我来抛出几道题: 说明m是商,n是余数: (1)正数%正数 3%2=m--.n 2%3=m--.n (2)正数%负数或者负数%正数 -3%2=m--.n 3%-2=m--.n -2%3=m--.n 2%-3=m--.n (3)负数%负数 -3%-2=m--.n -2%-3=m--.n 二,验证时刻 下面的结果没有商m只有余数n;有没有全部答对呢?没有的话来看总结吧 三,总结 (1) 3%2=1--.1 2%3=0--.1 正数除以正数: 商正余正 (2) -3%2=-1--.-

  • Java实现Fibonacci(斐波那契)取余的示例代码

    Description Fibonacci数列的递推公式为:Fn=Fn-1+Fn-2,其中F1=F2=1. 当n比较大时,Fn也非常大,现在我们想知道,Fn除以10007的余数是多少. Input 多组测试数据 输入包含一个整数n.1 <= n <= 1,000,000. Output 每组输出一行,包含一个整数,表示Fn除以10007的余数. Sample Input 10 22 Sample Output 55 7704 利用余数三大定理: 1.余数的加法定理 a与b的和除以c的余数,等于

  • C语言求Fibonacci斐波那契数列通项问题的解法总结

    C语言求Fibonacci斐波那契数列通项问题的解法总结

    一:递归实现   使用公式f[n]=f[n-1]+f[n-2],依次递归计算,递归结束条件是f[1]=1,f[2]=1. 二:数组实现   空间复杂度和时间复杂度都是0(n),效率一般,比递归来得快. 三:vector<int>实现   时间复杂度是0(n),时间复杂度是0(1),就是不知道vector的效率高不高,当然vector有自己的属性会占用资源. 四:queue<int>实现   当然队列比数组更适合实现斐波那契数列,时间复杂度和空间复杂度和vector<int&g

  • Java递归实现斐波那契数列

    程序调用自身的编程技巧称为递归( recursion).递归做为一种算法在程序设计语言中广泛应用. 一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法,它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解,递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算,大大地减少了程序的代码量.递归的能力在于用有限的语句来定义对象的无限集合.一般来说,递归需要有边界条件.递归前进段和递归返回段.当边界条件不满足时,递归前进:当边界条件满足时,递归返回.--这是百度百

  • python实现斐波那契数列的方法示例

    python实现斐波那契数列的方法示例

    介绍 斐波那契数列,又称黄金分割数列,指的是这样一个数列:0.1.1.2.3.5.8.13.21.--在数学上,斐波纳契数列以如下递归的方法定义: F(0)=0,F(1)=1,F(n)=F(n-1)+F(n-2)(n≥2,n∈N*) . 1. 元组实现 fibs = [0, 1] for i in range(8): fibs.append(fibs[-2] + fibs[-1]) 这能得到一个在指定范围内的斐波那契数列的列表. 2. 迭代器实现 class Fibs: def __init__

  • JAVA递归与非递归实现斐波那契数列

    斐波那契数列(Fibonacci sequence),又称黄金分割数列.因数学家列昂纳多·斐波那契(Leonardoda Fibonacci[1] )以兔子繁殖为例子而引入,故又称为"兔子数列",指的是这样一个数列:0.1.1.2.3.5.8.13.21.34.--在数学上,斐波纳契数列以如下被以递归的方法定义:F(0)=0,F(1)=1,F(n)=F(n-1)+F(n-2)(n≥2,n∈N*)在现代物理.准晶体结构.化学等领域,斐波纳契数列都有直接的应用,为此,美国数学会从1963起

  • 用Python实现斐波那契（Fibonacci）函数

    Fibonacci斐波那契数列,很简单,就是一个递归嘛,学任何编程语言可能都会做一下这个. 最近在玩Python,在粗略的看了一下Learning Python和Core Python之后,偶然发现网上有个帖子Python程序员的进化写的很有意思.于是打算仿照一篇,那篇帖子用了十余种方法完成一个阶乘函数,我在这里会用九种不同的风格写出一个Fibonacci函数. 要求很简单,输入n,输出第n个Fibonacci数,n为正整数 下面是这九种不同的风格: 1)第一次写程序的Python程序员: de

  • 递归之斐波那契数列java的3种方法

    本文实例为大家分享了java递归之斐波那契数列的具体代码,供大家参考,具体内容如下 第一种.普通写法 public class Demo { public static void main(String[] args) { int num1 = 1; int num2 = 1; int num3 = 0; System.out.println(num1); System.out.println(num2); for (int i = 1; i < 10; i++) { num3 = num1 +

  • 剑指Offer之Java算法习题精讲二叉树与斐波那契函数

    剑指Offer之Java算法习题精讲二叉树与斐波那契函数

    题目一 解法 class Solution { public int fib(int n) { int[] arr = new int[31]; arr[0] = 0; arr[1] = 1; for(int i = 2;i<=n;i++){ arr[i] = arr[i-2]+arr[i-1]; } return arr[n]; } } 题目二  解法 /** * Definition for a binary tree node. * public class TreeNode { * in

  • Java实现查找算法的示例代码(二分查找、插值查找、斐波那契查找)

    Java实现查找算法的示例代码(二分查找、插值查找、斐波那契查找)

    目录 1.查找概述 2.顺序查找 3.二分查找 3.1 二分查找概述 3.2 二分查找实现 4.插值查找 4.1 插值查找概述 4.2 插值查找实现 5.斐波那契查找 5.1 斐波那契查找概述 5.2 斐波那契查找实现 5.3 总结 1.查找概述 查找表: 所有需要被查的数据所在的集合,我们给它一个统称叫查找表.查找表(Search Table)是由同一类型的数据元素(或记录)构成的集合. 查找(Searching): 根据给定的某个值,在查找表中确定一个其关键字等于给定值的数据元素(或记录).

  • java编程经典案例之基于斐波那契数列解决兔子问题实例

    java编程经典案例之基于斐波那契数列解决兔子问题实例

    本文实例讲述了java基于斐波那契数列解决兔子问题.分享给大家供大家参考,具体如下: 题目:古典问题:有一对兔子,从出生后第3个月起每个月都生一对兔子,小兔子长到第三个月后每个月又生一对兔子,假如兔子都不死,问每个月的兔子总数为多少? package com.java.recursion; /** * @描述 三种方法实现斐波那契数列 * @项目名称 Java_DataStruct * @包名 com.java.recursion * @类名 Fibonacci * @author chenli

随机推荐