C++에서 Kn + ( K(n-1) * (K-1)1 ) + ( K(n-2) * (K-1)2 ) + ... (K-1)n 계열의 합

<시간/>

문제에서 우리는 두 수 k와 n 시리즈 K^n + ( K^(n-1) * (K-1)^1 ) + ( K^(n-2) * (K-1 )^2 ) + ... (K-1)^n. 우리의 임무는 시리즈의 합을 찾는 프로그램을 만드는 것입니다.

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

Input: n = 3, k = 4
Output: 175
Explanation: Sum of the series is
= 4^3 + ( (4^2)*(3^1) ) + ( (4^1)*(3^2) ) + ( (4^0)*(3^3) )
= 64 + 48 + 36 + 27 = 175

문제를 해결하는 간단한 방법은 for 루프를 사용하는 것입니다. 급수의 각 항을 찾아 합계에 값을 더하세요.

알고리즘

initialise sum = 0;
Step 1: for i -> 0 to n.
Step 1.1: update sum: sum += pow(k, n-i) * pow(k, i)
Step 2: return sum.

예시

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

#include <iostream>
#include <math.h>
using namespace std;
int calcSeriesSum(int k, int n) {
   int sum = 0;
   for (int i = 0; i <= n; i++) {
      int p = pow(k, n-i) * pow((k-1), i);
      sum = sum + p;
   }
   return sum;
}
int main() {
   int n = 4;
   int K = 2;
   cout<<"Sum of the series is "<<calcSeriesSum(K, n);
}

출력

Sum of the series is 31

이 솔루션은 효율적이지 않으며 n의 시간이 걸립니다.

효율적인 솔루션은 급수의 합에 대한 일반 공식을 찾는 것입니다.

The series K^n + ( K^(n-1) * (K-1)^1 ) + ( K^(n-2) * (K-1)^2 ) + ... (K-1)^n
Forms a geometric progression. The common ration of this progression is (k-1)/k and the first term is k^n.
sum = K^n + ( K^(n-1) * (K-1)^1 ) + ( K^(n-2) * (K-1)^2 ) + ... (K-1)^n
sum = kⁿ(1 + (k-1)/k + (k-1)²/k²+ … + (k-1)ⁿ)
sum = ((kⁿ)(1 - ( (k-1)⁽ⁿ⁺¹⁾)/k⁽ⁿ⁺¹⁾)) / (1 - ((k-1)/k))
sum = kⁿ ( (k⁽ⁿ⁺¹⁾ - (k-1)⁽ⁿ⁺¹⁾)/k⁽ⁿ⁺¹⁾ ) / ( (k - (k-1))/k )
sum = kⁿ ( (k⁽ⁿ⁺¹⁾ - (k-1)⁽ⁿ⁺¹⁾)/k⁽ⁿ⁺¹⁾ ) / (1/k)
sum = kⁿ ( (k⁽ⁿ⁺¹⁾ - (k-1)⁽ⁿ⁺¹⁾)/k⁽ⁿ⁺¹⁾ ) * k
sum = ( k⁽ⁿ⁺¹⁾ - (k-1)⁽ⁿ⁺¹⁾ )

예시

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

#include <iostream>
#include <math.h>
using namespace std;
int calcSeriesSum(int k, int n) {
   return ( pow(k,(n+1)) - pow((k-1),(n+1)) );
;
}
int main() {
   int n = 4;
   int K = 2;
   cout<<"Sum of the series is "<<calcSeriesSum(K, n);
}

출력

Sum of the series is 31