Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++로 수열 1, 3, 12, 60, 360...의 N번째 항 구하기

이 문제에서는 하나의 숫자 N이 주어지며, 우리의 목표는 C++를 사용하여 수열 1, 3, 12, 60, 360...의 N번째 항을 구하는 프로그램을 작성하는 것입니다.

문제 이해하기

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

1, 3, 12, 60, 360, 2520 ... N번째 항까지

입력 및 출력 예시

  • 입력: N = 6
  • 출력: 2520

해결 접근 방법

이 수열의 일반항 공식은 언뜻 보기에 쉽게 떠오르지 않습니다. 수열의 값이 기하급수적으로 커지기 때문에 팩토리얼(Factorial)이나 지수 형태일 가능성이 높습니다.

먼저 팩토리얼을 가정하고 수열을 관찰해 보면, 각 항의 증가율이 팩토리얼 값의 절반에 해당한다는 사실을 발견할 수 있습니다. 또한 첫 번째 항인 1은 2! (2의 팩토리얼)을 2로 나눈 값과 일치합니다.

이를 바탕으로 이 수열의 일반항 공식은 다음과 같이 도출됩니다.

TN = (N+1)! / 2

공식 검증을 위해 몇 가지 항을 직접 계산해 보겠습니다.

  • N = 1일 때: 2! / 2 = 2 / 2 = 1
  • N = 2일 때: 3! / 2 = 6 / 2 = 3
  • N = 3일 때: 4! / 2 = 24 / 2 = 12
  • N = 4일 때: 5! / 2 = 120 / 2 = 60

모든 항이 정확히 일치하므로, 위 공식이 올바른 일반항임을 확인할 수 있습니다.

C++ 구현 코드

#include <iostream>
using namespace std;

// 재귀 방식으로 팩토리얼을 계산하는 함수
int calcFact(int n) {
    if (n == 1) {
        return 1;
    }
    return (n * calcFact(n - 1));
}

// N번째 항을 계산하는 함수
int findNTerm(int N) {
    int nthTerm = ((calcFact(N + 1)) / 2);
    return nthTerm;
}

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

실행 결과

8th term of the series is 181440

코드 설명

위 프로그램은 두 개의 주요 함수로 구성되어 있습니다.

  • calcFact(): 재귀 호출을 통해 인자로 받은 숫자의 팩토리얼 값을 계산합니다. n이 1이면 1을 반환하는 것이 종료 조건입니다.
  • findNTerm(): 도출한 일반항 공식 (N+1)! / 2를 적용하여 N번째 항을 계산합니다.

시간 복잡도는 재귀적 팩토리얼 계산에 의해 O(N)이며, 입력값 N이 커질수록 결과값이 매우 빠르게 증가하므로 실제 사용 시 자료형의 범위를 고려해야 합니다. 더 큰 수를 다루려면 long long 타입을 사용하는 것이 좋습니다.