파스칼의 삼각형 값을 계산하는 재귀 함수를 만들었습니다.파스칼 삼각형 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)을 호출합니다
이 기능을 최적화하는 방법에 대한 아이디어가 있으십니까?
감사
다음 루틴은 재귀 적 정의와 메모를 사용하여 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;
}
감사합니다 !!! 몇 가지 개념은 저에게 새로운 것입니다. "메모"하는 법을 보는 것이 좋습니다. – JohnG
이전에 반환 된 결과의 테이블을 유지 (자신의 n 및 k 값에 의해 색인); 거기에 사용 된 기술은 memoization입니다. 재귀를 반복으로 변경하고 dynamic programming을 사용하여 n 및 k 값의 삼각형을 포함하는 배열을 평가하려고하는 것보다 작게 입력 한 다음 하나의 요소 만 가져올 수 있습니다.
나는이 대신 데이터 구조처럼 "테이블"에 당신이 그들을 저장해야이 값을 다시 계산 한 후 대신 다시 실행의 재귀하여 보는 고전 문제라고 생각합니다 함수를 사용하면 테이블에서 검색을 수행합니다. 정확히 무엇을 확인했는지, 동일한 값으로 함수를 호출하는 것과 중첩되는 것은 처리 시간 낭비입니다 (고전적 프로 시저 시간/메모리 트레이드 오프). 나는 이것에 대한 솔직한 해결책이 없지만 당신은 분명히 올바른 생각을 가지고 있습니다. – shaunhusain
하나의 작은 최적화는 n == k 일 때 1을 반환하는 것으로 O (C (n, i)는 0에서 k까지))'. – Neil
@shaunhusain 감사합니다. 분명히, 나는 약간의 기억을 할당 할 것입니다! @ 네일 좋은 생각. – JohnG