Thuật toán tính tổ hợp chập k của n phần tử sử dụng C/C++

Hôm nay mình sẽ cùng các bạn tìm hiểu cách tính tổ hợp trong C/C++. Tổ hợp là cách ta chọn một nhóm phần tử từ một tập hợp lớn hơn mà không phân biệt thứ tự.

Ví dụ: Chọn 2 trong 4 phần tử của M={0;1;2;3}. Ta sẽ có 6 cách chọn C1={0;1}, C2={0,2}, C3={0,3}, C4={1,2}, C5={1,3}, C6={2,3}.

Tính tổ hợp bằng đệ quy

Chúng ta có các tính chất sau:

• 
• 

Cài đặt thêm công thức truy hồi sau:

Dựa vào hai điều kiện trên ta có thể tính tổ hợp với đoạn code sau:

Xem code

Tuy nhiên phương pháp đệ quy luôn có nhược điểm là tốc độ chậm nếu input lớn một chút. Chính vì vậy dựa vào một tính chất khác ta có một cách tính khác rút ngắn được một chút thời gian.

Tính tổ hợp thông qua giai thừa

 

Dựa vào công thức trên đây ta đi xây dựng thêm một hàm tính giai thừa nữa như sau:

Xem code

Mặc dù nhanh hơn cách một nhưng phương pháp này không thể tính được một số quá lớn do hàm tính giai thừa vượt quá bộ nhớ. Ở đây ra chỉ làm ví dụ minh họa đơn giản mình chỉ khai báo kiểu int, các bạn nên khai báo lại với một kiểu lớn hơn.

Bài viết của mình tới đây là hết, hẹn gặp lại các bạn ở một bài viết khác.