Trong bài toán này, chúng ta được cho một số n biểu thị số hạng thứ n của chuỗi. Nhiệm vụ của chúng ta là tạo một Chương trình tìm tổng của chuỗi 1 + 2 + 2 + 3 +3 + 3 + .. + n trong C ++ .
Mô tả sự cố - Ở đây, chúng ta sẽ tìm tổng của dãy số có số hạng thứ n gấp n lần tổng của số n. Điều này có nghĩa là nó là một chuỗi các số bình phương.
Hãy lấy một ví dụ để hiểu vấn đề
Đầu vào
n = 4
Đầu ra
30
Giải thích
Tổng của chuỗi đến số hạng thứ 4 =1 + 2 + 2 + 3 + 3 + 3 + 4 + 4 + 4 + 4 =30
Phương pháp tiếp cận giải pháp
Giải pháp hiệu quả nhất cho vấn đề sẽ là sử dụng phương pháp tổng quát cho tổng của chuỗi.
Nhưng chúng ta hãy thảo luận về tất cả các giải pháp khả thi cho vấn đề mà người ta có thể nghĩ ra.
Giải pháp đơn giản nhất vấn đề là trực tiếp bằng cách cộng các số chuỗi cho đến n. Điều này sẽ yêu cầu hai vòng lặp lồng nhau, một trong số các từ và một vòng bên trong cho các giá trị trong mỗi thuật ngữ.
Thuật toán
Khởi tạo - sumVar =0;
- Bước 1 - Vòng lặp cho i -> 1 đến n.
- Bước 1.1 - Vòng lặp cho j -> 1 đến i.
- Bước 1.1.1 - Cập nhật sumVar, sumVar + =i;
- Bước 1.1 - Vòng lặp cho j -> 1 đến i.
- Bước 2 - In sumVar.
Chương trình minh họa hoạt động của giải pháp của chúng tôi
Ví dụ
#include <iostream>
using namespace std;
int calcSeriesSum(int n){
int sumVar = 0;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= i; j++){
sumVar += i;
}
}
return sumVar;
}
int main(){
int n = 7;
cout<<"The sum of series till "<<n<<" is "<<calcSeriesSum(n);
return 0;
} Đầu ra
The sum of series till 7 is 140
Giải pháp này đơn giản nhưng không hiệu quả vì nó có hai vòng lặp lồng nhau làm phức tạp thời gian của thứ tự O (n2) .
Một Giải pháp hiệu quả dựa trên thực tế là nếu một số (n) được thêm vào chính nó n lần. Sau đó, kết quả có thể đạt được bằng cách nhân số với chính nó.
tức là 5 + 5 + 5 + 5 + 5 =5 * 5.
Vì vậy, chúng ta có thể sử dụng phép nhân thay vì một vòng lặp để giải quyết vấn đề.
Thuật toán
Khởi tạo - sumVal =0;
- Bước 1 - vòng lặp cho i -> 0 đến n.
- Bước 2 - cập nhật sumVal, sumVal + =(i * i)
Chương trình minh họa hoạt động của giải pháp của chúng tôi
Ví dụ
#include <iostream>
using namespace std;
int calcSeriesSum(int n){
int sumVar = 0;
for(int i = 1; i <= n; i++){
sumVar += (i*i);
}
return sumVar;
}
int main(){
int n = 7;
cout<<"The sum of series till "<<n<<" is "<<calcSeriesSum(n);
return 0;
} Đầu ra
The sum of series till 7 is 140
Giải pháp tốt hơn vì nó chỉ cần một vòng lặp và có độ phức tạp về thời gian là O (n). Nhưng đó không phải là giải pháp tốt nhất có thể vì điều tương tự có thể được thực hiện với độ phức tạp O (1) thời gian.
Giải pháp hiệu quả nhất đang sử dụng một công thức chung cho tổng của chuỗi đã cho.
Tổng của chuỗi =
1 + 2 + 2 + 3 + 3 + 3 +…. N.
Điều này có thể được thực hiện như
1 + (2+2) + (3+3+3) + … + (N+N+N..N) 1*1 + 2*2 + 3*3 + … N*N. 12 + 22 + 32 + … N2.
$ Sum =\ sum _ {\ square =1} ^ \ square \ blacksquare \ square ^ 2 $
Công thức tổng bình phương là n * (n + 1) * (2n + 1) / 6. Và chúng ta cũng có thể tìm thấy tổng bằng cách sử dụng công thức này.
Chương trình minh họa hoạt động của giải pháp của chúng tôi
Ví dụ
#include <iostream>
using namespace std;
int calcSeriesSum(int n){
int sumVar = 0;
sumVar = ((n*(n + 1)*( 2 * n + 1))/6 );
return sumVar;
}
int main(){
int n = 7;
cout<<"The sum of series till "<<n<<" is "<<calcSeriesSum(n);
return 0;
} Đầu ra
The sum of series till 7 is 140