斐波那契数列

image.png

package one;
/**
* 带有缓存的方法，比递归方法性能好很多
*/
import java.util.Scanner;
public class BEGIN_4 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        Integer n = sc.nextInt();
        int f[] = new int[1000001];
        f[1] = 1;
        f[2] = 1;
        for (int i = 3; i <= n; i++) {
            f[i] = (f[i - 1] + f[i - 2]) % 10007;
        }
        System.out.println(f[n]);
        sc.close();
    }
    
}

实现斐波那契数列

1. 平推法

   public static long fibLoop(int num) {
       if(num < 1 || num > 92)
           return 0;
       long a = 1;
       long b = 1;
       long temp;
       for(int i = 3; i <= num; i++) {
           temp = a;
           a = b;
           b += temp;
       }
       return b;
   }
   

2. 递归法

   /**
   * 递归方法实现
   * f(n) = f(n - 1) + f(n - 2)
   * 最高支持 n = 92 ，否则超出 Long.MAX_VALUE
   * @param num n 
   * @return f(n) 
   */
   private static int fib(Integer n) {
           if (n <= 2) {
               return 1;
           }
           return fib(n - 1) + fib(n - 2);
   
       }
   

3. 数组法（缓存法）

    int f[] = new int[1000001];
    f[1] = 1;
    f[2] = 1;
    for (int i = 3; i <= n; i++) {
        f[i] = (f[i - 1] + f[i - 2]) % 10007;
    }