UVa 1647 - Computer Transformation（找规律＋递推）

发表于 分类于 ， Disqus：

暴力枚举前几项后发现规律 a [ i ] = a [ i − 1 ] + 2 ∗ a [ i − 2 ] 。然后打表就好。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
import java.math.*;
import java.util.Scanner;
public class Main{
    public static void main(String[] args){
        Scanner cin = new Scanner(System.in);
        BigInteger[] a = new BigInteger[1010];
        a[1].valueOf(0);
        a[2].valueOf(1);
        for (int i = 3; i<1010;++i){
            a[i] = a[i].add(a[i-1]);
            a[i] = a[i].add(a[i-2]);
            a[i] = a[i].add(a[i-2]);
        }
        while(cin.hasNext()) {
            int n = cin.nextInt();
            System.out.println(a[n]);
        }
    }
}

** 本文迁移自我的CSDN博客，格式可能有所偏差。 **