22

编程题 22 /22

NowCoder最近在研究一个数列:
* F(0) = 7
* F(1) = 11
* F(n) = F(n-1) + F(n-2) (n≥2)
他称之为NowCoder数列。请你帮忙确认一下数列中第n个数是否是3的倍数。

参考答案

题目中的公式为F(n)=F(n-1)+F(n-2)
模拟规律得:F(2)=F(1)+F(0)=11+7=18 可以整除
F(3)=F(2)+F(1)=18*1+11*1 不可以被整除
F(4)=F(3)+F(2)=18*2+11*1  不可以被整除
F(5)=F(4)+F(3)=18*3+11*2  不可以被整除
F(6)=F(5)+F(4)=18*5+11*3  可以整除
以此类推可以发现数列最终是求11出现的个数即只要11出现3倍的时候才能被整除,正好n=2,6,10,14......能被3整除 即n%4==2的即可被3整除。

发现这样一个规律便之和n有关系了,代码如下:

import java.util.Scanner;
public class Main{
    /**
     * 通过上面的公式发现数列最终是求11出现的个数即只要11出现3倍的时候才能被整除,正好n=2,6,10,14......能被3整除
     * 即n%4==2的即可被3整除
     */
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNext()) {
            int n = in.nextInt();
            System.out.printf("%s\n",( n % 4 == 2)?"Yes":"No");
        }
        in.close();
    }