반복 관계 : 반복 관계 쓰기

Question

이 알고리즘에 대한 반복 관계를 쓰려고합니다.하지만 "루트"변수와 혼동을 겪고 있습니다. 누구든지 나를 도와 주거나 더 나은 재귀 알고리즘을 계산 해줄 수 있습니까? 노드가있는 가능한 이진 트리 수?

Algorithm countTrees(n) { 
    if(n<=1) then return 1 
    else { 
     sum = 0 
     for root=1 to root<= n do { 
      left = countTrees(root-1) 
      right = countTrees(n-root) 
      sum = sum+(left*right) 
     } 
     return sum 
    } 
} 

내가 지금까지 작성한 그러나 나는이 문제를 해결하기 위해 루트를 처리하는 방법을 모르겠어요.

T (N) = N [T (루트-1) + T (N 루트)]

Answer 1

에 코드가 이미 단순한 알고리즘으로 표현 이진 트리의 개수에 대한 점화식이다. 나는 당신이 루프를 통해 합계를 가졌기 때문에 붙어 있었을 것입니다. 여기가 0..N-1을 더 표준으로 1..N 변경 루프 값을 표준 수학 notation--에 있습니다 손으로 쓰기

C(0) = C(1) = 1 
C(n) = sum(C(i) * C(n-i-1) for i = 0...n-1) 

(또는 유액에) 당신은 좋겠 sum보다는 합계 기호를 사용하십시오. 그러나 논리적으로는 같습니다.

이것은 일반적으로 C(1) 사례가 명시 적으로 나열되지는 않지만 반복적 인 관계이며, 링크 된 위키피디아 페이지에는 반복 관계에 대한 닫힌 형식의 솔루션과 그 정확성의 증명이 포함됩니다.