Java實(shí)現(xiàn)Fibonacci(斐波那契)取余的示例代碼
Description
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ù)是多少。
Input
多組測(cè)試數(shù)據(jù)
輸入包含一個(gè)整數(shù)n。1 <= n <= 1,000,000。
Output
每組輸出一行，包含一個(gè)整數(shù)，表示Fn除以10007的余數(shù)。
Sample Input
10
22
Sample Output
55
7704
利用余數(shù)三大定理：
1.余數(shù)的加法定理
a與b的和除以c的余數(shù)，等于a,b分別除以c的余數(shù)之和，或這個(gè)和除以c的余數(shù)。
即：(a+b)%c = (a%c+b%c)%c
例如：23，16除以5的余數(shù)分別是3和1，所以23+16=39除以5的余數(shù)等于4，即兩個(gè)余數(shù)的和3+1.
當(dāng)余數(shù)的和比除數(shù)大時(shí)，所求的余數(shù)等于余數(shù)之和再除以c的余數(shù)。
例如：23，19除以5的余數(shù)分別是3和4，故23+19=42除以5的余數(shù)等于3+4=7除以5的余數(shù)，即2.
2.余數(shù)的乘法定理
a與b的乘積除以c的余數(shù)，等于a,b分別除以c的余數(shù)的積，或者這個(gè)積除以c所得的余數(shù)。
即：(a*b)%c = (a%c*b%c)%c
例如：23，16除以5的余數(shù)分別是3和1，所以23×16除以5的余數(shù)等于3×1=3。
當(dāng)余數(shù)的和比除數(shù)大時(shí)，所求的余數(shù)等于余數(shù)之積再除以c的余數(shù)。
例如：23，19除以5的余數(shù)分別是3和4，所以23×19除以5的余數(shù)等于3×4除以5的余數(shù)，即2.
3.同余定理
若兩個(gè)整數(shù)a、b被自然數(shù)m除有相同的余數(shù)，那么稱a、b對(duì)于模m同余，用式子表示為：a≡b ( mod m )，左邊的式子叫做同余式。
同余式讀作：a同余于b，模m。由同余的性質(zhì)，我們可以得到一個(gè)非常重要的推論：
若兩個(gè)數(shù)a，b除以同一個(gè)數(shù)m得到的余數(shù)相同，則a，b的差一定能被m整除
用式子表示為：如果有a≡b ( mod m )，那么一定有a－b＝mk,k是整數(shù)，即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]);
}
}
}
到此這篇關(guān)于Java實(shí)現(xiàn)Fibonacci取余的示例代碼的文章就介紹到這了,更多相關(guān)Java Fibonacci取余內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
這篇文章主要給大家介紹了關(guān)于如何使用Java靈活讀取Excel內(nèi)容的相關(guān)資料,讀取Excel數(shù)據(jù)是Java開(kāi)發(fā)中常見(jiàn)的任務(wù),文中通過(guò)代碼示例介紹的非常詳細(xì),需要的朋友可以參考下2023-09-09
SpringBoot使用hutool操作FTP的詳細(xì)過(guò)程
在使用SpringBoot結(jié)合hutool操作FTP時(shí),遇到防火墻導(dǎo)致上傳文件大小為0kb的問(wèn)題,通過(guò)設(shè)置FTP為被動(dòng)模式解決,本文詳細(xì)解析了FTP的主動(dòng)模式和被動(dòng)模式的工作原理、安全性及適用場(chǎng)景,幫助理解FTP的連接方式和解決網(wǎng)絡(luò)限制問(wèn)題2024-09-09
這篇文章主要為大家詳細(xì)介紹了java圖形用戶界面實(shí)現(xiàn)菜單功能，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2018-05-05
這篇文章主要介紹了java中使用url進(jìn)行編碼和解碼，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教2022-08-08
解決Idea查看源代碼警告Library source does not mat
在使用IDEA開(kāi)發(fā)時(shí),遇到第三方j(luò)ar包中的源代碼和字節(jié)碼不一致的問(wèn)題,會(huì)導(dǎo)致無(wú)法正確打斷點(diǎn)進(jìn)行調(diào)試,這通常是因?yàn)閖ar包更新后源代碼沒(méi)有同步更新造成的,解決方法是刪除舊的jar包,通過(guò)Maven重新下載或手動(dòng)下載最新的源代碼包,確保IDE中的源碼與字節(jié)碼版本一致2024-10-10
這一次搞懂Spring自定義標(biāo)簽以及注解解析原理說(shuō)明
這篇文章主要介紹了這一次搞懂Spring自定義標(biāo)簽以及注解解析原理說(shuō)明，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。一起跟隨小編過(guò)來(lái)看看吧2020-08-08
這篇文章主要通過(guò)兩個(gè)例題為大家介紹一下Java合并兩個(gè)及以上有序鏈表的實(shí)現(xiàn)方法，文中的示例代碼講解詳細(xì)，具有一定的學(xué)習(xí)價(jià)值，需要的可以參考一下2023-04-04
Spring Data JPA使用JPQL與原生SQL進(jìn)行查詢的操作
這篇文章主要介紹了Spring Data JPA使用JPQL與原生SQL進(jìn)行查詢的操作，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教2021-06-06
SpringBoot熱部署和整合Mybatis的過(guò)程
熱部署,就是在應(yīng)用正在運(yùn)行的時(shí)候升級(jí)軟件,卻不需要重新啟動(dòng)應(yīng)用,本文給大家詳細(xì)介紹SpringBoot熱部署和整合Mybatis的過(guò)程,感興趣的朋友跟隨小編一起看看吧2023-10-10
Spring MVC學(xué)習(xí)教程之視圖深入解析
這篇文章主要給大家介紹了關(guān)于Spring MVC學(xué)習(xí)教程之視圖解析的相關(guān)資料，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家學(xué)習(xí)或使用spring mvc具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面來(lái)一起看看吧2018-11-11