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

C++로 수열 9, 33, 73, 129…의 n번째 항 구하기

이 문제에서는 정수 N이 주어지며, 수열 9, 33, 73, 129…의 n번째 항을 찾아야 합니다.

예시를 통해 문제를 이해해 보겠습니다.

입력

N = 4

출력

129

설명

n번째 항까지의 수열은 9, 33, 73, 129…입니다. 즉, N = 4일 때 네 번째 항인 129가 결과가 됩니다.

해결 접근 방법

이 문제의 해결 열쇠는 수열의 일반항을 찾는 것입니다. 수학적으로 일반항을 유도한 뒤, 그 식을 프로그램에 그대로 적용하면 됩니다.

먼저 원래 수열과 한 항씩 밀어낸 수열을 나란히 써서 서로 빼 보겠습니다.

Sum = 9 + 33 + 73 + … + t(n-1) + t(n)
- Sum = 9 + 33 + 73 + … + t(n-1) + t(n)

0 = 9 + ((33 − 9) + (73 − 33) + … + (t(n) − t(n-1))) − t(n)
t(n) = 9 + (24 + 40 + 56 + …)

여기서 24 + 40 + 56 + … 은 공차가 16인 등차수열입니다. 등차수열의 합 공식을 적용하면 일반항은 다음과 같이 표현됩니다.

t(n) = 9 + [((n−1)/2) × (2×24 + (n−2)×16)]

이 식을 전개하고 차례대로 간단히 정리하면,

t(n) = 9 + (n − 1) × (24 + (n − 2) × 8)
t(n) = 9 + (n − 1) × (8 + 8n)
t(n) = 9 + 8 × (n − 1)(n + 1)
t(n) = 9 + 8 × (n2 − 1)
t(n) = 8n2 + 1

최종적으로 수열의 n번째 항은 t(n) = 8n2 + 1이라는 매우 간단한 공식으로 나타납니다. 검산해 보면 n = 1일 때 9, n = 2일 때 33, n = 3일 때 73, n = 4일 때 129로 주어진 수열과 정확히 일치합니다.

이 공식을 활용한 C++ 프로그램입니다.

예제 코드

#include <iostream>
using namespace std;

int findNthTerm(int n) {
    return (8*n*n) + 1;
}

int main(){
    int n = 12;
    cout<<"The series is 9, 33, 73, 129...\n";
    cout<<n<<"th term of the series is "<<findNthTerm(n);
    return 0;
}

실행 결과

The series is 9, 33, 73, 129...
12th term of the series is 1153

코드 설명

함수 findNthTerm은 위에서 유도한 일반항 공식 8n2 + 1을 그대로 반환합니다. main 함수에서는 n = 12를 대입하여 12번째 항인 1153을 출력합니다. 반복문 없이 공식 하나만으로 답을 계산하므로 시간 복잡도는 O(1)이며, 어떤 큰 n이 주어져도 상수 시간 안에 결과를 얻을 수 있다는 점이 이 방법의 가장 큰 장점입니다.