Thuật toán tính tổ hợp – Cách tính tổ hợp trong C++

4
4214

Hôm nay mình sẽ giới thiệu đến các bạn cách tính tổ hợp trong c++ bằng phương pháp đệ quy và phương pháp lặp. Nhưng trước tiên ta cùng tìm hiểu tổ hợp là gì nhé ?

Trong Toán học, tổ hợp là cách chọn những phần tử từ một nhóm lớn hơn mà không phân biệt thứ tự. Ví dụ chọn 2 trong 3 phần tử {1, 2, 3 } sẽ có ba cách chọn đó là: {1, 2}, {1, 3}, {2, 3}. Các bạn có thể tham khảo tại đây để hiểu rõ hơn.

Cách tính tổ hợp trong c++ bằng đệ quy

Ta có công thức truy hồi như sau: C^k_n + C^{k+1}_n = C^{k+1}_{n+1}

Với các tính chất sau:

  • C^0_n=C^n_n = 1
  • C^1_n = C^{n-1}_n = n

Từ công thức truy hồi trên ta sẽ dễ dàng viết được một hàm đệ quy để tính tổ hợp như sau:

Sau khi chạy chương trình thì chúng ta sẽ có kết quả sau

Các bạn có thể thấy ở trên mình dùng ba điểm neo để làm điều kiện dừng đó là:

  • Tại k bằng 0 hoặc k bằng n thì ta phải return 1
  • Tại k bằng 1 thì ta return n

Hoàn toàn đúng với các tính chất mình đã trình bày ở trên nhé ^_^

Nhưng nhược điểm của phương pháp đệ quy này lại là tốc độ. không tin thì bạn cứ thử nhập k và n lớn xí nhé !

Cách tính tổ hợp trong c++ bằng phương pháp lặp

Số các tổ hợp chập k của n phần tử: 

Với công thức trên thì ta chỉ cần viết một hàm tính giai thừa là xong rồi phải không nào. Chúng ta cùng bắt đầu nhé

Mặc dù là nhanh nhưng cách làm trên vẫn không thể tính được nhũng số tổ hợp lớn được. Lý do đơn giản là vì khi tính ra giai thừa thì con số đã rất lớn. Đó cũng là lý do mà mình dùng kiểu long long ở trên (Nhưng chẳng nhằm nhò gì ^_^)

Các bạn thử cải thiện chương trình trên xem sao nhé ! Nếu có gặp khó khăn gì thì đừng ngại comment ở phía dưới mình sẽ hỗ trợ các bạn nhiệt tình. Bye !!!

 

avatar
2 Comment threads
2 Thread replies
0 Followers
 
Most reacted comment
Hottest comment thread
3 Comment authors
Nguyễn Văn HiếuTrương Công HữuTâm Recent comment authors
  Subscribe  
newest oldest most voted
Notify of
Tâm
Guest
Tâm

Thầy có thể tính độ phức tạp của giải thuật này giúp em ko?

Nguyễn Văn Hiếu
Admin
Nguyễn Văn Hiếu

Bạn cứ nói, nếu mình biết mình sẽ giúp

Trương Công Hữu
Guest
Trương Công Hữu

Sao anh không thêm k == n – 1. Return n. Anh có thể giải thích giúp.

Nguyễn Văn Hiếu
Admin
Nguyễn Văn Hiếu

Cách này chưa phải là cách tối ưu nhất nhưng dễ hiểu. Bạn có thể rút gọn cái Ckn này rồi tính thay vì cách đang trình bày nhé