题意：
斐波拉契数列的另外一个变型，如果F（n）能被3整除，则输出yes，否则输出no。(n<1000000)
解题思路：
看到(n<1000000)这个条件，有点感觉递归量有点大，因此要将递归转为循环~不过有没更巧妙地做法呢，暂且不知。
递归java代码实现：（结果当然是Time Limit Exceeded）
import java.util.*;
import java.io.*;
public class Main{
public static void main(String[] arg){
Scanner scan = new Scanner(new BufferedInputStream(System.in));
while(scan.hasNextInt()){
int n =scan.nextInt();
if(check(n)){
System.out.println("yes");
continue;
}
System.out.println("no");
}
scan.close();
}
static boolean check(int n){//检测F(n)能不能整除3
int result = getResult(n);
return result%3==0;
}
static int getResult(int n){
if(n==0){
return 7;
}
if(n==1){
return 11;
}
return getResult(n-1) + getResult(n-2);
}
}
于是我立刻就把递归改为了循环：（结果竟然是Wrong Answer），可能是数字越界了 吧，或者算法有错，或者其他原因~
/*
* 循环实现
* */
static int getResult2(int n){
int result = 0;
if(n==0){
return result += 7;
}
if(n==1){
return result += 11;
}
int preNum1 =7;
int preNum2 =11;
int len = n + 1;
for(int i = 2 ; i != len ; i ++){
int temp = preNum2;
preNum2 = preNum1 + preNum2;
preNum1 = temp;
result = preNum2;
}
return result;
}
在找错误的过程中，想到是被3整除，因此这道题的巧妙解法就诞生了。只需要求出前两个数的取余结果相加就行了。
另外一点，往往这种函数都是有周期性的：观察得取余结果的周期为8（1 2 0 2 2 1 0 1）
不得不惊叹数学的巧妙，哈哈哈
结果当然Accepted
import java.util.*;
import java.io.*;
public class Main{
public static void main(String[] arg){
Scanner scan = new Scanner(new BufferedInputStream(System.in));
while(scan.hasNextInt()){
int n =scan.nextInt();
if(resultArray[n%8]==0){
System.out.println("yes");
continue;
}
System.out.println("no");
}
scan.close();
}
static int[] resultArray = createResultArray();
/*
* 观察得取余结果周期为8
* 因此生产取余结果周期表（0-2序列）
* */
static int[] createResultArray(){
int[] resultArray = new int[8];
for(int i = 0 ; i != 8 ; i ++ ){
resultArray[i] = getResult(i);
}
return resultArray;
}
/*
* 由于该题的特殊环境，能不能被3整除
* 因此只需要求出前两个数的取余结果相加就行了
* */
static int getResult(int n){
int result = 0;
if(n==0){
return result += 7%3;
}
if(n==1){
return result += 11%3;
}
int preNum1 =7%3;
int preNum2 =11%3;
int len = n + 1;
for(int i = 2 ; i != len ; i ++){
int temp = preNum2%3;
preNum2 = (preNum1 + preNum2)%3;
preNum1 = temp;
result = preNum2;
}
return result;
}
}