[추석맞이 코딩챌린지①] 피보나치수 c

문제 출처 : https://cafe.naver.com/codeuniv?iframe_url=/ArticleList.nhn%3Fsearch.clubid=30026525%26search.menuid=193%26search.boardtype=L 

코딩 커뮤니티 - 코뮤니티 [파이썬/... : 네이버 카페

 

코뮤니티에서 열리는 추석맞이 코딩 챌린지에 참여했다.

참여 방법은 간단하다. 문제를 풀고 풀이와 코드를 블로그 혹은 카페에 자유롭게 게시하고, 댓글에 주소를 남기면 된다.

추석을 맞아 쉬는 것도 좋지만, 가벼운 문제들이라도 꾸준히 풀자는 좋은 취지인 것 같다.

문제

피보나치 수열은 수학에서 아래의 점화식으로 정의되는 수열이다.

피보나치 수는 0 번째 숫자인 0과 첫 번째 숫자인 1로 시작하며,

두 번째 숫자는 0 번째 수와 첫 번째 수의 합인 0 + 1 = 1,

세 번째 숫자는 첫 번째 수와 두 번째 수의 합인 1 + 1 = 2 의 값을 가진다.

​

숫자 n을 입력받아 피보나치 수열의 n번째 숫자를 출력하는 프로그램을 작성해보세요.

​

조건 1 : 입력받는 숫자 n은 2 이상의 자연수입니다.

조건 2 : n > 2인 피보나치 수에서, n번째 수 = (n - 2)번째 수 + (n - 1)번째 수 입니다.

조건 3 : 피보나치 수열을 나열하면 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ... 입니다.

​

입/출력 예시

👉 입력 예시

10

👉 출력 예시

55

​

👉 입력 예시

15

👉 출력 예시

610

​

풀이

n을 입력받으면 n에 대한 피보나치 수를 출력하는 문제이다.

재귀 혹은 피보나치를 배운다면 기본적으로 짜는 코드로, 알고리즘 문제를 풀다 보면,
이를 응용한 수학/재귀 문제가 종종 나온다.

우선 피보나치 재귀의 기저 사례로 n이 0일 때는 0을 반환하고, n이 1일 때는 1을 반환한다.

이후, n에 대한 피보나치 수는 fibonacci(n-1)+fibonacci(n-2)의 점화식을 이용해 재귀 함수를 완성한다.

 

코드

#include <stdio.h>
#include <stdlib.h>

int fibonacci(int n) {
	if (n == 0) {
		return 0;
	}
	if (n == 1) {
		return 1;
	}
	return fibonacci(n - 1) + fibonacci(n - 2);
}

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

	return 0;
}