C++로 M번째와 N번째 항이 주어졌을 때 등비수열(GP)의 P번째 항 구하기

이 문제에서는 다섯 개의 값, 즉 m, n, m번째 항, n번째 항, p가 주어집니다. 우리의 목표는 등비수열(GP)의 m번째 항과 n번째 항을 이용하여 p번째 항을 구하는 것입니다.

문제 이해를 위한 예시

입력

m = 7, mthTerm = 1458, n = 10, nthterm = 39366, p = 3

출력

해결 접근 방법

주어진 수열이 등비수열이라고 가정해 봅시다. 일반적인 등비수열의 형태는 다음과 같습니다.

GP = a , a*r , a*(r²), a*(r³) ….

여기서 T번째 항을 구하는 공식은 다음과 같습니다.

T번째 항 = a * r^(T-1)

문제에서 m번째 항과 n번째 항이 주어졌으므로 두 식을 세워볼 수 있습니다.

m번째 항 = a * (r ^ (m-1))
n번째 항 = a * (r ^ (n-1))

두 식을 서로 나누면 첫항 a가 소거되고 다음 관계식을 얻습니다.

m번째 항 / n번째 항 = (r ^(m - n))

이 식을 활용하면 공비 r의 값을 구할 수 있습니다. 그다음 m번째 항의 값을 대입하여 첫항 a를 계산합니다.

m번째 항 = a * (r^(m-1))

a와 r을 모두 구했다면, 아래 공식을 통해 p번째 항을 손쉽게 계산할 수 있습니다.

p번째 항 = a * (r^(p-1))

C++ 구현 예제

위 풀이 과정을 C++ 코드로 구현하면 다음과 같습니다.

#include <cmath>
#include <iostream>
using namespace std;
// 등비수열의 공비 r을 구하는 함수
double findRinGP(double m, double n, double mth, double nth) {
   if (m < n)
      return pow(nth / mth, 1.0 / (n - m));
   return pow(mth / nth, 1.0 / (m - n));
}
// p번째 항을 구하는 함수
double findTermGP(int m, int n, double mth, double nth, int p) {
   double r = findRinGP(m, n, mth, nth);
   double a = mth / pow(r, (m - 1));
   return ( a * pow(r, (p - 1)) );
}
int main() {
   int m = 7, n = 10, p = 5;
   double mth = 1458, nth = 39366;
   cout<<"The "<<p<<"th of the series is "<<findTermGP(m, n, mth, nth, p);
   return 0;
}

출력 결과

The 5th of the series is 162

코드 설명

findRinGP() 함수는 두 항의 비율과 지수 차이를 이용해 공비 r을 계산합니다. m과 n의 크기 관계에 따라 분모가 음수가 되지 않도록 조건문으로 처리한 점이 특징입니다.

findTermGP() 함수는 구해진 공비 r을 이용해 첫항 a를 역산한 뒤, 등비수열 일반항 공식에 p를 대입하여 최종 결과를 반환합니다.

이 알고리즘은 거듭제곱 연산에 의존하므로 전체 시간 복잡도는 O(log(max(m, n))) 수준으로 매우 효율적입니다.