2016-06-17 60 views
1

讓我們考慮使用動態規劃實現斐波那契數列。使用動態規劃的斐波那契數列

// Fibonacci Series using Dynamic Programming 
class fibonacci 
{ 
static int fib(int n) 
{ 
    /* Declare an array to store Fibonacci numbers. */ 
int f[] = new int[n+1]; 
int i; 

/* 0th and 1st number of the series are 0 and 1*/ 
f[0] = 0; 
f[1] = 1; 

for (i = 2; i <= n; i++) 
{ 
    /* Add the previous 2 numbers in the series 
    and store it */ 
    f[i] = f[i-1] + f[i-2]; 
} 

return f[n]; 
} 

public static void main (String args[]) 
{ 
    int n = 9; 
    System.out.println(fib(n)); 
} 
} 

我們使用動態編程,以便不會發生遞歸工作的重複。但是,在每次調用該函數時,都會生成一個新數組。那麼這個算法怎麼會被說成是更優化的呢?

+0

每次? 。我猜這個數組會在每個函數調用中創建一次。假設你想找到第100個斐波納契數。所以一個100的數組將只創建一次來存儲數字。 – FallAndLearn

+1

如果你不想在每次調用'fib'時創建數組,請不要在'fib'中創建它。 – zmbq

+0

另外,添加遞歸函數也會在創建樹時使用O(n)空間。 – FallAndLearn

回答

1

一個優化只會保存最後2個值而不是所有結果。您不需要存儲所有結果。

您還可以在O(n)的遞歸編寫斐波納契數列:

int fib(int n1, int n2, int counter) 
{ 
    if(counter == 0) 
    { 
     return n2; 
    } 
    else 
    { 
     return fib(n2,n2 + n1,counter-1); 
    } 
} 

//to start: 
int result = fib(0,1,100); //gives you the 100 fibonacci value 

此代碼遞歸運行,易於閱讀。您不必初始化數組或其他東西。

或者你可以使用非遞歸選項:如果你想存儲你的結果

int fib(int number) 
{ 
    int n1 = 0; 
    int n2 = 1; 
    int temp; 
    for(int i = 0; i< number;i++) 
    { 
     temp = n1 + n2; 
     n1 = n2; 
     n2 = temp; 
    } 
    return n2; 
} 

,您必須將數組初始化FIB功能之外:

// Fibonacci Series using Dynamic Programming 
class fibonacci 
{ 
    /* Declare an array to store Fibonacci numbers. */ 
    int f[]; 

    static void init(int n) 
    { /* 0th and 1st number of the series are 0 and 1*/ 
     f = new int[n+1];    
     f[0] = 0; 
     f[1] = 1; 
    } 

    static int fib(int n) 
    { 
     int i; 

     for (i = 2; i <= n; i++) 
     { 
      /* Add the previous 2 numbers in the series 
      and store it */ 
      f[i] = f[i-1] + f[i-2]; 
     } 

     return f[n]; 
    } 

    public static void main (String args[]) 
    { 
     int n = 9; 
     init(n); 
     System.out.println(fib(n)); 
    } 
} 
+0

將結果保存到一個數組只有有意義,如果以後使用它們 – Thomas

+0

這回答了「我如何編寫O(n)整數算術運算,O(1)附加整數存儲Fibonacci函數」這個問題,但我不知道我不認爲這就是問題所在。 –

+0

你是對的......因爲我編輯了我的回答thx @PaulHankin – Thomas