首页 > 代码库 > UVA - 1646 - Edge Case(找规律)

UVA - 1646 - Edge Case(找规律)

题意:n(3 <= n <= 10000)个结点组成一个圈,求匹配(即没有公共点的边集)的个数。

找规律为斐波那契的性质,因为数太大所以用的java大数。

import java.math.BigInteger;
import java.util.Scanner;
public class Main{
    public static int MAXN = 10000 + 10;
    public static BigInteger []c = new BigInteger[MAXN];
    public static void init(){
        c[3] = new BigInteger("4");
        c[4] = new BigInteger("7");
        for(int i = 5; i < MAXN; ++i)
            c[i] = c[i - 1].add(c[i - 2]);
    }
    public static void main(String []args){
        init();
        Scanner sc = new Scanner(System.in);
        while(sc.hasNextInt()){
            int n = sc.nextInt();
            System.out.println(c[n]);
        }
    }
}

 

UVA - 1646 - Edge Case(找规律)