NO8---蓝桥杯JAVA--- 斐波那契升级版

本文主要是介绍NO8---蓝桥杯JAVA--- 斐波那契升级版，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

斐波那契数列大家都非常熟悉。它的定义是：

f(x)=1....(x=1,2)

f(x)=f(x−1)+f(x−2)....(x>2)

对于给定的整数 n和 m，我们希望求出：

f(1)+f(2)+…+f(n)的值。

但这个值可能非常大，所以我们把它对 f(m) 取模。

但这个数字依然很大，所以需要再对 p 求模。

输入格式

输入包含多组数据。

每组数据占一行，包含三个整数 n,m,p。

输出格式

每组数据输出一个整数，表示答案。

每个数占一行。

数据范围

0<n,m,p<1018
测试数据不超过100组

输入样例1：

2 3 5

输出样例1：

0

import java.util.Scanner;public class Main {public static int n;public static int m;public static int p;public static int te;public static  int fei(int i) {if(i==1)return 1;else if(i==2)return 1;else if(i==0)return 0;else return fei(i-1)+fei(i-2);}public static void prin(int n,int m,int p) {int sum=0;for(int j=1;j<=n;j++) {sum+=fei(j);}te=fei(m);sum=sum%te;sum=sum%te;sum=sum%p;System.out.print(sum+"\n");}public static void main(String[] args) {Scanner sc=new Scanner(System.in);String ss=sc.nextLine();while(ss != null) {String[] words = ss.split(" ");n=Integer.valueOf(words[0]);m=Integer.valueOf(words[1]);p=Integer.valueOf(words[2]);prin(n,m,p);ss=sc.nextLine();}sc.close();}
}

我觉得重要的是连续输入3个一组的数据的处理

下面是一个例子

24 6 13 
26 6 13
24 3 17
26 3 17
25 3 19
25 6 137
288 48 3157
288 46 8947
288 47 9748
288 9 3157
232135 12896 91547
1081143 31797 31479
4567872 123456 654321
4567874 123456 654321

这时候就要用字符串分割

另外我的方法超时了

下面是大佬的方法

public class _斐波那契 {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt();int m = sc.nextInt();int p = sc.nextInt();BigInteger fb_res = new BigInteger("0");BigInteger m_res = new BigInteger(m+"");BigInteger tmp = new BigInteger("0");BigInteger P = new BigInteger(p+"");for (int i = 1; i <= n; i++) {tmp = fbn(i);fb_res = fb_res.add(tmp);}m_res = fbn(m);BigInteger res = fb_res.mod(m_res).mod(P);System.out.println(res);}public static BigInteger fbn(int n) {BigInteger one = new BigInteger("1");BigInteger zero = new BigInteger("0");BigInteger[] dp = new BigInteger[(n + 1)];dp[0] = zero;dp[1] = one;for (int i = 2; i < n + 1; i++) {dp[i] = dp[i - 1].add(dp[i - 2]);}return dp[n];}
}作者：caij2033
链接：https://www.acwing.com/solution/content/34261/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

有点子动态规划的样子在了

另外用BigInteger是我没想到的

BigInteger详解

这篇关于NO8---蓝桥杯JAVA--- 斐波那契升级版的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---