>

이 재귀 함수를 반복 함수로 변환하려면 어떻게해야합니까?

#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 를 사용할 수 없습니다


  • 답변 # 1

    이 함수가 느려지는 주된 이유는 기하 급수적으로 복잡하고 동일한 멤버를 계속해서 다시 계산하기 때문입니다. 가능한 치료법 중 하나는 메모 패턴 (C ++의 예제와 함께 직접 설명)입니다. 아이디어는 모든 결과를 빠른 액세스 (예 : 배열)가있는 구조에 저장하고 다시 필요할 때마다 미리 계산 된 결과를 검색하는 것입니다. 물론이 방법은 메모리 크기에 의해 제한되므로 매우 큰 숫자에는 작동하지 않습니다 ...

    귀하의 경우에는 다음과 같은 작업을 수행 할 수 있습니다 (재귀를 유지하면서 결과를 기억).

    #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은 맵의 크기 (이미 계산 된 결과 수)입니다. SO에서 이미 언급했듯이 STL의 일부이지만 표준 라이브러리의 일부가 아닌 C ++의 해시 맵도 있습니다. 해시 맵은 일정한 검색 시간을 약속하므로 (상수 값은 지정되지 않음 :) 시도 할 수도 있습니다.

  • 답변 # 2

    dynamic programming 를 사용할 수 있습니다  -H == 0이고 T == 0 일 때 아래에서 위로 시작하여 M을 계산하고 반복합니다. 다음은 피보나치 수에 대해이 작업을 수행하는 방법을 설명하는 링크입니다. 문제와 매우 유사합니다.

  • 답변 # 3

    이 항목을 확인하십시오. 재귀 버전과 재귀 버전은 지금까지 입력 한 모든 입력에 대해 동일한 결과를 제공했습니다. 중간 결과를 행렬로 유지하는 것이 좋습니다. 여기서 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));
    }
    
    

  • 답변 # 4

    시퀀스의 n 번째 (귀하의 경우 (m, n) 번째) 요소에 대한 공식을 모르는 경우 가장 쉬운 방법은 스택을 사용하여 재귀를 시뮬레이션하는 것입니다.

    코드는 다음과 같아야합니다.

    #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;
    }
    
    

  • 답변 # 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 (x, y)를 계산하는 방법

    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];
    }
    
    

관련 자료

  • 이전 php - Imagemagick 애니메이션 GIF 크기 최적화
  • 다음 HTML5를 사용하여 캔버스 내에서 드래그 앤 드롭 기능