ในปัญหานี้ เราได้รับจำนวน n ซึ่งได้รับ n ขององค์ประกอบของชุดที่ 1, 3, 6, 10 … (ตัวเลขสามเหลี่ยม) งานของเราคือสร้างโปรแกรมเพื่อคำนวณผลรวมของอนุกรม
มาดูตัวเลขสามเหลี่ยมกันก่อนจะคำนวณผลรวมกัน
ตัวเลขสามเหลี่ยมคือตัวเลขที่สามารถแสดงในรูปสามเหลี่ยมได้
สามเหลี่ยมเกิดขึ้นในลักษณะที่แถวแรกมีจุดหนึ่ง จุดที่สองมีจุดสอง เป็นต้น
ตัวอย่าง
มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน
ป้อนข้อมูล
n = 4
ผลผลิต
คำอธิบาย − ผลรวม =T1 + T2 + T3 + T4 =1 + 3 + 6 + 10 =20
วิธีง่ายๆ ในการแก้ปัญหานี้คือการหาตัวเลขสามเหลี่ยม 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.
ตัวอย่าง
โปรแกรมเพื่อแสดงการทำงานของโซลูชันของเรา
#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;
} ผลลัพธ์
Sum of the series 1, 3, 6, 10 ... (Triangular Numbers) is 56
นี่ไม่ใช่วิธีแก้ปัญหาที่มีประสิทธิภาพมากที่สุดเนื่องจากต้องใช้ O(n) ความซับซ้อนของเวลา
วิธีแก้ปัญหาที่มีประสิทธิภาพมากขึ้นคือการใช้สูตรโดยตรงสำหรับผลรวม
ถ้า Ti เป็นจำนวนสามเหลี่ยมที่ i จากนั้น
T1 =1
T2 =3
T3 =6
Tn =n*(n+1) /2
ผลรวมของจำนวนสามเหลี่ยมทั้งหมดคือ
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)]
นี่คือสูตรทั่วไปสำหรับผลรวมของตัวเลขสามเหลี่ยม
ตัวอย่าง
โปรแกรมเพื่อแสดงการทำงานของโซลูชันของเรา
#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;
} ผลลัพธ์
Sum of the series 1, 3, 6, 10 ... (Triangular Numbers) is 56
