주어진 숫자 'n'까지의 피보나치 수열을 생성하는 것이 이 프로그램의 목표입니다. 피보나치 수열은 0부터 시작하여 다음과 같은 형태로 나타납니다.
0, 1, 1, 2, 3, 5, 8, 13, 21, 34
여기서 첫 두 숫자인 0과 1은 항상 고정된 값이며, 그 이후부터는 앞의 두 숫자를 더한 값이 다음 자리에 위치하게 됩니다.
0+1=1(3번째 자리) 1+1=2(4번째 자리) 2+1=3(5번째 자리) ... 이후 계속 반복
피보나치 수열의 점화식
피보나치 수열의 n번째 항 F(n)는 다음과 같은 점화식으로 정의됩니다.
Fn = Fn-1 + Fn-2 단, F(0)=0 과 F(1)=1 은 항상 고정된 초기값입니다.
피보나치 수열 생성 방법
피보나치 수열을 생성하는 방법에는 여러 가지가 있으며, 대표적으로 두 가지 접근 방식이 있습니다.
재귀(Recursive) 방식 — 함수가 정수 값마다 자기 자신을 호출하는 방식입니다. 구현이 간단하고 직관적이라는 장점이 있지만, 지수 시간 복잡도 O(2ⁿ)가 발생하기 때문에 큰 입력값에서는 성능이 급격히 저하되어 비효율적입니다.
반복문(For Loop) 방식 — for 반복문을 사용하여 수열을 생성하면 시간 복잡도를 O(n)으로 줄일 수 있습니다. 따라서 실무에서는 이 방식이 훨씬 더 효율적이며 권장됩니다.
예제
입력: n=10 출력: 0 1 1 2 3 5 8 13 21 34
알고리즘
시작
Step 1 -> 피보나치 수열 함수 선언
Void Fibonacci(int n)
변수 선언: int a=0, b=1, c, i
a와 b 출력
반복문 For i=2; i<n; ++i
c = a+b 설정
c 출력
a = b 설정
b = c 설정
반복문 종료
Step 2 -> main() 함수에서
int형 변수 n을 10으로 선언
Fibonacci(n) 호출
종료C 언어 구현 코드
#include<stdio.h>
void fibonacci(int n){
int a=0,b=1,c,i;
printf("%d까지의 피보나치 수열: ",n);
printf("\n%d %d",a,b); // 0과 1 출력
for(i=2;i<n;++i) // 0과 1은 고정값이므로 반복문은 2부터 시작
{
c=a+b;
printf(" %d",c);
a=b;
b=c;
}
}
int main(){
int n=10;
fibonacci(n);
return 0;
}실행 결과
10까지의 피보나치 수열: 0 1 1 2 3 5 8 13 21 34
위 코드에서 변수 a와 b는 각각 현재 항과 다음 항을 저장하며, 매 반복마다 두 값을 더해 새로운 항 c를 계산합니다. 그런 다음 a와 b를 한 칸씩 앞으로 이동시켜 다음 반복을 준비합니다. 이러한 방식으로 반복문 기반 구현은 재귀 호출 없이 선형 시간 안에 수열 전체를 효율적으로 생성할 수 있습니다.