C++での級数Kn+（K（n-1）*（K-1）1）+（K（n-2）*（K-1）2）+ ...（K-1）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 = kn(1 + (k-1)/k + (k-1)2/k2 + … + (k-1)n)
sum = ((kn)(1 - ( (k-1)(n+1))/k(n+1))) / (1 - ((k-1)/k))
sum = kn ( (k(n+1) - (k-1)(n+1))/k(n+1) ) / ( (k - (k-1))/k )
sum = kn ( (k(n+1) - (k-1)(n+1))/k(n+1) ) / (1/k)
sum = kn ( (k(n+1) - (k-1)(n+1))/k(n+1) ) * k
sum = ( k(n+1) - (k-1)(n+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