재귀 구현

Question

정수 k가 합계로 표시 될 수있는 여러 가지 방법의 수를 찾는 순환 방법입니다. 각 피연산자는 n보다 작은 정수입니다. 알고리즘을 도와주십시오. 내가

Answer 1

기본적으로이 문제에 재귀 솔루션을 생각 할 수없는 나는, 내 첫 번째 아이디어는 것 다음

int numberOfWays(int x) 
{ 
    if(x <= 1) 
     return 0; 
    if(x == 2) 
     return 1; 
    // else: 
    int res = 0; 
    int i; 
    for(i = 1; i <= x/2; i++) 
     res += numberOfWays(x - i); 
    return res; 
} 

나는 그것을 시험과 생각의 몇 줄거야하지만 약이다 그것. 설명의

어쩌면 몇 마디 ... 분명히

, 정수 < 1의 합으로 일을 작성하는 방법이 없으며, 정수 < 2의 합으로 2를 작성하는 하나 개의 방법이 : 2 = 1 + 1

거기부터 재미있는 일이 있습니다. 모든 정수 x> 2는 (x-1) + 1로 쓰여질 수 있습니다. 우리는 이제 여러 가지 방법을 얻습니다. (x-1)은 정수의 합으로 쓸 수 있습니다. < (x-1) 에. 결국, 우리가 거기부터 1

를 반환합니다 (XN) = 2, 도달 할 것입니다, 우리는 우리가 숫자를 나타내는의 발견 방법의 수를 합산, 위쪽으로 돌아가서, 봐라 :