คำอธิบายปัญหา
สามเหลี่ยมปาสคาล (Pascal's Triangle) เป็นอาร์เรย์ของสัมประสิทธิ์ทวินาม (binomial coefficients) แถวบนสุดหมายเลข n=0 และในแต่ละแถวหมายเลขจากซ้ายเริ่มที่ k = 0 แต่ละตัวเลขหาได้โดยการบวกสองตัวเลขที่อยู่ในแถวก่อนหน้าและอยู่ตรงเหนือเซลล์ปัจจุบัน มันยังสามารถสร้างได้โดยการหา (𝑛𝐶𝑘) สำหรับหมายเลขแถว n และหมายเลขคอลัมน์ k
สมมติ input คือ 10 ผลลัพธ์จะเป็นดังนี้:
1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1 1 6 15 20 15 6 1 1 7 21 35 35 21 7 1 1 8 28 56 70 56 28 8 1 1 9 36 84 126 126 84 36 9 1
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้:
- for i := 0 to n
- for j = 0 to n – i – 2, พิมพ์ช่องว่าง
- for j := 0 to i, คำนวณ nCr(i, j)
ตัวอย่างโค้ด (C++)
#include<iostream> #include<iomanip> using namespace std; long fact(long n){ int i, fact = 1; for(i = n; i>1; i--) fact *= i; return fact;//factorial of given number } long nCr(long n, long r){ long nume = 1, i; for(i = n; i>r; i--) nume *= i; return long(nume/fact(n-r));//generate result of nCr } void genPascalsTriangle(long n){ for(int i = 0; i<n; i++){ for(int j = 0; j<(n-i-1); j++) cout <<setw(3)<< " ";//printing space to show triangular form for(int j = 0; j<(i+1); j++) cout <<setw(3)<< nCr(i, j) <<setw(3)<< " "; cout << endl; } } main(){ int n; cout << "Enter Number of lines: "; cin >> n; genPascalsTriangle(n); }นำเข้า
10
ผลลัพธ์
1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1 1 6 15 20 15 6 1 1 7 21 35 35 35 21 7 1 1 8 28 56 70 56 28 8 1 1 9 36 84 126 126 84 36 9 1
