• 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 测试数据不超过100组

    输入样例1:
    2 3 5
    
    输出样例1:
    0
    1. import java.util.Scanner;
    2. public class Main {
    3. public static int n;
    4. public static int m;
    5. public static int p;
    6. public static int te;
    7. public static int fei(int i) {
    8. if(i==1)return 1;
    9. else if(i==2)return 1;
    10. else if(i==0)return 0;
    11. else return fei(i-1)+fei(i-2);
    12. }
    13. public static void prin(int n,int m,int p) {
    14. int sum=0;
    15. for(int j=1;j<=n;j++) {
    16. sum+=fei(j);
    17. }
    18. te=fei(m);
    19. sum=sum%te;
    20. sum=sum%te;
    21. sum=sum%p;
    22. System.out.print(sum+"\n");
    23. }
    24. public static void main(String[] args) {
    25. Scanner sc=new Scanner(System.in);
    26. String ss=sc.nextLine();
    27. while(ss != null) {
    28. String[] words = ss.split(" ");
    29. n=Integer.valueOf(words[0]);
    30. m=Integer.valueOf(words[1]);
    31. p=Integer.valueOf(words[2]);
    32. prin(n,m,p);
    33. ss=sc.nextLine();
    34. }
    35. sc.close();
    36. }
    37. }

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

    下面是一个例子

    1. 24 6 13
    2. 26 6 13
    3. 24 3 17
    4. 26 3 17
    5. 25 3 19
    6. 25 6 137
    7. 288 48 3157
    8. 288 46 8947
    9. 288 47 9748
    10. 288 9 3157
    11. 232135 12896 91547
    12. 1081143 31797 31479
    13. 4567872 123456 654321
    14. 4567874 123456 654321

    这时候就要用字符串分割

    另外我的方法超时了

    下面是大佬的方法

    1. public class _斐波那契 {
    2. public static void main(String[] args) {
    3. Scanner sc = new Scanner(System.in);
    4. int n = sc.nextInt();
    5. int m = sc.nextInt();
    6. int p = sc.nextInt();
    7. BigInteger fb_res = new BigInteger("0");
    8. BigInteger m_res = new BigInteger(m+"");
    9. BigInteger tmp = new BigInteger("0");
    10. BigInteger P = new BigInteger(p+"");
    11. for (int i = 1; i <= n; i++) {
    12. tmp = fbn(i);
    13. fb_res = fb_res.add(tmp);
    14. }
    15. m_res = fbn(m);
    16. BigInteger res = fb_res.mod(m_res).mod(P);
    17. System.out.println(res);
    18. }
    19. public static BigInteger fbn(int n) {
    20. BigInteger one = new BigInteger("1");
    21. BigInteger zero = new BigInteger("0");
    22. BigInteger[] dp = new BigInteger[(n + 1)];
    23. dp[0] = zero;
    24. dp[1] = one;
    25. for (int i = 2; i < n + 1; i++) {
    26. dp[i] = dp[i - 1].add(dp[i - 2]);
    27. }
    28. return dp[n];
    29. }
    30. }
    31. 作者:caij2033
    32. 链接:https://www.acwing.com/solution/content/34261/
    33. 来源:AcWing
    34. 著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

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

    另外用BigInteger是我没想到的

    BigInteger详解

  • 相关阅读:
    Git -- submoudule子模块使用
    [动态规划] (十) 路径问题 LeetCode 174.地下城游戏
    【LoRaWAN节点应用】安信可Ra-08/Ra-08H模组入网LoRaWAN网络的应用及功耗情况
    iOS全埋点解决方案-控件点击事件
    【1608. 特殊数组的特征值】
    PMP真的有用吗?
    基于bootstarp-table实现列固定
    【飞桨PaddleSpeech语音技术课程】— 声纹检索系统与实践
    GBase 8a的SNMP Trap 告警
    android 中Handle弱引用使用
  • 原文地址:https://blog.csdn.net/2202_75787160/article/details/134518823