優化遞歸函數

Question

我創建一個程序，它返回它完美對於n值很小隻使用1，2，6和13得到一個數（n）所需資金的數量最少，但一旦n得到的值爲200，這會讓程序花費太多時間來計算結果。

因此，我有兩個問題：

有沒有什麼辦法讓遞歸更快？

2.我應該避免使用遞歸和使用循環呢？

這裏的註釋代碼：

#include <iostream> 
#define MAX 500000 

using namespace std; 

void cal(int inp, int &mini, int counter = 0); 

int main (void) 
{ 
    //Gets input 
    int n; 
    cin >> n; 

    //Defines mini as the MAX result we can get 
    int mini = MAX; 

    //Calls the function 
    cal(n, mini); 

    //Prints the best result 
    cout << mini << endl; 

    return 0; 
} 

void cal(int inp, int &mini, int counter) 
{ 
    //Breaks recursion if it finds an answer 
    if(!inp) 
    { 
     if(counter<mini) mini = counter; 
     return; 
    } 

    //Breaks recursion if the input is negative 
    //or the counter is more than the best result 
    else if((inp<0) || (counter>mini)) return; 

    //Counts amount of recursions 
    counter++; 

    //Tries every combination 
    cal(inp-13, mini, counter); 
    cal(inp-6, mini, counter); 
    cal(inp-2, mini, counter); 
    cal(inp-1, mini, counter); 

    return; 
} 

謝謝

Answer 1

您可以使用DP（動態規劃）的方法來解決你的問題。這是衆所周知Coins Problem

Answer 2

的問題是你的蠻力。讓我建議一些更好的東西：

預備：如果你有兩個1，最好用一個2.如果你有三個2，最好用一個6.如果你有十三個6，那會更好使用六十三個。

所以任何admissable總和將總是看起來像n = 13m+k其中k寫成的1，2和6的總和隨着預賽中，我們知道，最佳的總和k絕不會超過1+2*2+12*6 = 77。 （反向不成立。沒有任何數量低於78的情況下儘量當然13S寫的。）所以暴力破解這些是不夠好。然後您可以使用查找表。

這仍然可以進一步優化，但它不應該拆毀在200

假設你已經發現你的第一個77項（可以及優化），你可以做到這一點（仍未經優化的;-) ：

int num_13 = ((n-78)/13) + 1; 
int sum_length = MAX; 
for (i = num_13; i*13 < n; i++) { 
    int tmp = entries_77[n-i*13]+i; 
    if (tmp < sum_length) { 
     num_13 = i; 
     sum_length = tmp; 
    } 
} 

我會更快編譯的陣列的等價類模13中，由於對於任何給定的等價類任何數量超過78將具有相同的k。

Answer 3

你的遞歸需要一個記憶化，以避免重複計算。並且不需要遞歸的第二個和第三個參數。我已更新並對您的代碼進行了解釋。如果您有任何困惑，請告訴我。

#include <iostream> 
#include <string.h> 
#define INF 999999 

using namespace std; 

int cal(int inp); 
int mem[502]; 
int main (void) 
{ 
    //Gets input 
    int n; 
    cin >> n; 

    //initialzing the array for using with memoization 
    memset(mem,-1,sizeof(mem)); 

    //Calls the function 
    //Prints the best result 
    cout << cal(n) << endl; 

    return 0; 
} 

//returns the minimum quantity of sum operations to get inp. 
int cal(int inp) 
{ 
    //Breaks recursion if it finds an answer. 
    //Return cost 0. As in this stage no processing was done. 
    if(!inp) 
     return 0; 

    // Returning infinite cost for invalid case. 
    if(inp < 0) 
     return INF; 

    int _ret = mem[inp]; 

    // If already visited here before then no need to calcuate again. 
    // Just return previous calculation. This is called memoisation. 
    // If not visited then _ret would have equal to -1. 
    if(_ret >=0) 
     return _ret; 

    _ret = INF; 

    //Tries every combination and takes the minimum cost. 
    _ret = min(_ret, cal(inp-13)+1); 
    _ret = min(_ret,cal(inp-6)+1); 
    _ret = min(_ret,cal(inp-2)+1); 
    _ret = min(_ret,cal(inp-1)+1); 

    // Updating the value so that can be used for memoization. 
    mem[inp] = _ret; 

    return _ret; 
} 

這也適用於更大的數字。複雜性是4 * n。