[실기] 4. 피보나치 수열

in 정보처리기사 on 기사 실기 알고리즘


피보나치 수열이란? 앞에 연속 된 2개의 항의 합하여 새로운 항을 만들어 나열하는 규칙


설명

  • 피보나치 수열
    • 앞에 연속 된 2개의 항의 합하여 새로운 항을 만들어 나열하는 규칙
    • 1, 1, 2, 3, 5, 8, 13, 21, 34 …
    • 피보나치 수열의 2개의 시작하는 항은 1, 1이다.
    • n번째 항, An = An-2 + An-1

An = An-2 + An-1

  • 1 + 1 = 2 -> 1, 1, 2
  • 1 + 2 = 3 -> 1, 1, 2, 3
  • 2 + 3 = 5 -> 1, 1, 2, 3, 5
  • 3 + 5 = 8 -> 1, 1, 2, 3, 5, 8

위와 같은 규칙으로 수열이 나열 된다.


문제

  • 1, 1, 2, 3, 5, 8, 13, 21 …
  • 다음 피보나치 수열에 대해 100번째까지 항의 합을 구하는 알고리즘을 구해라


C언어

#include<stdio.h>

int main() {

	int A = 1; // n-2번째 항의 변수 
	int B = 1; // n-1번째 항의 변수
	int C = 0; // 새로 생성되는 변수(n번째 항의 변수) 
	int S = A + B; // 합의 변수
	int N = 2;     // 항 개수 (처음 항이 1, 1로 시작)
	while (1) {
		C = A + B;
		S = S + C;
		A = B;
		B = C;
		N++;
		if (N > 100) break;
	}
	printf("%d\n", S);
};


JAVA

public class Main {
	public static void main (String[] args) {

		int A = 1; // n-2번째 항의 변수 
		int B = 1; // n-1번째 항의 변수
		int C = 0; // 새로 생성되는 변수(n번째 항의 변수) 
		int S = A + B; // 합의 변수
		int N = 2;     // 항 개수 (처음 항이 1, 1로 시작)
		while (true) {
			C = A + B;
			S = S + C;
			A = B;
			B = C;
			N++;
			if (N > 100) break; 
		}
		System.out.println(S);
	}
}