次のフィボナッチ数を生成

Question

フィブリッド番号の生成についてこの質問がありました。私が見たfib数の再帰的実装は、fib（n）= fib（n-1）+ fib（n-2）のように常に上から前になりましたが、この質問はfib（n-1）、fib n-2）が存在すると仮定する。

public class Fibonacci { 
    int[] fiboNums; 

    public Fibonacci(int n) { 
     // TODO: generate the first n fibonacci numbers 
    } 

    private void generateNextFibo(int n, int lastFibo, int lastLastFibo) { 
     // TODO: Implement this recursive function to compute next 
     // fibonacci number. 
    } 

    public int[] getAll() { 
     return fiboNums; 
    } 
} 

Answer 1

最初のトリッキーな部分は、params generateNextFiboを呼び出す必要があります。 2番目の部分はgenerateNextFiboメソッドの終了条件です。

public class Fibonacci { 
    int fiboNums[]; 

    public Fibonacci(int n) { 
     // generate the first n fibonacci numbers 
     fiboNums = new int[n]; 
     fiboNums[0] = 1; 
     fiboNums[1] = 1; 

     // Start from 3 since the first two fibo numbers are given 
     if (n >= 3) 
      generateNextFibo(3, fiboNums[1], fiboNums[0]); 
    } 

    private void generateNextFibo(int n, int lastFibo, int lastLastFibo) { 
     // Implement this recursive function to compute next fibo number. 
     fiboNums[n - 1] = lastFibo + lastLastFibo; 
     if (fiboNums.length > n) { 
      lastLastFibo = lastFibo; 
      lastFibo = fiboNums[n - 1]; 
      generateNextFibo(n + 1, lastFibo, lastLastFibo); 
     } 
    } 

    public int[] getAll() { 
     return fiboNums; 
    } 
}