1. 피보나치 수열

피보나치 수열 문제

1, 1, 2, 3, 5, 8, 13, 21 ...

n항과  (n+1)항을 더하는 알고리즘을 작성해보자.

숫자를 입력받으면 해당하는 항의 피보나치 수열을 출력한다. 

 

---

알고리즘 분석

 

---

숫자 n이 입력되면 n항까지 피보나치 수열을 계산한다.

n0 = 1 이라면 n1 = 1이다.

n0 + n1 = n2

n1 + n2 = n3

n2 + n3 = n4

 의 계산과정을 거친다.

 

우선 생각이 가는대로 알고리즘을 작성해본다.

ADT 피보나치 (int n){
int 출력수1 = 1;
int 출력수2 = 1;


	출력하세요(출력수1);    // 첫째항을 미리 출력하자
	for(int i=0; i<n-1; i++){
    	if(n이 1이라면)
    		출력하세요 (출력수2);   // 두번째항을 출력하자
            
        if(n이 1보다 크다면) {
        	int temp;
           	temp = 출력수2;
        	출력수2 =  출력수1 + 출력수2;
            출력수1 = temp;
            출력하세요 (출력수2);
            }
    }
}

 

C언어로 구현해보았다.

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>


void pibo(int n) {
	int output1 = 1;
	int output2 = 1;

	printf("%d ", output1);
	for (int i = 0; i < n; i++) {
		if (i == 1)
			printf("%d ", output2);
		if (i > 1) {
			int temp;
			temp = output2;
			output2 = output1 + output2;
			output1 = temp;
			printf("%d ", output2);
		}
	}
	
}

int main() {
	int n;
	printf("피보나치 수열을 구합니다. 숫자를 입력해주세요.");
	scanf("%d", &n);
	pibo(n);
	return 0;
}

 

알맞게 작동한다.

 

 

---

재귀함수로 작성해보아라.

피보나치 수열 문제

1, 1, 2, 3, 5, 8, 13, 21 ...

n항과  (n+1)항을 더하는 알고리즘을 작성해보자.

숫자를 입력받으면 해당하는 항의 피보나치 수열만 출력한다.

(나머지 항을 출력할 필요는 없다.)

 

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>

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

int main() {
	int n;
	printf("피보나치 수열을 구합니다. 숫자를 입력해주세요.");
	scanf("%d", &n);
	printf("%d", f1(n));
}