UVa 1646 – Edge Case [规律+大数]

点击打开vjudge题目链接

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

分析:找规律,n=3时答案是4,n=4时答案是7,画画图递推一下发现n=5时答案是11,n=6时答案是18…类似于斐波那契数列。因为并没有取模,需要大数,直接上java.

import java.math.BigInteger;
import java.util.Scanner;

public class Main {
    static BigInteger[] a = new BigInteger[10240];
    private static void init() {
        a[3] = BigInteger.valueOf(4);
        a[4] = BigInteger.valueOf(7);
        for(int i = 5; i < a.length; ++i)
            a[i] = a[i-2].add(a[i-1]);
    }
    public static void main(String[] args) {
        init();
        Scanner cin = new Scanner(System.in);
        while(cin.hasNextInt()) {
            int n = cin.nextInt();
            System.out.println(a[n]);
        }
        cin.close();
    }
}

欢迎留言