- 列表项目
public static void main(String[] args) {
Scanner in=new Scanner(System.in);
while(in.hasNext()){
int A=in.nextInt();
int B=in.nextInt();
int n=in.nextInt();
if(A>=1 && A<=1000 && B>=1 && B<=1000 && n>=1 && n<=100000000){
if(A==0 && B==0 && n==0){
break;
}
int a[]=new int[n];
if(n==1){
a[0]=1;
}
if(n==2){
a[0]=1;
a[1]=1;
}
if(n>2){
a[0]=1;
a[1]=1;
for(int i=2;i<n;i++){
a[i]=(A * a[i-1] + B * a[i-2])%7;
}
}
System.out.println(a[n-1]);
}
}
}
我这样写,显示错误。
不知道哪里错了。
我这样写对的,不知道上一种方法哪里错了
报啥错你看了么?显示错误
这样的问题描述,如果是问你自己,你该如何回答?
推测是OOM了 ,算法没啥问题,但是如果n=100000000
,就要分将近400M内存给new int[n];
一般的ACM平台,不会给这么大内存吧
这题就是斐波那契的变种,三种方法可以得出结果,第一种是传统的递归模式(效率极低,请勿使用),第二种是尾递归,第三种是单次循环,都可以使用。
java
import java.util.Scanner; public class Main { private int A,B; Main(int A,int B){ this.A=A; this.B=B; } // 递归,效率极低 public int answer(int n){ if(n==1 || n==2)return 1; return (A*answer(n-1)+B*answer(n-2))%7; } // 尾递归,效率高 public int answer2(int n){ return answer2(n,1,1); } public int answer2(int n,int x,int y) { if(n==1 || n==2)return y; return answer2(n-1,y,(A*y+B*x)%7); } // 单次循环,效率高 public int answer3(int n){ if(n==1 || n==2)return 1; int x=1,y=1; for(int i=3;i<=n;i++){ int z=y; y=(A*y+B*x)%7; x=z; } return y; } public static void main(String[] args) { Scanner in=new Scanner(System.in); while(in.hasNext()){ int A=in.nextInt(),B=in.nextInt(),n=in.nextInt(); if(A==0 && B==0 && n==0){ break; } if(A>=1 && A<=1000 && B>=1 && B<=1000 && n>=1 && n<=100000000){ System.out.println(new Main(A,B).answer3(n)); } } } }