斯巴达

用户名：AcmeGaga

访问量：1972

签　名：

等　　级
排　　名	5405
经　　验	1544
参赛次数	0
文章发表	22
年　　龄	0
在职情况	学生
学　　校	河南大学
专　　业

　　自我简介：

TA的其他文章

1697: 数据结构-二叉链表存储的二叉树
浏览：214

1592: 蓝桥杯算法训练VIP-FBI树
浏览：122

1744: 畅通工程代码搬运工(java)
浏览：152

你可能喜欢

1907: 蓝桥杯算法提高VIP-递推求值 java

　　作者: 斯巴达　　　　发表时间：2022-03-04 19:30:50 浏览：496　|　评论：1　

原题链接：蓝桥杯算法提高VIP-递推求值

- 思路
    
    观察F(n,1)与F(n,2)并没有发现什么明显的规律, 所以分开写F1, 与F2函数更合适
    
    得到代码如下:
    
    - 错误代码
        
        ```java
        import java.util.Scanner;
         
        public class Main {
            public static void main(String[] args) {
            	Scanner scan = new Scanner(System.in);
            	long n = scan.nextLong();
            	
            	System.out.println(F1(n));
            	System.out.println(F2(n));
            	scan.close();
            }
            public static long mod = 99999999;
            public static long F1(long n) {
            	if(n>3) return (F2(n-1)%mod + (2 * F1(n-3))%mod + 5)%mod;
            	else if(n==3) return 6L;
            	else if(n==2) return 1L;
            	else return 2L;
            }
            public static long F2(long n) {
            	if(n>3) return (F1(n-1)%mod + (3 * F1(n-3))%mod + (2 * F2(n-3))%mod + 3)%mod;
            	else if(n==3) return 5L;
            	else if(n==2) return 4L;
            	else return 3L;
            }
        }
        ```
        
    出现内存泄漏, 错因, 两个方法出现反复调用
    
    所以需要修改代码, 使之成为单方法循环调用, 或者双方法不互相调用
    
- 修正思路与代码
    
    依据矩阵的思路来处理此题
    
    ![https://blog.dotcpp.com/image_editor_upload/20200323011822_64845.png](https://blog.dotcpp.com/image_editor_upload/20200323011822_64845.png)
    
    - 思路描述
        
        观察这两个函数我们可以发现, 虽然两者互相调用, 但是他们的等式右边的系数是固定的. 
        
        当n>3时, 这两个函数会互相调用, 从而使对应位上的系数呈现出累成的显现. 
        
        这个规律, 发现跟矩阵快速幂十分吻合, 可以通过快速幂把多次调用的系数问题解决.
        
        当递归到n<3时就把对应的值带入计算即可
        
        ---
        
        这样只需要考虑递归矩阵ST的构造, 以及手动求出系数矩阵A 
        
        若令: $$a\_i = F(i,1), b\_i = F(i,2)$$ 则有
        
        $$a\_i = b\_{i-1}+ 2a\_{i-3} + 5,   b\_i = a\_{i-1}+ 3 a\_{i-3} + 2b\_{i-3} + 3$$
        
        考虑到i = 1, 2, 3时a, b为常数. 所以可以设置ST为$$[a\_i, b\_i,  a\_{i-1}, b\_{i-1}, a\_{i-2}, b\_{i-2}]$$
        
        又观察到$$a\_i = b\_{i-1}+ 2*a\_{i-3} + 5$$,  ST缺了个常数项, 这里用1来补充所以有
        
        ST为$$[a\_i, b\_i, a\_{i-1}, b\_{i-1}, a\_{i-2}, b\_{i-2}, 1]$$, 
        
        当$$ST\_{i+1}  =[a\_i, b\_i, a_{i\-1}, b\_{i-1}, a\_{i-2}, b\_{i-2}, 1] * A$$
        
        我们可以得出A, 
        
    - 代码
        
        ```java
        import java.util.Scanner;
        public class Main {
        	static final int mod=99999999;
        	static long num[]=new long[] {6,5,1,4,2,3,1};
        	static long n,ans1,ans2;
        	static class Matrix{
        		long mat[][]=new long[7][7];
        		Matrix multi(Matrix a) {       //矩阵乘法
        			Matrix rec=new Matrix();
        			for(int i=0;i<7;i++) {
        				for(int k=0;k<7;k++) {
        					if(this.mat[i][k]!=0) // this是指调用这个方法的Matrix型变量
        						for(int j=0;j<7;j++) {
        							rec.mat[i][j]=(rec.mat[i][j]+(this.mat[i][k]*a.mat[k][j])%mod)%mod;
        						}
        				}
        			}
        			return rec;
        		}
        	}
        	//ST表示该方阵，E表示单位矩阵（其地位相当于整数1）
        	static Matrix ST=new Matrix(),E=new Matrix();
        	static void init() {      //初始化
        		for(int i=0;i<7;i++)
        			E.mat[i][i]=1;
        		ST.mat[0][1]=1;ST.mat[0][4]=2;ST.mat[0][6]=5;
        		ST.mat[1][0]=1;ST.mat[1][4]=3;ST.mat[1][5]=2;ST.mat[1][6]=3;
        		ST.mat[2][0]=1;
        		ST.mat[3][1]=1;
        		ST.mat[4][2]=1;
        		ST.mat[5][3]=1;
        		ST.mat[6][6]=1;
        	}
        	static Matrix matrix_pow(long n) { //矩阵快速幂
        		Matrix rec=E,base=ST;
        		while(n!=0) {
        			if(n%2==1) {
        				rec=rec.multi(base);
        			}
        			base=base.multi(base);
        			n=n>>1;
        		}
        		return rec;
        	}
        	public static void main(String[] args) {
        		Scanner cin=new Scanner(System.in);
        		n=cin.nextLong();
        		if(n<4) {
        			int index=(int)(3-n)*2;
        			System.out.println(num[index]);
        			System.out.println(num[index+1]);
        		}else {
        			init();
        			ST=matrix_pow(n-3);
        			for(int i=0;i<7;i++) {
        				ans1=(ans1+(ST.mat[0][i]*num[i])%mod)%mod; //求F(n,1)
        				ans2=(ans2+(ST.mat[1][i]*num[i])%mod)%mod; //求F(n,2)
        			}
        			System.out.println(ans1);
        			System.out.println(ans2);
        		}
        	}
        }
        ```
		
        因为ST的顺序是 $$[a\_i, b\_i, a\_{i-1}, b\_{i-1}, a\_{i-2}, b\_{i-2}, 1]$$ , 所以num应该分别对应 $$[6, 5, 1, 4, 2,3,1]$$ , 这个1 是因为要乘以矩阵快速幂后的常数项, 不能影响常数项的变化所以是1.

------------

发现上面这些公式的格式格式不太对劲, 修改修改

------------
以上内容参考多方大佬:

[蓝桥杯算法提高VIP-递推求值 （C++代码）-Dotcpp编程社区](https://blog.dotcpp.com/a/10594)

[根据递推公式构造系数矩阵用于快速幂_RBS的专栏-CSDN博客](https://blog.csdn.net/u012061345/article/details/52224623/)

[Java实现 蓝桥杯 算法提高 递推求值_南 墙-CSDN博客](https://blog.csdn.net/a1439775520/article/details/91896453)

0.0分

1 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

　　评论区

SinzoL

这算简单题吗

2022-06-24 21:41:31

斯巴达

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题9.6 （C语言代码）

字符统计（C语言代码）

C二级辅导-公约公倍（C语言代码）

C语言程序设计教程（第三版）课后习题9.2 （C语言代码）

C二级辅导-统计字符（C语言代码）

1907: 蓝桥杯算法提高VIP-递推求值 java

评论区

精彩推荐

母牛的故事（C语言代码）

C语言程序设计教程（第三版）课后习题3.7 （C语言代码）

最长单词（C语言代码）

DNA （C语言描述，蓝桥杯）

a+b

回文数字（C语言代码）

关于float，double变量的几点说明

循环入门练习6 （C语言代码）

C语言程序设计教程（第三版）课后习题8.5 （C语言代码）

C语言程序设计教程（第三版）课后习题11.5 （C语言代码）

斯巴达

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题9.6 （C语言代码）

字符统计 （C语言代码）

C二级辅导-公约公倍 （C语言代码）

C语言程序设计教程（第三版）课后习题9.2 （C语言代码）

C二级辅导-统计字符 （C语言代码）

1907: 蓝桥杯算法提高VIP-递推求值 java

评论区

精彩推荐

母牛的故事 （C语言代码）

C语言程序设计教程（第三版）课后习题3.7 （C语言代码）

最长单词 （C语言代码）

DNA （C语言描述，蓝桥杯）

a+b

回文数字 （C语言代码）

关于float，double变量的几点说明

循环入门练习6 （C语言代码）

C语言程序设计教程（第三版）课后习题8.5 （C语言代码）

C语言程序设计教程（第三版）课后习题11.5 （C语言代码）

字符统计（C语言代码）

C二级辅导-公约公倍（C语言代码）

C二级辅导-统计字符（C语言代码）

　　评论区

母牛的故事（C语言代码）

最长单词（C语言代码）

回文数字（C语言代码）