파스칼 삼각형 C++의 재귀 적 프로그램 최적화

파스칼의 삼각형 값을 계산하는 재귀 함수를 만들었습니다.파스칼 삼각형 C++의 재귀 적 프로그램 최적화

최적화 할 방법이 있습니까?

파스칼의 삼각형에 대한 짧은 알림 : C (N, K) = C (N-1, K-1) + C (N-1, k)는 내 코드는 :

int Pascal(int n, int k) { 
if (k == 0) return 1; 
if (n == 0) return 0; 
return Pascal(n - 1, k - 1) + Pascal(n - 1, k); 
}

비 효율성 두 번 값을 두 번 저장한다는 것을 알 수 있습니다. (6,2) = C (5,1) + C (5,2) 예 : C (6,2) = C (5,1) + C (5,2) C 1) + C (4,2) 두 번 C (4,1)을 호출합니다

이 기능을 최적화하는 방법에 대한 아이디어가 있으십니까?

감사

출처

2011-02-23 JohnG

나는이 대신 데이터 구조처럼 "테이블"에 당신이 그들을 저장해야이 값을 다시 계산 한 후 대신 다시 실행의 재귀하여 보는 고전 문제라고 생각합니다 함수를 사용하면 테이블에서 검색을 수행합니다. 정확히 무엇을 확인했는지, 동일한 값으로 함수를 호출하는 것과 중첩되는 것은 처리 시간 낭비입니다 (고전적 프로 시저 시간/메모리 트레이드 오프). 나는 이것에 대한 솔직한 해결책이 없지만 당신은 분명히 올바른 생각을 가지고 있습니다. – shaunhusain

하나의 작은 최적화는 n == k 일 때 1을 반환하는 것으로 O (C (n, i)는 0에서 k까지))'. – Neil

@shaunhusain 감사합니다. 분명히, 나는 약간의 기억을 할당 할 것입니다! @ 네일 좋은 생각. – JohnG

다음 루틴은 재귀 적 정의와 메모를 사용하여 n-choose-k를 계산합니다. 루틴은 입니다 매우 빠르고 정확한 :

inline unsigned long long n_choose_k(const unsigned long long& n, 
            const unsigned long long& k) 
{ 
    if (n < k) return 0; 
    if (0 == n) return 0; 
    if (0 == k) return 1; 
    if (n == k) return 1; 
    if (1 == k) return n; 

    typedef unsigned long long value_type; 

    class n_choose_k_impl 
    { 
    public: 

     n_choose_k_impl(value_type* table,const value_type& dimension) 
     : table_(table), 
     dimension_(dimension/2) 
     {} 

     inline value_type& lookup(const value_type& n, const value_type& k) 
     { 
     const std::size_t difference = static_cast<std::size_t>(n - k); 
     return table_[static_cast<std::size_t>((dimension_ * n) + ((k < difference) ? k : difference))]; 
     } 

     inline value_type compute(const value_type& n, const value_type& k) 
     { 
     // n-Choose-k = (n-1)-Choose-(k-1) + (n-1)-Choose-k 
     if ((0 == k) || (k == n)) 
      return 1; 
     value_type v1 = lookup(n - 1,k - 1); 
     if (0 == v1) 
      v1 = lookup(n - 1,k - 1) = compute(n - 1,k - 1); 
     value_type v2 = lookup(n - 1,k); 
     if (0 == v2) 
      v2 = lookup(n - 1,k) = compute(n - 1,k); 
     return v1 + v2; 
     } 

     value_type* table_; 
     const value_type dimension_; 
    }; 

    static const std::size_t static_table_dim = 100; 
    static const std::size_t static_table_size = static_cast<std::size_t>((static_table_dim * static_table_dim)/2); 
    static value_type static_table[static_table_size]; 
    static bool static_table_initialized = false; 

    if (!static_table_initialized && (n <= static_table_dim)) 
    { 
     std::fill_n(static_table,static_table_size,0); 
     static_table_initialized = true; 
    } 

    const std::size_t table_size = static_cast<std::size_t>(n * (n/2) + (n & 1)); 

    unsigned long long dimension = static_table_dim; 
    value_type* table = 0; 

    if (table_size <= static_table_size) 
     table = static_table; 
    else 
    { 
     dimension = n; 
     table = new value_type[table_size]; 
     std::fill_n(table,table_size,0LL); 
    } 

    value_type result = n_choose_k_impl(table,dimension).compute(n,k); 

    if (table != static_table) 
     delete [] table; 

    return result; 
}

출처

2011-02-24 03:06:59

감사합니다 !!! 몇 가지 개념은 저에게 새로운 것입니다. "메모"하는 법을 보는 것이 좋습니다. – JohnG

이전에 반환 된 결과의 테이블을 유지 (자신의 n 및 k 값에 의해 색인); 거기에 사용 된 기술은 memoization입니다. 재귀를 반복으로 변경하고 dynamic programming을 사용하여 n 및 k 값의 삼각형을 포함하는 배열을 평가하려고하는 것보다 작게 입력 한 다음 하나의 요소 만 가져올 수 있습니다.

출처

2011-02-23 19:52:52

파스칼 삼각형 C++의 재귀 적 프로그램 최적화

답변

관련 문제