Оптимизация рекурсивной функции

Question

Я создаю программу, которая возвращает наименьшее количество сумм, необходимых для получения числа (n), используя только 1, 2, 6 и 13. Он отлично работает при малых значениях n, но один раз n получает значения, равные 200, для вычисления результата требуется слишком много времени.

Поэтому, у меня есть два вопроса:

1. Есть ли способ сделать рекурсию быстрее?

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 (Dynamic Programming) для решения вашей проблемы. Хорошо известно Coins Problem

Answer 2

Проблема ваша грубая сила. Позвольте мне предложить что-то получше:

Предварительные сведения: Если у вас есть два 1s, всегда лучше использовать 2. Если у вас есть три 2s, лучше использовать 6. Если у вас тринадцать 6 секунд, лучше использовать шесть триртов.

Таким образом, любая сумма всегда Допустимое будет выглядеть n = 13m+k где k записывается в виде суммы 1, 2 и 6. С предварительными, мы знаем, что для оптимальной суммы k никогда не будет превышать 1+2*2+12*6 = 77. (Обратное не выполняется. Не любое число ниже 78 лучше всего писать без 13-го курса, конечно.) Так грубо заставляя их достаточно хорошо. Затем вы можете использовать таблицу поиска.

Это еще может быть оптимизирована дальше, но она не должна тормоза вниз на 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.