HDOJ 1568 Fibonacci 解题报告 - Linux安全网 - Linux操作系统_Linux 命令_Linux教程

HDOJ 1568 Fibonacci 解题报告

日期:2011-08-07 点击:23 来源: 未知分享至:

http://acm.hdu.edu.cn/showproblem.php?pid=1568 话说好久没用Java啦~

这道题算的上经典，运用Fibonacci的通项公式 $\"\"$ 和10底对数lg。

两边同时取lg，有 $\"\"$ 。最后一项是无穷小，乎略不计。

Run ID	Submit Time	Judge Status	Pro.ID	Exe.Time	Exe.Memory	Code Len.	Language	Author
4347857	2011-08-06 15:59:18	Accepted	1568	156MS	3816K	599 B	Java	GongZi

import java.util.*;

public class Main {
    static Scanner cin = new Scanner(System.in);
    static int[] fib = new int[21];

    public static void main(String[] args) {

        fib[0] = 0;
        fib[1] = 1;
        for (int i = 2; i < 21; ++i) {
            fib[i] = fib[i - 1] + fib[i - 2];
        }

        while (cin.hasNext()) {
            int n = cin.nextInt();
            if (n <= 20) {
                System.out.println(fib[n]);
            } else {
                double p = n * Math.log10((1 + Math.sqrt(5)) / 2) - Math.log10(5) / 2;
                p = p - (int) p;
                int result = (int) (Math.pow(10, p) * 1000);
                System.out.println(result);
            }
        }
    }
}

刚开始想用Java的BigInteger来实现，结果TLE.....

4346737

2011-08-06 14:03:07

Time Limit Exceeded

1568

1000MS

4008K

666 B

Java

GongZi

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

public class Main {
    public static void main(String[] argc) {
        Scanner cin = new Scanner(System.in);
        int n;
        while (cin.hasNextInt()) {
            n = cin.nextInt();
            System.out.println(fib(n));
        }
    }

    public static String fib(int n) {
        String s = null;
        if (n == 0) {
            return \"0

Tags：

分享至: