解題區/解題區 - UVa

UVa 10694 - Combinatorial Summation

contents

  1. 1. Problem
  2. 2. Sample Input
  3. 3. Sample Output
  4. 4. Solution

Problem

對於組合公式，輸出其結果。

Sample Input

1
2
3
2
3
4

Sample Output

1
2
7
14

Solution

暴力法將前幾項找出來，發現其相鄰兩項之差恰好有規律。

1
2
0 1 3 7 14 26 46 79 133 
  0 2 4 7 12 20 33 54

其規律是前兩項總和再加一。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
import java.util.Scanner;
import java.math.BigInteger;
public class Main {
    public static void main(String[] args) {
        BigInteger[] f1 = new BigInteger[1024];
        BigInteger[] f2 = new BigInteger[1024];
        f1[1] = BigInteger.valueOf(2);
        f1[2] = BigInteger.valueOf(4);
        f2[0] = BigInteger.valueOf(0);
        f2[1] = BigInteger.valueOf(1);
        for (int i = 3; i < f1.length; i++)
            f1[i] = f1[i - 2].add(f1[i - 1]).add(BigInteger.ONE);
        for (int i = 2; i < f2.length; i++)
            f2[i] = f2[i - 1].add(f1[i - 1]);
        Scanner cin = new Scanner(System.in);
        int testcase = cin.nextInt();
        while (testcase-- != 0) {
            int n = cin.nextInt();
            if (n < 0)
                n = 0;
            System.out.println(f2[n]);
        }
    }
}
/*
 * 0 1 3 7 14 26 46 79 133 
 	 0 2 4 7 12 20 33 54
 */