递推求值

已知递推公式： 　　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 import java.util.Scanner; public class Main { //递推 public static int f(int m,int i){ if(m==1&&i==1) //把已知条件写进去 return 2; else if(m==1&&i==2) return 3; else if(m==2&&i==1) return 1; else if(m==2&&i==2) return 4; else if(m==3&&i==1) return 6; else if(m==3&&i==2) return 5; else if(m>3&&i==1) //通过已知递推回来的算法 return f(m-1, 2) + 2*f(m-3, 1) + 5; else if(m>3&&i==2) return f(m-1,1)+3*f(m-3,1)+2*f(m-3,2)+3; return 0; //因为是int型返回所以必须return 0;否则报错 } public static void main(String[] args) { // TODO Auto-generated method stub Scanner sc=new Scanner(System.in); int n=sc.nextInt(); System.out.println(f(n,1)