[C언어] K-보나치

K-보나치 (K-bonacci)

---

​K-보나치는 피보나치 함수를 아주 조금 확장한 형태이다.

K-보나치 수열의 정의는 다음과 같다.

If n>k Fn = Fn-1 + Fn-2 + … + Fn-k else F1 = F2 = F3 .. = Fk = 1

​

피보나치 수열은 K=2인 경우이고

4-보나치 수열은 아래와 같다.

If n>4 Fn = Fn-1 + Fn-2 + Fn-3 + Fn-4 else F1 = F2 = F3 = F4 = 1

​

K-보나치 수열의 n번째 값을 구하는 프로그램은 recursion(재귀)를 이용하면 쉽게 코드를 구현할 수 있다.

K값은 고정되어 변하지 않지만 n번째값을 구하기 위해

1~n-1까지의 합을 구하면 되기 때문에 n값을 변화시키는 재귀함수가 필요하다.

​

 

 

 

 

 

코드

---

#include <stdio.h>

int k_bonacci(int k, int n) {
	int i, total = 0;

	if (k >= n)        // 재귀 종료 조건
		return 1;
	else {
		for (i = n - 1; i >= n - k; i--)
			total += k_bonacci(k, i);
		return total;
	}
}

int main(void) {
	int k, n;
	scanf_s("%d %d", &k, &n);

	printf("%d-보나치의 %d번째 값은 %d", k, n, k_bonacci(k, n));
}

​

​

코드 결과

​

* Test Case

① k=4     n=2     F2=1

② k=4     n=6     F6=7

③ k=6     n=10   F10=41

​

​

​

K-보나치 끝!