이 문제에서는 세 개의 값 a, d, n이 주어지며, C++로 조화급수의 합을 구하는 프로그램을 작성해야 합니다.
조화급수(HP)는 각 항의 역수가 등차수열을 이루는 수열입니다. 즉, 조화급수 A1, A2, A3, ..., An이 존재한다면, 그 역수들인 1/A1, 1/A2, 1/A3, ...은 등차수열(AP)이 됩니다.
따라서 일반적인 조화급수는 다음과 같은 형태입니다.
1/a, 1/(a+d), 1/(a+2d), …, 1/(a+nd)
여기서 1/a는 첫째 항이며, d는 역수로 변환된 등차수열의 공차(common difference)입니다.
문제 설명
조화급수의 첫째 항 a, 공차 d, 항의 개수 n이 주어졌을 때, 해당 급수의 합을 계산하는 것이 목표입니다.
예시를 통해 문제를 자세히 살펴보겠습니다.
입력
a = 3, d = 2, n = 5
출력
0.878211
설명
위 입력값에 대한 조화급수는 ⅓, ⅕, 1/7, 1/9, 1/11 입니다.
합 = ⅓ + ⅕ + 1/7 + 1/9 + 1/11 = 0.878211
풀이 접근법
가장 직관적인 방법은 1번째 항부터 n번째 항까지 반복하면서 각 항의 값을 계산하고, 그 값을 sumVal 변수에 누적하는 것입니다. 반복이 끝나면 sumVal을 반환하면 됩니다.
알고리즘
초기화 − sumVal = 0, term = 0
- 1단계 − i가 1부터 n까지 반복합니다.
- 1.1단계 − 각 항을 계산합니다: term = 1 / (a + (i-1)*d)
- 1.2단계 − sumVal을 갱신합니다: sumVal += term
- 2단계 − 최종 결과인 sumVal을 출력합니다.
반복문을 사용한 풀이 프로그램
예제 1: 반복문 활용
#include <iostream>
using namespace std;
float findSeriesSum(int a, int d, int n){
float sumVal = 0;
float term = 0;
for(float i = 1; i <= n; i++){
term = (1.0)/(float)(a + (i-1)*d);
sumVal += term;
}
return sumVal;
}
int main(){
int n = 5, a = 3, d = 2;
cout<<"The sum of HP is "<<findSeriesSum(a, d, n);
return 0;
}
출력
The sum of HP is 0.878211
또 다른 접근법으로는 재귀 함수를 사용하여 급수의 합을 구할 수 있습니다. 재귀 버전에서는 n번째 항을 먼저 계산한 뒤, 나머지 항들의 합을 재귀 호출로 구하여 더하는 방식입니다. 이때 기저 조건(base case)은 n이 1일 때 첫째 항인 1/a를 반환하는 것입니다.
예제 2: 재귀 함수 활용
#include <iostream>
using namespace std;
float findSeriesSum(int a, int d, int n){
if(n == 1){
return (float)(1.0)/a;
}
float term = (1.0)/ (float)(a + (n-1)*d);
return term + findSeriesSum(a, d, n-1);
}
int main(){
int n = 5, a = 3, d = 2;
cout<<"The sum of HP is "<<findSeriesSum(a, d, n);
return 0;
}
출력
The sum of HP is 0.878211
복잡도 분석
두 방법 모두 n개의 항을 한 번씩 계산하므로 시간 복잡도는 O(n)입니다. 반복문 방식은 추가 메모리 없이 동작하여 공간 복잡도가 O(1)인 반면, 재귀 방식은 호출 스택을 사용하므로 공간 복잡도가 O(n)입니다. 따라서 일반적으로는 반복문 방식이 더 효율적이며, 코드의 가독성과 학습 목적에 따라 재귀 방식을 선택할 수 있습니다.