이 문제에서는 두 개의 정수 m과 n이 주어집니다. 우리의 임무는 처음 n개의 자연수의 m번째 합을 찾는 것입니다.
문제 설명: n개의 자연수의 합을 m번 구합니다. 합계는 공식으로 제공됩니다.
만약 (m> 1),
합(n, m) =합( 합(n, (m-1)), 1 )
만약 (m =1)
sum(n, m) =sum(n, 1) =n개의 자연수의 합
문제를 이해하기 위해 예를 들어 보겠습니다.
입력: m =4, n =2
출력: 231
설명:
합계(2, 4) =합계( 합계(2, 3), 1 )
=합계 ( 합계 ( 합계 (2, 2), 1) , 1 )
=합계 ( 합계 ( 합계 ( 합계( 2, 1), 1) , 1 ), 1)
=합계 ( 합계 ( 합계 (3, 1) , 1 ), 1)
=합계 ( 합계 ( 6 , 1 ), 1)
=합계 (21, 1)
=231
해결 방법 -
문제에 대한 간단한 해결책은 두 개의 중첩 루프를 사용하는 것입니다. 바깥쪽은 m 값을 위한 것이고 안쪽은 n 값을 위한 것입니다. n의 값을 업데이트하고 n개의 자연수의 합을 m번 계산합니다.
보다 효과적인 접근 방식은 n개의 자연수의 합을 m번 반복적으로 호출하여 재귀가 수행될 때마다 이전 합으로 값을 업데이트하는 것입니다.
알고리즘:
1단계: sum =sum(n, m-1)* (sum(n, m-1)+1) / 2 로 합계 값 업데이트 m의 합이 1보다 큰 경우.
2단계: m =1의 값이면 sum =n * (n+1) /2를 반환합니다.
3단계: 반환 합계.
우리 솔루션의 작동을 설명하는 프로그램,
예시
#include <iostream>
using namespace std;
int calcSumN(int n, int m) {
if (m == 1)
return (n * (n + 1) / 2);
return (calcSumN(n, m-1) * (calcSumN(n, m-1) + 1) / 2);
}
int main() {
int n = 4;
int m = 6;
cout<<m<<"-th summation of first "<<n<<" natural numbers is "<<calcSumN(n, m);
return 0;
} 출력
6-th summation of first 4 natural numbers is 125230148