Bài toán: Nhập vào một số nguyên dương n. Hãy vẽ ra tam giác Pascal với chiều cao n.
Ý tưởng vẽ tam giác Pascal
Từ hình ảnh trên, chúng ta có thể thấy:
- Hàng thứ nhất chỉ có một số 1. Đây chính là tổ hợp 1.
- Hàng thứ hai có hai số 1. Đây chính là tổ hợp 2.
- Các hàng tiếp theo sẽ là các tổ hợp của i (với i chạy từ 0 đến n-1).
Nếu bạn chưa biết cách tính tổ hợp, có thể xem tại đây.
Với ý tưởng trên, chúng ta sẽ sử dụng hai vòng for lồng nhau để vẽ tam giác Pascal.
- Vòng for thứ nhất đại diện cho số dòng là i, chạy từ 0 đến n-1.
- Vòng for thứ hai đại diện cho tổ hợp chập j của i phần tử (với j chạy từ 0 đến i).
Code tham khảo cách vẽ tam giác Pascal
Cùng xem đoạn code dưới đây:
#include <iostream>
using namespace std;
int C(int k, int n) {
if (k == 0 || k == n) return 1;
if (k == 1) return n;
return C(k - 1, n - 1) + C(k, n - 1);
}
int main(){
int n;
cin >> n;
cout << "-PASCAL-" << endl;
for (int i = 0; i < n; i++) {
for (int j = 0; j <= i; j++) {
cout << C(j, i) << " ";
}
cout << endl;
}
return 0;
}
Sau khi chạy chương trình trên, kết quả sẽ là:
3 -PASCAL-
1 1 1
1 2 1
Vậy là đã đúng với yêu cầu bài toán, nhưng bạn có thấy rằng kết quả khác so với hình ảnh ở trên phải không? Hãy cùng cải thiện chương trình để vẽ ra một tam giác Pascal đẹp hơn nhé!
1 1 1
1 2 1
Bạn có thấy hàng cuối cùng luôn nằm sát với lề không? Trong khi đó, hàng trên lại bị thụt vào một khoảng trống so với hàng dưới.
Nếu hàng thứ n (hàng cuối cùng) không có khoảng trắng, thì hàng thứ n-1 sẽ có 1 khoảng trắng, tương tự cho các hàng khác. Vậy hàng đầu tiên sẽ có (n-1) khoảng trắng, phải không?
Với ý tưởng trên, chúng ta có thể viết lại chương trình như sau:
#include <iostream>
using namespace std;
int C(int k, int n) {
if (k == 0 || k == n) return 1;
if (k == 1) return n;
return C(k - 1, n - 1) + C(k, n - 1);
}
int main(){
int n;
cin >> n;
cout << "-PASCAL-" << endl;
for (int i = 0; i < n; i++) {
for (int j = n; j > i; j--) cout << " ";
for (int j = 0; j <= i; j++) {
cout << C(j, i) << " ";
}
cout << endl;
}
return 0;
}
Sau khi chạy chương trình, kết quả sẽ là:
5 -PASCAL-
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
Bài viết của mình đến đây là kết thúc. Cám ơn các bạn đã theo dõi!
Nguồn: https://tenrenvietnam.com
Danh mục: Tài liệu chia sẻ