算法笔记_091:蓝桥杯练习 递推求值(Java)

时间:2023-02-13 18:22:14

目录

1 问题描述

2 解决方案

 


1 问题描述

问题描述
  已知递推公式:

  F(n, 1)=F(n-1, 2) + 2F(n-3, 1) + 5,

  F(n, 2)=F(n-1, 1) + 3F(n-3, 1) + 2F(n-3, 2) + 3.

  初始值为:F(1, 1)=2, F(1, 2)=3, F(2, 1)=1, F(2, 2)=4, F(3, 1)=6, F(3, 2)=5。
  输入n,输出F(n, 1)和F(n, 2),由于答案可能很大,你只需要输出答案除以99999999的余数。
输入格式
  输入第一行包含一个整数n。
输出格式
  输出两行,第一行为F(n, 1)除以99999999的余数,第二行为F(n, 2)除以99999999的余数。
样例输入
4
样例输出
14

21
数据规模和约定
  1<=n<=10^18。

 


2 解决方案

本题直接用传统的递推求解,结果会运行超时。

此处要利用要构造矩阵,来计算相应结果。

首先看一下参考资料1中对于斐波那契数,构造矩阵的示例:

 算法笔记_091:蓝桥杯练习 递推求值(Java)

其具体相关理解,请参考文末参考资料1哦。

本题构造的矩阵如下:

对应1*8的矩阵为[f(3,1),f(3,2),f(2,1),(2,2),f(1,1),f(1,2),3,5]

public final static long[][] UNIT = {{0,1,1,0,0,0,0,0},
        {1,0,0,1,0,0,0,0},
        {0,0,0,0,1,0,0,0},
        {0,0,0,0,0,1,0,0},
        {2,3,0,0,0,0,0,0},
        {0,2,0,0,0,0,0,0},
        {0,1,0,0,0,0,1,0},
        {1,0,0,0,0,0,0,1}};   //根据递推公式构造的矩阵

 算法笔记_091:蓝桥杯练习 递推求值(Java)

具体代码如下:

import java.util.Scanner;

public class Main {
    public final static long[][] UNIT = {{0,1,1,0,0,0,0,0},
        {1,0,0,1,0,0,0,0},
        {0,0,0,0,1,0,0,0},
        {0,0,0,0,0,1,0,0},
        {2,3,0,0,0,0,0,0},
        {0,2,0,0,0,0,0,0},
        {0,1,0,0,0,0,1,0},
        {1,0,0,0,0,0,0,1}};   //根据递推公式构造的矩阵
    public final static long[][] ZERO = new long[8][8];  //元素全为0
    public final static long p = 99999999L;
    //获取矩阵NUIT的n次方结果
    public long[][] getNofMatrix(long n) {
        if(n == 0)
            return ZERO;
        if(n == 1)
            return UNIT;
        if((n & 1) == 0) {  //当n为偶数时
            long[][] matrix = getNofMatrix( n >> 1);
            return multiOfMatrix(matrix, matrix);
        } 
        //当n为奇数时
        long[][] matrix = getNofMatrix((n - 1) >> 1);
        return multiOfMatrix(multiOfMatrix(matrix, matrix), UNIT);
    }
    //计算矩阵A*B取余99999999的值
    public long[][] multiOfMatrix(long[][] A, long[][] B) {
        long result[][] = new long[A.length][B[0].length];
        for(int i = 0;i < A.length;i++) {
            for(int j = 0;j < B[0].length;j++) {
                for(int k = 0;k < A[0].length;k++)
                    result[i][j] = (result[i][j] + A[i][k] * B[k][j]) % p;
            }
        }
        return result;
    }
    
    public void printResult(long n) {
        long[][] start = {{6,5,1,4,2,3,3,5}};
        if(n == 1) {
            System.out.println(start[0][4]+"\n"+start[0][5]);
            return;
        } else if(n == 2) {
            System.out.println(start[0][2]+"\n"+start[0][3]);
            return;
        } else if(n == 3) {
            System.out.println(start[0][0]+"\n"+start[0][1]);
            return;
        }
        long[][] A = getNofMatrix(n - 3);
        start = multiOfMatrix(start, A);
        System.out.println(start[0][0]+"\n"+start[0][1]);
        return;
    }
    
    public static  void main(String[] args) {
        Main test = new Main();
        Scanner in = new Scanner(System.in);
        long n = in.nextLong();
        test.printResult(n);
    }
}

 

 

 

参考资料:

1.矩阵构造方法

2.蓝桥杯算法提高 递推求值 【矩阵快速幂】