Trong bài toán này, chúng ta được cung cấp một giá trị nguyên N. Nhiệm vụ của chúng ta là tìm Tổng của Chuỗi 1 + 22 + 333 + 4444 + 55555 ... tối đa n số hạng .
Hãy lấy một ví dụ để hiểu vấn đề,
Input : N = 4 Output : 4800
Giải thích -
1 + 22 + 333 + 4444 = 4800
Phương pháp tiếp cận giải pháp
Một cách tiếp cận đơn giản để giải quyết vấn đề là tìm số hạng chung của chuỗi và sau đó tìm tổng cho đến n số hạng. Và việc tính tổng bằng công thức sẽ giảm thời gian xuống còn O (1).
Sê-ri là,
1 + 22 + 333 + 4444 + 55555 ...
Tổng của chuỗi có thể được viết lại thành,
$ \ mathrm {Sum} \:=\:1 ^ * (\ frac {10 ^ 1-1} {9}) \:+ \:2 ^ * (\ frac {10 ^ 1-1} {9}) \:+ \:3 ^ * (\ frac {10 ^ 1-1} {9}) \ dotm $
Lấy 1/9 chung thì tổng trở thành,
$ \ mathrm {Sum} \:=\:1/9 ^ * \ lbrace (1 ^ * 10 ^ 1-1) \:+ \ :( 2 ^ * 10 ^ 2-1) \:+ \ :( 3 ^ * 10 ^ 3-1) \:+ \:\ dotm (n ^ * 10 ^ 1-n) \ rbrace $
$ \ mathrm {Sum} \:=\:1/9 ^ {*} \ lbrace1 ^ * 10 ^ 1 \:+ \:2 ^ * 10 ^ 2 \:+ \:3 ^ * 10 ^ 3 \:+ \:\ dotm + n ^ * 10 ^ n \:- \ :( 1 + 2 + 3 + \ dotm \:n) \ rbrace $
$ \ mathrm {Sum} \:=\:1/9 ^ {*} \ lbrace (1 ^ * 10 ^ 1 \:+ \:2 ^ * 10 ^ 2 \:+ \:3 ^ * 10 ^ 3 \ :+ \:\ dotm + n ^ * 10 ^ n) \:- \:1/2 (n ^ * (n + 1)) \ rbrace $
Thuật ngữ (1 * 10 1 + 2 * 10 2 + 3 * 10 3 + ... + n * 10 n ) có thể được giải quyết bằng cách phân biệt công thức chung cho chuỗi,
1 + x + x 2 + x 3 + ... n * x n
Vì vậy, các điều khoản (1 * 10 1 + 2 * 10 2 + 3 * 10 3 + ... + n * 10 n ) có thể được viết lại thành,
$ \ frac {n ^ * (10 ^ {n + 2}) - (n + 1) * (10 ^ {n + 1}) + 10} {81} $
Đưa trở lại công thức tính tổng,
$ \ mathrm {Sum} \:=\:1/9 ^ * \ lbrace (\ frac {n ^ * (10 ^ {n + 2}) - (n + 1) * (10 ^ {n + 1}) +10)} {81} \:- \:1/2 (n ^ * (n + 1)) \ rbrace $
$ \ mathrm {Sum} \:=\:\ frac {1} {1458} * \ lbrace2 ^ * (n * (10 ^ {n + 2}) - (n + 1) * (10 ^ {n + 1 }) + 10) -81 ^ * n ^ * (n + 1) \ rbrace $
$ \ mathrm {Sum} \:=\:\ frac {1} {1458} * \ lbrace2 ^ * (n * (10 ^ {n + 2}) - (n + 1) * (10 ^ {n + 1 }) + 10) -81 ^ * n ^ * (n + 1) \ rbrace $
$ \ mathrm {Sum} \:=\:\ frac {1} {1458} * \ lbrace (n ^ * (2 ^ * 10 ^ {n + 1} -2 ^ * 10 ^ {n + 1}) - 2 ^ * 10 ^ {n + 1}) \:+ \:20 \:- \:81 ^ * n ^ 2-81n \ rbrace $
$ \ mathrm {Sum} \:=\:\ frac {1} {1458} * \ lbrace10 ^ {n + 1 *} (20n-2n-2) -81n ^ 2-81n + 20 \ rbrace $
$ \ mathrm {Sum} \:=\:\ frac {1} {1458} * \ lbrace10 ^ {n + 1 *} (18n-2) -81n ^ 2-81n + 20 \ rbrace $
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 calcSumNTerms(int n) {
return ( ( (18*n - 2)*(pow(10, n+1)) - 81*n*n - 81*n + 20 )/1458 );
}
int main() {
int n = 5;
cout<<"The sum of series upto n terms is "<<calcSumNTerms(n);
return 0;
} Đầu ra
The sum of series upto n terms is 60355