從遞歸到迭代函數

Question

我想從f_rec（遞歸函數）到f_iter（迭代函數），但我不能。 （我的邏輯是創建一個循環計算f_rec的結果（N-1）。

int f_rec(int n) 
{ 
if(n>=3) 
    return f_rec(n-1)+2*f_rec(n-2)+f_rec(n-3); 
else 
    return 1; 
} 

int f_iter(int n) 
{ 
} 

我也認爲我對f_rec時間複雜度爲3 n次方，請糾正我，如果我錯了。

謝謝

Answer 1

以下是想法

int first=1,second=1,third=1; /* if n<=3 then the respective is the answer */ 
    for(i=4;i<=n;i++) 
    { 
    int next=first+2*second+third; 
    first=second; 
    second=third; 
    third=next; 
    } 
    cout<<"The answer is "<<next<<endl; 

內存O（1）和時間爲爲O（n）。

編輯 你的遞歸函數確實是在指數時間，以保持它的線性就可以使數組F [N]使用 ，並使用記憶化。首先將F []初始化爲-1。

int f_rec(int n) 
    { 
     if(n>=3) 
     { 
      if(F[n]!=-1)return F[n]; 

      F[n]=f_rec(n-1)+2*f_rec(n-2)+f_rec(n-3); 
      return F[n];  
     } 

     else 
      return 1; 

}

Answer 2

只要保持三個變量與a，b和c都等於把它們卷在

• 啓動1
• 在每一步new_a是a + 2*b + c
• 翻轉：new_c是b，new_b是a
• 重複所需的步數

Answer 3

你總是可以從過去三年計算的最新值。剛開始從一開始計算，並始終保存最後三：

int f_iter (int n) { 
    int last3[3] = {1,1,1}; // The three initial values. Use std::array if C++ 

    for (int i = 3; i <= n; ++i) { 
     int new_value = last3[0] + 2 * last3[1] + last3[2]; 
     last3[0] = last3[1]; 
     last3[1] = last3[2]; 
     last3[2] = new_value; 
    } 
    return last3[2]; 
} 

這種解決方案需要O（1）內存和O（n）的運行時間。可能有一個公式可以用O（1）（最有可能）來計算這個公式，但我想爲了演示迭代技術，這是要走的路。

您的解決方案具有指數運行時間：每個額外的級別都會生成三個評估，因此您最終會得到O（3^n）操作和堆棧內存。

Answer 4

有兩個選項：

1）使用離散數學課程和推導公式。複雜性（如果@Sasha提到它的話）對於內存和算法都是O（1）。沒有循環，沒有遞歸，只是公式。

首先您需要找到特徵多項式並計算其根。假設我們的根源是r1，r2，r3，r4。那麼第n個元素是F(n) = A * r1^n + B * r2^n + C * r3^n + D * r4^n，其中A，B，C，D是一些未知係數。你可以使用你的初始條件找到這些係數（F(n) = 1 n < = 3）。

如果需要，我可以在俄羅斯解釋。

2）使用額外的變量來存儲中間值。就像@ 6052已經回答（他的回答非常快:)）。

Answer 5

矯枉過正的位，但是這可以通過讓所述變量代表在展開循環變化，（鏈接）合併什麼Duff's device進入循環得到進一步的優化：

int f_iter(int n){ 
int a=1, b=1, c=1; 
    if(n < 3) 
     return(1); 
    switch(n%3){ 
     for(; n > 2; n -= 3){ 
      case 2: 
       b = c + 2*a + b; 
      case 1: 
       a = b + 2*c + a; 
      case 0: 
       c = a + 2*b + c; 
     } 
    } 
    return c; 
}