打印出斐波那契数列

Question

我正在尝试编写一个递归算法来计算斐波那契数列。但是，该程序在打印结果时遇到困难。

我的想法是将每个计算值存储到一个数组中（这样算法应该更快）。

我想要的输出：

The fibonacci of n = 1 is fn= 1    
The fibonacci of n = 2 is fn= 2    
The fibonacci of n = 3 is fn= 2    
The fibonacci of n = 4 is fn= 3
...
The fibonacci of n = 8 is fn= 21

public class fibonacciCalculator {

    static int[] arr = new int[50];

    static int fibo (int n, int arr[]) {
        if ( n == 0 ) {
            return 0; 
        }else if ( n == 1 ) {
            return 1; 
        } 
        if ( arr[n-1] == 0) {
            arr[n-1] = fibo(n-1, arr);  
        }
        if ( arr[n-2] == 0) {
            arr[n-2] = fibo(n-2, arr);
        }
        return arr[n-1] + arr[n - 2];
    } 

    public static void main(String[] args) {

        for (int i = 1; i == 8; i++) {
            if (arr [i] == 0) {
                fibo(i, arr);
                int x = arr[i];
                String a = String.format("The fibonacci of n = %d is fn= %d", i , x);
                System.out.println(a);
                }
        }
    }
}

Answer 1

您可以在不声明数组的情况下执行此操作。这样，中间值存储在执行栈中：

public class fibonacciCalculator {

    static int fibo (int n) {
        if ( n == 0 ) {
            return 0; 
        } else if ( n == 1 ) {
            return 1; 
        } else {
            return fibo(n-2) + fibo(n-1);  
        }
    } 

    public static void main(String[] args) {

        for (int i = 1; i <= 8; i++) {
            int x = fibo(i);;
            String a = String.format("The fibonacci of n = %d is fn= %d", i , x);
            System.out.println(a);
        }
    }
}

Answer 2

这是一种方法。

   public int[] fib(int values[], int count) {
      if (count <= 0) {
         return values;
      }

      int k = values.length + 1;
      values = Arrays.copyOf(values, k);

      values[k - 1] = values[k - 2] + values[k - 3];
      return fib(values, count - 1);
   }

但更好的方法是 memoize 创建值时。这允许您从最后计算的项开始计算，然后继续计算直到达到您的目标。如果您指定的值小于计算出的数字，则只返回请求的值。

使用了列表的防御副本，因此您不能 taint 返回的子列表。

   List<Integer> fibs = new ArrayList(List.of(0, 1));
   public List<Integer> fib(int count) {
      int s = fibs.size();
      if (count < s) {
         // return a defensive copy to protect cached values.
         return new ArrayList<>(fibs.subList(0, count));
      }
      int e = fibs.get(s - 1) + fibs.get(s - 2);
      fibs.add(e);
      return fib(count);
   }

Answer 3

好的，我将post 关闭这个工作代码。也许这会对其他人有所帮助。

public class fibonacciCalculator {
    static int[] arr = new int[48];
    static int fibo (int n, int arr[]) {
        if ( n == 1|| n == 2 ) {
            return 1; 
        }else if ( n == 0 ) {
            return 0; 
        }
        if (arr[n-1] == 0) {
            arr[n-1] = fibo(n-1, arr);
        }
        if (arr[n-2] == 0) {
            arr[n-2] = fibo(n-2, arr);
        }
        return arr[n-1] + arr[n - 2];
    }   
    public static void main(String[] args) {

        for (int i = 1; i <= arr.length-1; i++) {
            if (arr [i] == 0) {
                arr[i] = fibo(i, arr);
                System.out.print("The Fibonacci number " + i);
                System.out.println(" is: " + arr[i]);
            }       
        }
    }
}

但是...int 将超过其在 Fibonacci 48 的限制。如果您想要更高的值，则应将 int 替换为 long。但在那之后不知道.. :D 问候 Synix

打印出斐波那契数列

Printing out an array of Fibonacci numbers

java

printing

arrays

recursion

fibonacci