Tam giác Pascal có thể được tạo như sau. Ở hàng trên cùng, có một mảng gồm 1. Hàng tiếp theo được tạo bằng cách thêm số ở trên và bên trái với số ở trên và bên phải, coi các phần tử trống là 0
Một vài hàng đầu tiên là
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
ví dụ 1
Đầu vào
n = 3
đầu ra
[1, 3, 3, 1]
Giải trình
Đây là hàng 3 trong
[1]
[1, 1]
[1, 2, 1]
[1, 3, 3, 1]
Tính tam giác Pascal
Chúng ta có thể tính toán các giá trị tại Tam giác Pascal bằng Thuật toán lập trình động. Giá trị tại p[i][j] bằng p[i – 1][j] + p[i – 1][j – 1]. Do đó, chúng tôi có thể lặp lại cập nhật hàng [kích thước có thể được xác định trước]
1 2 3 4 5 6 7 8 9 10
vector solve[int n] { vector res[n + 1, 0]; res[0] = 1; for [int i = 0; i 0; -- j] { res[j] += res[j - 1]; } } return res; }
vector solve[int n] {
vector res[n + 1, 0];
res[0] = 1;
for [int i = 0; i 0; -- j] {
res[j] += res[j - 1];
}
}
return res;
}Độ phức tạp thời gian là O[N^2] và độ phức tạp không gian là O[N]
Triển khai Tam giác Pascal
- Dạy Bé Lập Trình – Thuật Toán Pascal Và Ứng Dụng
- Bài tập mã hóa – Tam giác Pascal II – Giải pháp C ++ và Python
- Cách in Tam giác Pascal trong C++ [kèm mã nguồn]
- Tính hàng thứ n của tam giác Pascal bằng thuật toán lập trình động
- GoLang. Tạo Tam giác Pascal
–EOF [Blog máy tính & công nghệ cơ bản] —
Xếp hạng sao GD
đang tải
Bài cuối. Hai con trỏ với thuật toán cửa sổ trượt để tính chuỗi con dài nhất có nhiều nhất K ký tự riêng biệt
Bài tiếp theo. Chuyển đổi một chuỗi thành định dạng trường hợp lạc đà trong C ++
URL Vĩnh viễn là. Tính toán hàng thứ n của tam giác Pascal bằng thuật toán lập trình động [Phiên bản AMP]
bài viết liên quan
Dạy Lập Trình Cho Bé - Thuật Toán Lập Trình Động Tính Tổng Đường Đi Tối Thiểu Tam Giác
Cho một mảng tam giác, trả về tổng đường dẫn tối thiểu từ trên xuống dưới. Cho mỗi…
Dạy Bé Lập Trình - Thuật Toán Tam Giác Pascal Và Ứng Dụng
Tam giác Pascal trông như thế này. [1] [1, 1] [1, 2, 1] [1, 3, 3,…
Thuật toán tính giá trị của Tam giác Pascal
Câu đố là tạo ra một vài hàng numRows đầu tiên của Tam giác Pascal. Bạn có…
Dạy Lập Trình Cho Bé - Nhập Môn Thuật Toán Lập Trình Động
Thuật toán lập trình động là gì?
Tam giác Pascal là một trong những bài toán phổ biến nhất. Nó sắp xếp số theo hình tam giác. Nói cách khác, Nó là một mảng có dạng tam giác bao gồm các hệ số nhị thức. Chương trình Tam giác Pascal trong ngôn ngữ C có thể được thực hiện theo nhiều cách khác nhau bao gồm cách tiếp cận vũ phu sau đó chúng ta có thể tối ưu hóa mã để giảm độ phức tạp về thời gian và độ phức tạp về không gian
Phạm vi
Trong bài viết này chúng ta sẽ tìm hiểu chi tiết về các khái niệm sau
- Tam giác Pascal và các ví dụ của nó là gì?
- Cách thực hiện tam giác pascal trong C
- Các phương pháp thực hiện tam giác pascal trong C
- Cách tiếp cận vũ phu
- Phương pháp tối ưu hóa thời gian phức tạp
- Phương pháp tiếp cận độ phức tạp không gian được tối ưu hóa
Tam giác Pascal là gì?
Tam giác Pascal là một sự sắp xếp [mảng] hình tam giác của các số hiển thị các hệ số nếu một biểu thức nhị thức được mở rộng. Các số bên trong mẫu tam giác Pascal được thiết kế sao cho mỗi số sẽ là tổng của hai số gần nhất ở hàng trên của tam giác và các số ở hai cực của mỗi hàng của tam giác sẽ là 1
Nó là một mảng tam giác gồm các hệ số nhị thức được sử dụng rộng rãi trong các bài toán đại số, lý thuyết xác suất và Tổ hợp. Tam giác Pascal là tam giác đặc biệt được đặt tên theo nhà toán học người Pháp Blaise Pascal. Nói chung, tam giác Pascal được sử dụng để tìm kết quả của một đồng xu, hệ số khai triển nhị thức theo xác suất, v.v.
Bây giờ chúng ta hãy tìm hiểu thêm về mô hình tam giác pascal với sự trợ giúp của một ví dụ
Ví dụ về Tam giác Pascal
Trên đây là một biểu diễn của tam giác pascal trong đó các số được sắp xếp theo cách mà chúng ta có 1 ở cả hai cực trị hoặc các cạnh của tam giác cho đến hết. Các số ở giữa tam giác là tổng của hai số ở hàng trên. Hàng trên cùng trong tam giác pascal được coi là hàng thứ 0 của tam giác. Tiếp theo là hàng tiếp theo được gọi là hàng đầu tiên và sau đó là hàng thứ 2, v.v. Phần tử ở ngoài cùng bên trái của một hàng được coi là phần tử thứ 0 trong hàng đó. Với quy ước này, số phần tử bên trong hàng thứ n bằng [n+1] phần tử trong hàng cụ thể đó
Tam giác Pascal được thiết kế bằng cách có 1 là phần tử đầu tiên và cuối cùng của một hàng và bằng cách dễ dàng cộng các cặp số liên tiếp ở hàng trước rồi viết chúng vào dòng mới
Làm thế nào để viết các chương trình tam giác Pascal trong C?
Như chúng ta đã thảo luận ở các phần trước, tam giác Pascal là một tam giác đặc biệt có sự sắp xếp các hệ số nhị thức. Các số trong tam giác pascal được sắp xếp sao cho mỗi hàng của tam giác bắt đầu bằng 1 và các phần tử ở giữa là tổng của hai phần tử gần nhất của hàng trên
Bây giờ, hãy hiểu cách chúng ta có thể thực hiện hoặc viết chương trình tam giác Pascal bằng ngôn ngữ C
Chúng ta sẽ viết hàm dựng tam giác pascal trong C, nhập vào là n và in ra n dòng đầu tiên của tam giác Pascal
Chúng ta có thể thực hiện tam giác Pascal trong C theo ba cách khác nhau như sau. -
- Cách tiếp cận vũ phu
- Phương pháp tối ưu hóa thời gian phức tạp
- Phương pháp tiếp cận độ phức tạp không gian được tối ưu hóa
Bây giờ, hãy hiểu mọi cách tiếp cận với việc thực hiện nó
Phương pháp 1. Lực lượng vũ phu
Giới thiệu
Trong cách tiếp cận này, chúng tôi sẽ sử dụng một cách tiếp cận đơn giản để in tam giác Pascal bằng cách sử dụng định lý nhị thức. Ở đây chúng tôi đã sử dụng các công thức giai thừa và kết hợp để thực hiện chương trình Tam giác Pascal trong C
Bây giờ chúng ta cùng xem code của chương trình để hiểu rõ hơn cách tiếp cận
cú pháp
//Pascal Triangle program in C #include int fact[int n] //function to calculate factorial of a number { int a; for [a = 1; n > 1; n--] a *= n; return a; } int combination[int n, int r] { return fact[n] / [fact[n - r] * fact[r]]; // using the mathematical formula of combination nCr } int main[] { int rows; int i, j; //number of rows of pascal's triangle to be printed printf["Enter Number of Rows: "]; scanf["%d", &rows]; for [i = 0; i