C++로 수열 0, 2, 1, 3, 1, 5, 2, 7, 3…의 N번째 항 구하기

이 문제에서는 숫자 N이 주어지며, C++로 수열 0, 2, 1, 3, 1, 5, 2, 7, 3…의 N번째 항을 구하는 프로그램을 작성하는 것이 목표입니다.

문제 설명

주어진 수열은 다음과 같습니다.

0, 2, 1, 3, 1, 5, 2, 7, 3 … N번째 항

이 수열의 N번째 항을 구하려면 먼저 수열의 일반항 규칙을 파악한 뒤, 그 규칙에 따라 N번째 값을 계산해야 합니다.

예시로 이해하기

입력: N = 7
출력: 2

접근 방법

일반항 공식을 찾으려면 수열을 면밀히 관찰해야 합니다. 겉보기에는 규칙이 없어 보이지만, 사실 이 수열은 서로 다른 두 수열이 교차해서 나타나는 혼합 수열(mixture series)입니다. 이 점만 깨닫으면 일반항을 훨씬 쉽게 도출할 수 있습니다.

홀수 번째 항과 짝수 번째 항을 각각 분리해 보겠습니다.

• 홀수 번째 항: 0, 1, 1, 2, 3, … → 피보나치 수열
• 짝수 번째 항: 2, 3, 5, 7, … → 소수 수열

이제 규칙이 명확해졌습니다. 이 수열은 다음과 같이 정리할 수 있습니다.

• N이 홀수이면 → (N/2)번째 피보나치 수를 반환
• N이 짝수이면 → (N/2)번째 소수를 반환

구현 코드

#include<iostream>
using namespace std;

// n번째 소수를 찾는 함수
int findNthPrimeTerm(int n) {
    int primeCount = 0;
    for (int i = 2; ; i++) {
        int isPrime = 1;
        for (int j = 2; j <= (i / 2); j++) {
            if (i % j == 0) {
                isPrime = 0;
                break;
            }
        }
        if (isPrime)
            primeCount++;
        if (primeCount == n) {
            return i;
        }
    }
    return -1;
}

// n번째 피보나치 수를 찾는 함수
int FibonaciiNthTerm(int n) {
    int nthTerm = 1, last = 0;
    if (n == 0)
        return 0;
    else if (n == 1)
        return 1;
    else {
        for (int i = 2; i <= n; i++) {
            nthTerm += last;
            last = nthTerm - last;
        }
        return nthTerm;
    }
}

// N번째 항을 찾는 함수
int findNTerm(int N) {
    if (N % 2 == 0)
        return findNthPrimeTerm(N / 2);   // 짝수 → 소수
    else
        return FibonaciiNthTerm(N / 2);   // 홀수 → 피보나치 수
}

int main() {
    int N = 13;
    cout << N << "th term of the series is " << findNTerm(N) << endl;
    N = 4;
    cout << N << "th term of the series is " << findNTerm(N);
    return 0;
}

실행 결과

13th term of the series is 8
4th term of the series is 3

코드 설명

findNthPrimeTerm() 함수는 2부터 차례대로 수를 검사하며 소수인지 판별하고, n번째 소수를 만나면 해당 값을 반환합니다. FibonaciiNthTerm() 함수는 반복문을 사용해 n번째 피보나치 수를 계산합니다. 마지막으로 findNTerm() 함수가 N의 홀짝 여부를 판단해 적절한 함수를 호출함으로써 혼합 수열의 N번째 항을 구합니다.

예를 들어 N = 13인 경우 N이 홀수이므로 6번째 피보나치 수인 8이 반환되고, N = 4인 경우 N이 짝수이므로 2번째 소수인 3이 반환됩니다.