[c언어]피보나치 수열 함수, for 반복문 으로 풀어보기

안녕하세요 modernAlchemist 의 H 입니다. 오늘은 피보나치 수열을 풀어보겠습니다. 

피보나치 수열이란 F0​=0, F1​=1, Fn+2​=Fn+1​+Fn​ 이다. 이때 초항과 그 다음 항을 0과 1이 아닌 숫자 

두개를 설정하게 되면 루카스 수열이 되므로 주의해야한다.

 

예를 들어 16번째 항까지만 나열해 보자면 

(0), 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987 이된다. 

 

int fibo(int n) {
	int result;

	if (n == 0) {
		result = 0;
	}
	else if (n == 1) {
		result = 1;
	}
	else {
		result = fibo(n - 1) + fibo(n - 2);
	}

	return result;
}

재귀 함수의 형태로 표현을 해줄 수 있다. 

만약 이게 어렵다면 아래와 같은 형태로 반복문으로도 표현이 가능하다. 

	int fn_2 = 0, fn_1 = 1, fn;
	int start = 2, index;

	if (n == 0) {
		return 0;
	}
	else if (n == 1) {
		return 1;
	}
	else {
		for (index = 2; index <= n; index++) {
			fn = fn_1 + fn_2;
			fn_2 = fn_1;
			fn_1 = fn;
		}
	}

해당 식을 main 함수에 표현해본다면 

//재귀적인 정의 피보나치 순열 
// fnI = fn-1 + fn-2
//f0 = 0
//f1 = 1

#define _CRT_SECURE_NO_WARNINGS 
#include <stdio.h>
int fibo(int n);
int forfibo(int n);

int main(void) {
	int result = 0;
	result = fibo(10);
	printf("10번째 피보나치 수열 =%d", result);

	printf("\n");

	for (int i = 10; i < 11; i++) {
		result = forfibo(i);
		printf("%d", result);
	}

	return 0;
}

// n >= 2 
int forfibo(int n) {
	//fn = fn-1 + fn-2 
	// n	f0 + f1 -> f2
	//		f1 + f2 -> f3 
	//		f2 + f3 -> f4 

	int fn_2 = 0, fn_1 = 1, fn;
	int start = 2, index;

	if (n == 0) {
		return 0;
	}
	else if (n == 1) {
		return 1;
	}
	else {
		for (index = 2; index <= n; index++) {
			fn = fn_1 + fn_2;
			fn_2 = fn_1;
			fn_1 = fn;
		}
	}

	return fn;
}

int fibo(int n) {
	int result;

	if (n == 0) {
		result = 0;
	}
	else if (n == 1) {
		result = 1;
	}
	else {
		result = fibo(n - 1) + fibo(n - 2);
	}

	return result;
}