Преобразуйте эту рекурсивную функцию в итеративный

Question

Как преобразовать эту рекурсивную функцию в итеративную функцию?

#include <cmath> 

int M(int H, int T){ 
    if (H == 0) return T; 
    if (H + 1 >= T) return pow(2, T) - 1; 
    return M(H - 1, T - 1) + M(H, T - 1) + 1; 
} 

Ну это код 3 строки, но это очень трудно для меня, чтобы преобразовать это в итерационной функции. Потому что он имеет 2 переменные. И я ничего не знаю о Stacks, поэтому я не смог его преобразовать.

Моя цель для этого - это скорость функции. Эта функция слишком медленная. Я хотел использовать map, чтобы сделать это быстрее, но у меня есть 3 переменные M, H и T поэтому я не мог использовать map

Answer 1

Основная причина, почему эта функция является медленным, потому что он имеет экспоненциальную сложность, и он продолжает пересчитывать те же самые члены снова и снова. Одним из возможных способов лечения является memoize pattern (удобное объяснение с примерами на C++ here). Идея состоит в том, чтобы хранить каждый результат в структуре с быстрым доступом (например, массив), и каждый раз, когда вам это нужно, извлекайте уже предварительно вычисленный результат. Конечно, этот подход ограничен размером вашей памяти, поэтому он не будет работать для чрезвычайно больших чисел ...

В вашем случае мы могли бы сделать что-то подобное (сохраняя рекурсию, но сохраняя мемуары) :

#include <cmath> 
#include <map> 
#include <utility> 

std::map<std::pair<int,int>,int> MM; 

int M(int H, int T){ 
    std::pair<int,int> key = std::make_pair(H,T); 
    std::map<std::pair<int,int>,int>::iterator found = MM.find(key); 
    if (found!=MM.end()) return found->second; // skip the calculations if we can 
    int result = 0; 
    if (H == 0) result = T; 
    else if (H + 1 >= T) result = pow(2, T) - 1; 
    else result = M(H - 1, T - 1) + M(H, T - 1) + 1; 
    MM[key] = result; 
    return result; 
} 

Относительно сложности времени, карты C++ являются карты дерева, поэтому поиск существует порядка N * Log (N), где N является размером карты (количество результатов, которые были уже вычисленным) , Существуют также хеш-карты для C++, которые являются частью STL, но не являются частью стандартной библиотеки, как уже было mentioned on SO. Карта хэша обещает постоянное время поиска (значение константы не указано, хотя :)), поэтому вы также можете попробовать.

Answer 2

Если вы не знаете формулу для п-го (в вашем случае (т, п) - th) элемента последовательности, самым простым способом является имитация рекурсии с использованием стека.

Код должен выглядеть следующим образом:

#include <cmath> 
#include <stack> 

struct Data 
{ 
public: 
    Data(int newH, int newT) 
     : T(newT), H(newH) 
    { 

    } 

    int H; 
    int T; 
}; 

int M(int H, int T) 
{ 
    std::stack<Data> st; 

    st.push(Data(H, T)); 

    int sum = 0; 

    while (st.size() > 0) 
    { 
     Data top = st.top(); 
     st.pop(); 

     if (top.H == 0) 
      sum += top.T; 
     else if (top.H + 1 >= top.T) 
      sum += pow(2, top.T) - 1; 
     else 
     { 
      st.push(Data(top.H - 1, top.T - 1)); 
      st.push(Data(top.H, top.T - 1)); 
      sum += 1; 
     } 
    } 

    return sum; 
} 

Answer 3

можно использовать dynamic programming - начать снизу вверх, когда H == 0 и T == 0 высчитывает M и перебирать их. вот link, объясняющий, как это сделать для чисел Фибоначчи, которые очень похожи на вашу проблему.

Answer 4

Проверьте это, рекурсивные и не рекурсивные версии дали равные результаты для всех входов, которые я дал до сих пор. Идея состоит в том, чтобы сохранить промежуточные результаты в матрице, где H - индекс строки, T - индекс col, а значение - M (H, T). Кстати, вы можете вычислить его один раз, а затем просто получить результат от матрицы, так что вы будете иметь производительность O (1)

int array[10][10]={{0}}; 

int MNR(int H, int T) 
{ 
    if(array[H][T]) 
     return array[H][T]; 

    for(int i =0; i<= H;++i) 
    { 
     for(int j = 0; j<= T;++j) 
     { 
      if(i == 0) 
       array[i][j] = j; 

      else if(i+1 > j) 
       array[i][j] = pow(2,j) -1; 

      else 
       array[i][j] = array[i-1][j-1] + array[i][j-1] + 1; 

     } 
    } 

    return array[H][T]; 
} 

int M(int H, int T) 
{ 
    if (H == 0) return T; 
    if (H + 1 >= T) return pow(2, T) - 1; 
    return M(H - 1, T - 1) + M(H, T - 1) + 1; 
} 

int main() 
{ 
    printf("%d\n", M(6,3)); 
    printf("%d\n", MNR(6,3)); 
} 

Answer 5

Вы можете рассчитывать, используя один демонический массив.Немного теории,

Let F(a,b) == M(H,T) 
1. F(0,b) = b 
2. F(a,b) = 2^b - 1, when a+1 >= b 
3. F(a,b) = F(a-1,b-1) + F(a,b-1) + 1 

Let G(x,y) = F(y,x) ,then 
1. G(x,0) = x     // RULE (1) 
2. G(x,y) = 2^x - 1, when y+1 >= x // RULE (2) 
3. G(x,y) = G(x-1,y-1) + G(x-1,y) + 1 // RULE(3) --> this is useful, 
// because for G(x,y) need only G(x-1,?), i.e if G - is two deminsions array, then 
// for calculating G[x][?] need only previous row G[x-1][?], 
// so we need only last two rows of array. 

// Here some values of G(x,y) 
4. G(0,y) = 2^0 - 1 = 0 from (2) rule. 
5. G(1,0) = 1 from (1) rule. 
6. G(1,y) = 2^1 - 1 = 1, when y > 0, from (2) rule. 

G(0,0) = 0, G(0,1) = 0, G(0,2) = 0, G(0,3) = 0 ... 
G(1,0) = 1, G(1,1) = 1, G(1,2) = 1, G(1,3) = 1 ... 

7. G(2,0) = 2 from (1) rule 
8. G(2,1) = 2^2 - 1 = 3 from (2) rule 
9. G(2,y) = 2^2 - 1 = 3 when y > 0, from (2) rule. 

G(2,0) = 2, G(2,1) = 3, G(2,2) = 3, G(2,3) = 3, .... 

10. G(3,0) = 3 from (1) rule 
11. G(3,1) = G(2,0) + G(2,1) + 1 = 2 + 3 + 1 = 6 from (3) rule 
12. G(3,2) = 2^3 - 1 = 7, from (2) rule 

Теперь, как вычислить эту G (х, у)

int M(int H, int T) { return G(T,H); } 

int G(int x, int y) 
{ 
    const int MAX_Y = 100; // or something else 
    int arr[2][MAX_Y] = {0} ; 
    int icurr = 0, inext = 1; 

    for(int xi = 0; xi < x; ++xi) 
    { 
      for(int yi = 0; yi <= y ;++yi) 
      { 
      if (yi == 0) 
       arr[inext][yi] = xi; // rule (1); 
      else if (yi + 1 >= xi) 
       arr[inext][yi] = (1 << xi) - 1; // rule (2) 
      else arr[inext][yi] = 
       arr[icurr][yi-1] + arr[icurr][yi] + 1; // rule (3) 

      } 
      icurr ^= 1; inext ^= 1;   //swap(i1,i2); 
    } 
    return arr[icurr][y]; 
} 

// Или некоторые оптимизации

int G(int x, int y) 
{ 
    const int MAX_Y = 100; 
    int arr[2][MAX_Y] = {0}; 
    int icurr = 0, inext = 1; 

    for(int ix = 0; ix < x; ++ix) 
    { 
     arr[inext][0] = ix; // rule (1) 

     for(int iy = 1; iy < ix - 1; ++ iy) 
      arr[inext][iy] = arr[icurr][iy-1] + arr[icurr][iy] + 1; // rule (3) 

     for(int iy = max(0,ix-1); iy <= y; ++iy) 
      arr[inext][iy] = (1 << ix) - 1; // rule(2) 

     icurr ^= 1 ; inext ^= 1; 
    } 

    return arr[icurr][y]; 
}