C++로 수열 0, 8, 64, 216, 512…의 n번째 항 구하기

이 문제에서는 정수 N이 주어지며, 우리의 목표는 다음 수열의 n번째 항을 구하는 것입니다.

0, 8, 64, 216, 512, 1000, 1728, 2744…

문제 이해를 위한 예시

입력: N = 6
출력: 1000

접근 방법

수열의 n번째 항을 찾으려면 먼저 수열의 패턴을 면밀히 관찰해야 합니다. 이 수열은 짝수의 세제곱으로 이루어져 있으며, 첫 번째 항은 0에서 시작합니다.

따라서 수열은 다음과 같이 해석할 수 있습니다.

[0]³, [2]³, [4]³, [6]³, [8]³, [10]³…

i번째 항을 일반화하면 다음과 같습니다.

T1 = [0]³ = [2×(1−1)]³

T2 = [2]³ = [2×(2−1)]³

T3 = [4]³ = [2×(3−1)]³

T4 = [6]³ = [2×(4−1)]³

T5 = [8]³ = [2×(5−1)]³

위의 규칙을 종합하면, 수열의 n번째 항은 { [2×(N−1)]³ }이라는 공식으로 표현할 수 있습니다. 이 공식을 사용하면 반복문 없이 O(1)의 시간 복잡도로 답을 바로 계산할 수 있습니다.

구현 예제

다음은 위 접근 방식을 C++로 구현한 프로그램입니다.

#include <iostream>
using namespace std;

long findNthTermSeries(int n){
    return ((2*(n-1))*(2*(n-1))*(2*(n-1)));
}
int main(){
    int n = 12;
    cout<<n<<"번째 항은 "<<findNthTermSeries(n);
    return 0;
}

실행 결과

12번째 항은 10648

위 코드에서 n = 12를 입력하면, 공식 [2×(12−1)]³ = [22]³ = 10648이 계산되어 정확한 결과가 출력됩니다.