Trong bài toán này, chúng ta cho một số n là n phần tử của dãy số 1, 3, 6, 10… (số tam giác). Nhiệm vụ của chúng ta là tạo một chương trình để tính tổng của chuỗi.
Hãy cùng tìm hiểu về các số hình tam giác trước khi tính tổng.
Số hình tam giác là những số có thể được biểu diễn dưới dạng hình tam giác.
Hình tam giác được tạo theo cách sao cho hàng đầu tiên có một điểm, hàng thứ hai có hai điểm, v.v.
Ví dụ
Hãy lấy một ví dụ để hiểu vấn đề,
Đầu vào
n = 4
Đầu ra
Giải thích - tổng =T1 + T2 + T3 + T4 =1 + 3 + 6 + 10 =20
Một cách đơn giản để giải quyết vấn đề này là tìm tất cả n số tam giác. Và thêm lần lượt chúng vào biến tổng.
Thuật toán
Initialise sum = 0. Step 1: loop for i = 0 to n. And follow steps 2 and 3 Step 2: for each value of i, calculate the triangular numbers using the formula, t[i] = ∑ i = i*(i+1)/2. Step 3: Update sum value, sum += t[i]. Step 4: 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>
using namespace std;
int calcSeriesSum(int n) {
int sum = 0;
for (int i=1; i<=n; i++)
sum += i*(i+1)/2;
return sum;
}
int main() {
int n = 6;
cout<<"Sum of the series 1, 3, 6, 10 ... (Triangular Numbers) is "<<calcSeriesSum(n);
return 0;
} Đầu ra
Sum of the series 1, 3, 6, 10 ... (Triangular Numbers) is 56
Đây không phải là giải pháp hiệu quả nhất vì nó tốn O (n), phức tạp về thời gian.
Một giải pháp hiệu quả hơn là sử dụng công thức trực tiếp cho tổng.
Nếu Ti là số thứ i của tam giác. Sau đó,
T1 =1
T2 =3
T3 =6
Tn =n * (n + 1) / 2
Tổng của tất cả các số hình tam giác là
sum = 1 + 3 + 6 + 10 + … sum = T1 + T2 + T3 + … + Tn sum = ∑ (Ti) , i -> 0 to n sum = ∑ (n)(n+1)/2 sum = ½ ∑ n2 + n sum = ½ ∑n^2 + ∑ n sum = ½ [ (n*(n+1)*(2n+1)/6) + (n*(n+1)/2) ] sum = ½ (n*(n+1)/2)*[ (2n+1)/3 + 1 ] sum = ¼ [n*(n+1)]*[(2n+1+3)/3] sum = ¼ [n*(n+1)]*[(2n+4)/3] sum = ¼ [n*(n+1)]*[2(n+2)/3] sum= ⅙ [n*(n+1)*(n+2)]
Đây là công thức chung cho tổng các số tam giác.
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>
using namespace std;
int calcSeriesSum(int n) {
return ( ( n*(n + 1)*(n + 2) )/6);
}
int main() {
int n = 6;
cout<<"Sum of the series 1, 3, 6, 10 ... (Triangular Numbers) is "<<calcSeriesSum(n);
return 0;
} Đầu ra
Sum of the series 1, 3, 6, 10 ... (Triangular Numbers) is 56