像算法

Question

斐波納契對於F（N）= F（N - 1）+ F（N - 2^10），當0 < = N < 2^10中，F（N）= 1，

寫一個函數來計算F（N）。（不使用遞歸方法）

int compute_f(int n) 
{ 
    int result = 0; 

    ... 

    return result 
} 

想知道是否有任何有效的方式來辦？

Answer 1

你可以遵循斐波那契的相同想法，並做Dynamic Programming。

僞代碼：

if n < 0: 
    //throw some exception 
arr = new int[max(1024,n+1)] 
for i = 0 to 1024: 
    arr[i] = 1 
for i = 1024 to n+1: 
    arr[i] = arr[i-1] + arr[i-1024] 
return arr[n] 

將其轉換爲實際的代碼是留給你。獎勵：您可以通過保存1024個大小的數組並使用O（1）額外的空間來操作它，並在不改變時間複雜度的情況下操縱它並記住您當前的位置（使用modolus運算符）。

Answer 2

這是我的版本，類似斐波那契的遞歸版本。

int compute_f(int n) 
{ 
    if(n < 0) 
     return -1; //Error 
    if(n <= 1024) 
     return 1; 
    return (compute_f(n-1) + compute_f(n-1024)); 
}