首页 > 代码库 > UVA10862 - Connect the Cable Wires(递推 + java的大数)

UVA10862 - Connect the Cable Wires(递推 + java的大数)

UVA10862 - Connect the Cable Wires(递推 + java的大数)

题目链接

题目大意:给你n座房子位于一条直线上,然后仅仅给你一个cable service。要求每座房子都连上有线,方式能够是间接的通过这个房子的直接邻居连接(前提是它的邻居要连上有线),第二种是直接连上cable service也是能够的。

解题思路:把后面的房子编号为1,前面的为n。如果我们要连1号房子,那么它有三种可能。


1、直接和cable service连接,那么就是加上f(n - 1)种(前面的n - 1座房子的组合方式)。


2、和2号房子连接不和cable service连接,那么又是f(n - 1)种。


3、和2号房子链接且和cable service连接,那么这就意味这2号房子不能和cable service链接,否则形成环了。这样就能够把1号和2号看成一个总体,而且和cable service有一条边。这种情况就能够分两种:(1)、不和三号连,加上f(n - 2)。

(2)和三号连,这样情况又回到情况3,说明这个是能够递归的。

所以f(n) = 2 f(n - 1) + f(n - 2) + f(n - 3) + .. + f(1) + 1.(递归到1的时候仅仅有不和1号连接和与1号连接然后1号不和cable service这两种)
相同写出f(n - 1),相减得:f(n) = 3 $*
$ f(n - 1) - f(n - 2); (n > 2).
边界f(2) = 3, f(1) = 1;3的2000次方会超过long long的,所以要用大数。

代码:

import java.util.*;
import java.math.*;
import java.io.*;

public class Main {

    static BigInteger f[] = new BigInteger[2005];

    public static void init() {

        f[1] = BigInteger.valueOf(1); 
        f[2] = BigInteger.valueOf(3);
        for (int i = 3; i <= 2000; i++)
            f[i] = BigInteger.valueOf(3).multiply(f[i - 1]).subtract(f[i - 2]);
    }

    public static void main(String args[]) {

        Scanner cin = new Scanner(System.in);
        int n;
        init();

        while (true) {

            n = cin.nextInt();
            if (n == 0)
                break;

            System.out.println(f[n]);
        }
    }
}

UVA10862 - Connect the Cable Wires(递推 + java的大数)