遞歸求解Fibonacci序列沒有先前的位數

Question

有沒有辦法在手邊沒有任何信息的情況下將斐波那契序列打印到第n位數字？這是我的一種方法，儘管我們使用了先前的信息。

int p; 
int n = 0; 
String fib = "0, 1"; 

public printFib() { 
    String fibSequence = fibPrint(0, 1, x); //x denotes xth fib number 
    System.out.println(fibSequence); 
} 

private String logicFib (int a, int b, int c) { 
    if (n == c-2) { 
     return fib; 
    } else { 
     n++; 
     p = a + b; 
     fib = fib + ", " + p; 
     logicFib(b, p, c); 
    } 
} 

這裏的問題是，我打印數字3, 4, 5, ... n上的數字1, 2，當我想全部打印出來，而不首先聲明前兩位頂部。我的方法的邏輯只適用於前兩位數字已經知道，當我想放棄這一點。

Answer 1

我認爲斐波納契標準的解決辦法如下所示：

public class Fibonacci { 

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

    public static void main(String...args){ 

     int n = 20; 
     Fibonacci f = new Fibonacci(); 
     for(int i = 0; i < n; i++){ 
      System.out.println(f.fibo(i)); 
     } 
    } 
} 

在你總是需要休息條件的遞歸方法。在這種斐波納契方法的情況下，這將是您可以在上面識別的第0和第1斐波那契數。沒有其他方法遞歸地計算斐波納契數。你只需要休息條件。

如果你不需要你的方法的遞歸字符，你可以通過Binet的公式計算出數字。有關這一點的更多信息，請點擊here。

編輯：

我改變我的方法。現在它正在計數直到第n個斐波納契數。

Answer 2

那麼你知道限制，因爲你必須知道你想打印多少個數字。

public class Fibonacci { 
    public int limit = 10; 
    public int left=0, right=1; 
    public int next; 
    public void countNextFibo(int limit) { 
     if(this.limit==0) { 
      return; 
     } 
     else { 
      System.out.print(left+", "); 
      next = left+right; 
      left = right; 
      right = next;    
      --this.limit; 
      countNextFibo(this.limit); 
     } 
    } 

    public static void main(String args[]) { 
     Fibonacci f = new Fibonacci(); 
     f.countNextFibo(10); 
    } 
} 

Answer 3

該解決方案使用Iterator接口。運行時，它會計算長距離內的所有斐波納契數。接受的答案是每次呼叫的O(n^2)，因爲它是倍增指數時間。在我的計算機上將n更改爲93來執行與我的程序相同的操作，它將使用幾個小時來計算此代碼在0.09秒內執行的相同列表。

import java.util.Iterator; 
import java.util.NoSuchElementException; 
import java.lang.IllegalArgumentException; 

public class Fibonacci implements Iterable<Long> 
{ 
    final int FIB_MAX_LONG_INDEX = 92; // highest index producing correct long 
    int fromIndex = 0; 
    int toIndex = FIB_MAX_LONG_INDEX; 

    public Fibonacci(int fromIndex, int toIndex) 
    { 
     if(fromIndex > toIndex) 
      throw new IllegalArgumentException("toIndex must be same or greater than fromIndex"); 

     if(toIndex > FIB_MAX_LONG_INDEX) 
      throw new IllegalArgumentException("toIndex must be lowe or equal to 92 to not overflow long"); 

     this.fromIndex = fromIndex; 
     this.toIndex = toIndex; 
    } 

    public Fibonacci(){} 

    private class FibonacciIterator implements Iterator<Long> 
    { 
     private long cur = 0, next = 1; 
     private int index=0; 

     public boolean hasNext() 
     { 
      return index <= toIndex; 
     } 

     public Long next() 
     { 
      if (index > toIndex) 
       throw new NoSuchElementException(); 

      long tmpCur; 
      do { 
       tmpCur = cur; 
       cur = next; 
       next +=tmpCur; 
       index++; 
      } while (index <= fromIndex); 

      return tmpCur; 
     } 

     public void remove() 
     { 
      throw new UnsupportedOperationException(); 
     } 
    } 

    public Iterator<Long> iterator() 
    { 
     return new FibonacciIterator(); 
    } 

    public static void main (String[] args) 
    { 
     Fibonacci fib = new Fibonacci(); 
     for (long i : fib) 
     { 
      System.out.print(i + " "); 
     } 
     System.out.println(); 
    } 
} 

運行時輸出（我已經添加了一些換行）：

0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 
2584 4181 6765 10946 17711 28657 46368 75025 121393 
196418 317811 514229 832040 1346269 2178309 3524578 
5702887 9227465 14930352 24157817 39088169 63245986 
102334155 165580141 267914296 433494437 701408733 
1134903170 1836311903 2971215073 4807526976 7778742049 
12586269025 20365011074 32951280099 53316291173 
86267571272 139583862445 225851433717 365435296162 
591286729879 956722026041 1548008755920 2504730781961 
4052739537881 6557470319842 10610209857723 
17167680177565 27777890035288 44945570212853 
72723460248141 117669030460994 190392490709135 
308061521170129 498454011879264 806515533049393 
1304969544928657 2111485077978050 3416454622906707 
5527939700884757 8944394323791464 14472334024676221 
23416728348467685 37889062373143906 61305790721611591 
99194853094755497 160500643816367088 
259695496911122585 420196140727489673 
679891637638612258 1100087778366101931 
1779979416004714189 2880067194370816120 
4660046610375530309 7540113804746346429 

但正如你看到的，你可以做幾乎所有的指標範圍內。下面的循環超過30至39，並結束up打印832040 1346269 2178309 3524578 5702887 9227465 14930352 24157817 39088169 63245986

Fibonacci fib = new Fibonacci(30, 39); 
for(long i : fib) { 
    System.out.print(i + " "); 
}