591 : 함수3 - 자가진단5

첫 번째 수는 1이고 N번째 수는 (N/2)번째 수(파이썬인경우 N//2번째)와 (N-1)번째 수의 합으로 구성된 수열이 있다.

50 이하의 자연수 N을 입력받아 재귀호출을 이용하여 이 수열에서 N번째 수를 출력하는 프로그램을 작성하시오.

(1 2 3 5 7 10 13 18 …)

예제 ) 8을 입력했을 때, 18이 나온다. (8번째 수는 4번째(8/2) 수인 5와 7번째(8-1) 수인 13의 합이다.)

 

#include<stdio.h>

int arr(int n){
	if(n<=1) return 1;
	
	return arr(n/2)+arr(n-1);
}

int main(){
	int n;
	scanf("%d",&n);
	printf("%d",arr(n));
}

 

 

아직 재귀함수가 익숙치 않아서 일반 함수 호출로는 풀 수 있었지만 재귀함수로는 어려워서

 

다른 멋진 사람들이 만든 코드를 참고했다 ㅠ

코드를 읽어보며 원리를 파헤쳐보자.

 

int main(){
	int n;
	scanf("%d",&n);
	printf("%d",arr(n));
}

 

main 함수는 위와 같다.

정수 n을 선언하고 입력받는다.

 

int arr(int n){

	if(n<=1) return 1;
	
	return arr(n/2)+arr(n-1);
}

 

딱 보면 알듯이 매우 간단하고 원리 또한 간단하다.

 

위 함수에 예제인 8을 넣어보면

arr(8) = arr(4) + arr(7)이 되는데

arr(4)는 다시 arr(2)+arr(3)으로 나눠지고 이 둘은 또 다시

arr(1) + arr(1) + arr(1) + arr(2)로 나눠진다.

 

수열의 첫번째 수가 1이므로 arr(4) = 1 + 1 + 1 + 2 = 5가 된다. { arr(2)는 2가 나온다. }

arr(7)도 같은 방식으로 재귀함수를 계속 호출해 나눠지다 보면 13이 나오는 것을 확인할 수 있다.

arr(8) = arr(4) + arr(7) = 5 + 13 = 18

 

#include<stdio.h>

int arr(int n){
	if(n<=1) return 1;
	
	return arr(n/2)+arr(n-1);
}

int main(){
	int n;
	scanf("%d",&n);
	printf("%d",arr(n));
}

 

다 만들어진 코드를 보면 딱 이해가 가는데 처음 만드는 것이 정말 어려운 것 같다 ...