C++로 구현하는 교차 피보나치 수열: 알고리즘과 예제 코드

피보나치 수열이란?

피보나치 수(Fibonacci Number)는 일반적으로 0, 1 또는 1, 1처럼 고정된 두 개의 수로 시작하는 수열을 의미하며, 그 이후의 모든 항은 바로 앞에 있는 두 항을 더한 값으로 정의됩니다.

예를 들어 피보나치 수열의 초반 부분은 다음과 같습니다.

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89

피보나치 수열의 점화식

이 수열을 일반화하면, n번째 항은 (n-1)번째 항과 (n-2)번째 항의 합과 같습니다. 이를 수식으로 표현하면 다음과 같습니다.

T_n = T_n-1 + T_n-2

예를 들어 0부터 인덱스를 세었을 때 6번째 항은 다음과 같이 구할 수 있습니다.

F₆ = F₅ + F₄ = 5 + 3 = 8

교차 피보나치 수열이란?

교차 피보나치 수열(Alternate Fibonacci Series)은 원래 피보나치 수열과 값은 동일하지만, 수열의 요소를 하나씩 건너뛰며 출력한 것을 말합니다. 즉, 원래 수열의 0번째, 2번째, 4번째, 6번째 항만 순서대로 출력합니다.

예를 들어 교차 피보나치 수열의 처음 네 개 요소는 0, 1, 3, 8입니다. 이는 원래 피보나치 수열(0, 1, 1, 2, 3, 5, 8, ...)에서 한 칸씩 건너뛴 값들입니다.

교차 피보나치 수열을 출력하는 프로그램을 만들려면 위의 점화식을 이용해 수열의 모든 항을 계산하되, 그중 교차하는 값만 화면에 출력하면 됩니다.

알고리즘

Step 1 : 수열의 첫 번째 값과 두 번째 값을 n1 = 0, n2 = 1로 초기화한다.
Step 2 : i = 2부터 n*2까지 반복하면서 3~5단계를 수행한다.
Step 3 : 다음 항을 계산한다. n3 = n1 + n2
Step 4 : n1 = n2, n2 = n3로 값을 갱신한다.
Step 5 : 만약 i % 2 == 0이면 n3를 출력한다.

C++ 구현 예제

#include <iostream>
using namespace std;

int main(){
    int n1 = 0, n2 = 1, n3, i, number;
    cout << "수열에 포함할 항의 개수를 입력하세요: ";
    cin >> number;
    cout << "교차 피보나치 수열 : ";
    cout << n1 << " ";
    for (i = 2; i < (number * 2); ++i){
        n3 = n1 + n2;
        n1 = n2;
        n2 = n3;
        if(i % 2 == 0)
            cout << n3 << " ";
    }
    return 0;
}

실행 결과

수열에 포함할 항의 개수를 입력하세요: 4
교차 피보나치 수열 : 0 1 3 8

코드 설명

사용자가 원하는 항의 개수(number)를 입력하면, 루프는 number * 2번 반복됩니다. 두 항 중 하나만 출력되기 때문에 원하는 개수만큼의 값을 얻으려면 실제로는 두 배의 항을 계산해야 하기 때문입니다.

첫 번째 값 0은 루프가 시작되기 전에 미리 출력하고, 이후에는 매 반복마다 점화식에 따라 새로운 항(n3)을 계산합니다. 조건문 if(i % 2 == 0)은 짝수 번째 반복에서만 해당 항을 출력하므로, 결과적으로 하나씩 건너뛴 형태의 피보나치 수열이 완성됩니다.