Trong bài toán, chúng ta là ginen hai số k và n của chuỗi K ^ n + (K ^ (n-1) * (K-1) ^ 1) + (K ^ (n-2) * (K-1 ) ^ 2) + ... (K-1) ^ n. Nhiệm vụ của chúng tôi là tạo một chương trình để tìm tổng của chuỗi.
Hãy lấy một ví dụ để hiểu vấ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
Một cách đơn giản để giải quyết vấn đề là sử dụng vòng lặp for. Tìm từng số hạng của chuỗi và cộng giá trị vào tổng.
Thuật toán
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.
Ví dụ
Chương trình minh họa hoạt động của giải pháp của chúng tôi,
#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);
} Đầu ra
Sum of the series is 31
Giải pháp này không hiệu quả và mất thời gian của đơn đặt hàng n.
Một giải pháp hiệu quả sẽ là tìm công thức chung cho tổng của chuỗi.
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) )
Ví dụ
Chương trình minh họa hoạt động của giải pháp của chúng tôi,
#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);
} Đầu ra
Sum of the series is 31