Pascal Üçgen Yinelemeli Program optimizasyonu C++

Question

Pascal'ın üçgen değerlerini hesaplamak için özyinelemeli bir işlev geliştirdim.

Bunu optimize etmenin bir yolu var mı?

Pascal üçgeni hakkında kısa bir hatırlatma: C (n, k) = C (n-1, k-1) + C (n-1, k) My kodudur:

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

verimsizlik Görüyorum ki, bazı değerleri iki kez depolar. Örnek: ° C (6,2) = C (5,1) + C (5,2) ° C (6,2) = C (4,0) + C (4,1) + C (4, 1) + C (4,2) , C (4,1) iki kere

'u arayacaktır. Bu işlevi nasıl optimize edeceğinize dair bir fikriniz var mı?

Teşekkür

Answer 1

Aşağıdaki rutin, n-select-k'yi özyinelemeli tanımlamayı ve notlamayı kullanarak hesaplayacaktır. Rutin son derece hızlı ve doğru:

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

Answer 2

önce döndürülen sonuç bir tablo tutun (kendi n ve k değerler tarafından dizine); Kullanılan teknik memoization. Yinelemeyi yinelemeli olarak da değiştirebilir ve n ve değerlendirmeye çalıştığınızdan daha küçük k değerlerini içeren bir diziyi doldurmak için dynamic programming'u kullanabilirsiniz, daha sonra yalnızca bir öğe alın.