首页 > 代码库 > UVA 1646 Edge Case

UVA 1646 Edge Case

题意:n(3<=n<=10000)个结点组成一个圈,点顺次连接为边,求没有公共点的边集个数。

分析:

1、推规律,n=3有4个,n=4有7个,n=5有11个,n=6有18个,……,a[i] = a[i - 1] + a[i - 2]

2、边集,包括空集

import java.math.BigInteger;
import java.util.Scanner;
public class Main {
    public static BigInteger[] a = new BigInteger[10000 + 10];
    public static void init(){
        a[3] = BigInteger.valueOf(4);//基本类型转化成大数
        a[4] = BigInteger.valueOf(7);
        for(int i = 5; i <= 10000; ++i){
            a[i] = a[i - 1].add(a[i - 2]);
        }
    }
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        init();
        Scanner sc = new Scanner(System.in);
        while(sc.hasNextInt()){
            int i = sc.nextInt();
            System.out.println(a[i]);
        }
    }
}

 

UVA 1646 Edge Case