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

C++에서 계열 1 + 2 + 2 + 3 + 3 + 3 + .. + n의 합을 찾는 프로그램

<시간/>

이 문제에서는 급수의 n번째 항을 나타내는 숫자 n이 주어집니다. 우리의 임무는 C++에서 계열 1 + 2 + 2 + 3 +3 + 3 + .. + n의 합을 찾는 프로그램을 만드는 것입니다. .

문제 설명 − 여기에서 n번째 항이 n번 숫자 n의 합인 급수의 합을 찾습니다. 이것은 일련의 제곱수임을 의미합니다.

문제를 이해하기 위해 예를 들어보겠습니다.

입력

n = 4

출력

30

설명

4번째 항까지 급수의 합 =1 + 2 + 2 + 3 + 3 + 3 + 4 + 4 + 4 + 4 =30

솔루션 접근 방식

문제에 대한 가장 효과적인 해결책은 급수의 합에 대한 일반 공식을 사용하는 것입니다.

하지만 생각할 수 있는 문제의 가능한 모든 솔루션에 대해 논의해 보겠습니다.

가장 간단한 솔루션 문제는 n까지 시리즈의 수를 추가하는 것입니다. 이를 위해서는 두 개의 중첩 루프가 필요합니다. 하나는 용어이고 다른 하나는 각 용어의 값에 대한 내부 루프입니다.

알고리즘

초기화 - sumVar =0;

  • 1단계 − i -> 1 ~ n.
      에 대한 루프
    • 1.1단계 − j -> 1에서 i.
        에 대한 루프
      • 1.1.1단계 - sumVar 업데이트, sumVar+=i;
  • 2단계 − sumVar를 인쇄합니다.

우리 솔루션의 작동을 설명하는 프로그램

예시

#include <iostream>
using namespace std;
int calcSeriesSum(int n){
   int sumVar = 0;
   for(int i = 1; i <= n; i++){
      for(int j = 1; j <= i; j++){
         sumVar += i;
      }
   }
   return sumVar;
}
int main(){
   int n = 7;
   cout<<"The sum of series till "<<n<<" is "<<calcSeriesSum(n);
   return 0;
}

출력

The sum of series till 7 is 140

이 솔루션은 간단하지만 O(n2) 순서의 시간 복잡도를 만드는 두 개의 중첩 루프가 있으므로 효과적이지 않습니다. .

효과적인 솔루션 이는 number(n)이 자신에게 n번 더해진다는 사실에 기반합니다. 그런 다음 숫자를 자체적으로 곱하면 결과를 얻을 수 있습니다.

즉, 5+5+5+5+5 =5*5.

따라서 하나의 루프 대신 곱셈을 사용하여 문제를 해결할 수 있습니다.

알고리즘

초기화 - sumVal =0;

  • 1단계 - i에 대한 루프 -> 0에서 n.
    • 2단계 - sumVal, sumVal 업데이트 +=(i*i)

우리 솔루션의 작동을 설명하는 프로그램

예시

#include <iostream>
using namespace std;
int calcSeriesSum(int n){
   int sumVar = 0;
   for(int i = 1; i <= n; i++){
      sumVar += (i*i);
   }
   return sumVar;
}
int main(){
   int n = 7;
   cout<<"The sum of series till "<<n<<" is "<<calcSeriesSum(n);
   return 0;
}

출력

The sum of series till 7 is 140

솔루션은 하나의 루프만 사용하고 O(n) 차수의 시간 복잡도를 갖기 때문에 더 좋습니다. 그러나 O(1) 시간 복잡도에서 동일한 작업을 수행할 수 있으므로 최상의 솔루션은 아닙니다.

가장 효과적인 솔루션 주어진 급수의 합에 대한 일반 공식을 사용하고 있습니다.

시리즈 합계 =

1 + 2 + 2 + 3 + 3 + 3 + … 아니오.

다음과 같이 만들 수 있습니다.

1 + (2+2) + (3+3+3) + … + (N+N+N..N)
1*1 + 2*2 + 3*3 + … N*N.
12 + 22 + 32 + … N2.

$Sum =\sum_{\square=1}^\square\blacksquare\square^2$

제곱합의 공식은 n*(n+1)*(2n+1)/6입니다. 그리고 우리는 이 공식을 사용하여 합을 찾을 수도 있습니다.

우리 솔루션의 작동을 설명하는 프로그램

예시

#include <iostream>
using namespace std;
int calcSeriesSum(int n){
   int sumVar = 0;
   sumVar = ((n*(n + 1)*( 2 * n + 1))/6 );
      return sumVar;
}
int main(){
   int n = 7;
   cout<<"The sum of series till "<<n<<" is "<<calcSeriesSum(n);
   return 0;
}

출력

The sum of series till 7 is 140