資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
服裝設計
法律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 = 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
更新於：2020年8月17日
253 次檢視
廣告