首页 > 专题系列 > Java解POJ > POJ 3070 Fibonacci [解题报告] Java
2013
11-12

POJ 3070 Fibonacci [解题报告] Java

Fibonacci

问题描述 :

In the Fibonacci integer sequence, F0 = 0, F1 = 1, and Fn = Fn − 1 + Fn − 2 for n ≥ 2. For example, the first ten terms of the Fibonacci sequence are:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, …

An alternative formula for the Fibonacci sequence is

.

Given an integer n, your goal is to compute the last 4 digits of Fn.

输入:

The input test file will contain multiple test cases. Each test case consists of a single line containing n (where 0 ≤ n ≤ 1,000,000,000). The end-of-file is denoted by a single line containing the number −1.

输出:

For each test case, print the last four digits of Fn. If the last four digits of Fn are all zeros, print ‘0’; otherwise, omit any leading zeros (i.e., print Fn mod 10000).

样例输入:

0
9
999999999
1000000000
-1

样例输出:

0
34
626
6875

温馨提示:

As a reminder, matrix multiplication is associative, and the product of two 2 × 2 matrices is given by

.

Also, note that raising any 2 × 2 matrix to the 0th power gives the identity matrix:

.

解题代码:

import java.io.BufferedReader;
    import java.io.IOException;
    import java.io.InputStreamReader;
   
    public class Main {
   
        public static void main(String[] args) throws IOException {
            BufferedReader read = new BufferedReader(new InputStreamReader(
                    System.in));
          int[] f = new int[15000];
           f[0] = 0;
           f[1] = 1;
           f[2] = 1;
           for (int i = 2; i < f.length - 1; i++) {
               f[i + 1] = (f[i - 1] + f[i]) % 10000;
           }
           int i;
           while ((i = Integer.parseInt(read.readLine())) != -1) {
               System.out.println(f[i % 15000]);
           }
       }
   }

  1. 这道题这里的解法最坏情况似乎应该是指数的。回溯的时候
    O(n) = O(n-1) + O(n-2) + ….
    O(n-1) = O(n-2) + O(n-3)+ …
    O(n) – O(n-1) = O(n-1)
    O(n) = 2O(n-1)

  2. 给你一组数据吧:29 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 1000。此时的数据量还是很小的,耗时却不短。这种方法确实可以,当然或许还有其他的优化方案,但是优化只能针对某些数据,不太可能在所有情况下都能在可接受的时间内求解出答案。