열린 양식 및 닫힌 양식

Question

열린 양식의 상응하는 닫힌 양식으로 변환 할 수있는 방법. 또한 일반적으로 사용되는 닫힌 양식 인 은 일반적으로 효율적으로 사용됩니다.

Answer 1

당신은 재귀 함수와 수학에 대해 이야기하고 있다고 생각합니다.

다음 합계 회귀 함수를 고려하십시오.

sum(0) = 0 
sum(i) = sum(i-1) + i 

이 양식은 닫히지 않았습니다. 닫힌 양식은 sum(n) = (n+1)*n/2이며 + - * /, 전원 및 경우에 따라 계승과 같은 기본 작업 만 사용합니다.

질문에 대한 오픈 폼 수식을 닫힌 폼으로 변환하는 방법. 대답은 입니다. 열린 양식 중 일부는 동등한 닫힌 양식이 없기 때문에 모든 열린 양식을 닫힌 양식으로 변환하는 일반적인 규칙은 없습니다.

Concrete Mathematics을 참조하십시오.이 주제를 진지하게 치료할 수 있습니다. 이 책의 주요 목표는 재귀 함수/열린 형식의 큰 계열을 닫힌 형식으로 변환하는 것입니다.

Answer 2

열린 형태은 일반적으로 해결 될 수식으로 주어집니다. 예를 들어,

a(0) = 1   -- base case 
a(n) = b * a(n-1) -- recurrence relation 

이 폐쇄 형태로 변환하려면 점화식를 해결 . 이 경우, 반복 교체는 상기베이스 케이스 일본어 반면하면

a(n) = b * a(n-1) = b * b + a(n-2) = ... = b * b * ... * b * a(0) = b^n 

힘이 (N 로그온 즉 비례) N에서 대수 시간에서 평가 될 수 있기 때문에 이것은 더 효율적인 제공에 도달 할 때까지 반복 관계는 n에서 선형 시간이 걸립니다.

되풀이 관계를 해결하는 데 사용되는 많은 기술이 있습니다. 몇 가지 예는 wikipedia article에서 찾을 수 있습니다. 그러나 모든 재발 관계가 해결 될 수는 없다는 사실을 깨닫는 것이 중요합니다. 실제로 대부분은 풀 수 없습니다 (프로그래밍이 중요한 이유입니다).