使用遞歸實現斐波那契而不使用java.bignumber

Question

我想在不使用BigInteger類導入的情況下實現斐波那契序列，因此我重寫了自己的添加方法，並花了兩天時間，但我不知道爲什麼前6個數字的答案是正確的，其餘答案與正確答案相反（例如，n = 7，我的答案是：31是正確的：13; n = 15，我的答案= 016，正確的一個= 610），當n變大時，答案就完全錯誤了（甚至不是正確答案的顛倒過程，這發生在n> = 25時）。 任何意見將不勝感激！

以下是我的輸出：

The 0th Fibonacci number is : 
    0 
    The 1th Fibonacci number is : 
    1 
    The 2th Fibonacci number is : 
    1 
    The 3th Fibonacci number is : 
    2 
    The 4th Fibonacci number is : 
    3 
    The 5th Fibonacci number is : 
    5 
    The 6th Fibonacci number is : 
    8 
    The 7th Fibonacci number is : 
    31 
    The 8th Fibonacci number is : 
    12 
    The 9th Fibonacci number is : 
    43 
    The 10th Fibonacci number is : 
    55 
    The 11th Fibonacci number is : 
    98 
    The 12th Fibonacci number is : 
    441 
    The 13th Fibonacci number is : 
    332 
    The 14th Fibonacci number is : 
    773 
    The 15th Fibonacci number is : 
    016 
    The 16th Fibonacci number is : 
    789 
    The 17th Fibonacci number is : 
    7951 
    The 18th Fibonacci number is : 
    4852 
    The 19th Fibonacci number is : 
    1814 
    The 20th Fibonacci number is : 
    5676 
    The 21th Fibonacci number is : 
    64901 
    The 22th Fibonacci number is : 
    11771 
    The 23th Fibonacci number is : 
    75682 
    The 24th Fibonacci number is : 
    86364 
    The 25th Fibonacci number is : 
    52047 
    The 26th Fibonacci number is : 
    393021 
    The 27th Fibonacci number is : 
    814491 
    The 28th Fibonacci number is : 
    118413 
    The 29th Fibonacci number is : 
    922905 
    The 30th Fibonacci number is : 
    040428 

而下面是我的代碼：

package com.example.helloworld; 


import java.util.ArrayList; 
import java.util.Arrays; 
import java.util.Collections; 

public class Fibonacci_Recursive{ 
    public static void main(String[] args) { 
     long start = System.nanoTime(); 
     long time = 0L; 
     for(int i = 0; time <= 60L; i++) 
     { 
      Fibonacci_Recursive fr = new Fibonacci_Recursive(i); 
      time = ((System.nanoTime() - start)/1000_000_000); 
     } 
    } 

    private Fibonacci_Recursive(int n){ 
     System.out.println("The " + n + "th Fibonacci number is :"); 
     if (n <= 1){ 
      System.out.println(n); 
     } 
     else { 
      int[] finalResult = getF(n); 
      String st = ""; 
      for (int i = 0; i < finalResult.length; i++){ 
       st = finalResult[i] + st; 
      } 
      System.out.println(st); 
     } 
    } 

    private int[] getF(int n){ 
     int[] head = new int[1]; 
     if (n <= 1) { 
      head[0] = n; 
      return head; 
     } 
     return add(getF(n - 1), getF(n - 2)); 
    } 

    private int[] add(int[] s1, int[] s2){ 
     int carrier = 0; 
     ArrayList<Integer> result = new ArrayList<>(); 
     int[] array1 = s1; 
     int[] array2 = s2; 
     array1 = reverseGeneralArray(array1); 
     array2 = reverseGeneralArray(array2); 
     int min = array2.length; 
     int min2 = array1.length; 

     if(min2 > min) { 
      for (int i = 0; i < min; i++) { 
       int x = array1[i] + array2[i]; 
       result.add((x + carrier) % 10); 
       carrier = x/10; 
      } 
      for (int j = 0; j <= min2 - min - 1; j++) { 
       int index = min; 
       result.add((array1[index] + carrier) % 10); 
       carrier = (array1[index] + carrier)/10; 
       index++; 
      } 
      if (carrier > 0) { 
       result.add(carrier); 
      } 
      Collections.reverse(result); 
      return convertIntegers(result); 
     } 
     else if(min2 < min) 
      { 
       for(int i = 0; i < min2; i ++){ 
        int x = array1[i] + array2[i]; 
        result.add((x + carrier) % 10); 
        carrier = x/10; 
       } 
       for(int j = 0; j <= min - min2 - 1; j++){ 
        int index = min2; 
        result.add((array2[index] + carrier) % 10); 
        carrier = (array2[index] + carrier)/10; 
        index++; 
       } 
       if (carrier > 0) { 
        result.add(carrier); 
       } 
       Collections.reverse(result); 
       return convertIntegers(result); 
      }else { 
       for (int i = 0; i < min; i++) { 
        int x = array1[i] + array2[i]; 
        result.add((x + carrier) % 10); 
        carrier = x/10; 
       } 
       if (carrier > 0) { 
        result.add(carrier); 
       } 
      Collections.reverse(result); 
      return convertIntegers(result); 
      } 

    } 

    private static int[] convertIntegers(ArrayList<Integer> integers) 
    { 
     int[] ret = new int[integers.size()]; 
     for (int i=0; i < integers.size(); i++) 
     { 
      ret[i] = integers.get(i); 
     } 
     return ret; 
    } 

    private int[] reverseGeneralArray(int[] x){ 
     int[] newX = new int[x.length]; 
     for(int i = 0; i < x.length; i++){ 
      newX[i] = x[x.length - i -1]; 
     } 
     return newX; 
    } 

} 

Answer 1

你錯過建設的結果，你從int[] finalResult拼接錯誤（反向）的方式String st：

private Fibonacci_Recursive(int n) { 
    ... 
    for (int i = 0; i < finalResult.length; i++) { 
     //Replaced st = finalResult[i] + st by 
     st = st + finalResult[i]; 
    } 
    ... 
} 

額外：考慮，在環連接字符串時，因爲串聯拷貝整個字符串，使用StringBuilder：

StringBuilder st = new StringBuilder(); 
for (int i = 0; i < finalResult.length; i++) { 
    st.append(finalResult[i]); 
} 

更新：從25開始，錯誤變得明顯：承運人不正確時的總和兩位數字等於10（74025而不是75025）。該缺陷是在add方法，其中，承運人應被計算爲：

carrier = (x + carrier)/10; 

即：你必須要考慮到先前的載體。