Computer >> 컴퓨터 >  >> 프로그램 작성 >> C++

C++에서 처음 n개의 자연수의 m번째 합 찾기

<시간/>

이 문제에서는 두 개의 정수 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