Liệt kê tổ hợp chập k của nhóm n phần tử.

[NguyenNgocThuHien]

Giới thiệu cùng mọi người một file dùng để liệt kê tổ hợp chập k của n phần tử. Có một số thành viên có hỏi về vấn đề này nên mình làm thử, cũng thấy ngon ngon. Chỉ việc chạy macro, bấm, bấm, chọn chọn là có thể có kết quả như ý muốn.
Link file: https://drive.google.com/drive/folders/1hpD6jvBPgaYTGOaQdCyYtNYr4a2ltIbj

Mọi chi tiết tham khảo video sau:

 

[vanthinh3101]

Giới thiệu cùng mọi người một file dùng để liệt kê tổ hợp chập k của n phần tử. Có một số thành viên có hỏi về vấn đề này nên mình làm thử, cũng thấy ngon ngon. Chỉ việc chạy macro, bấm, bấm, chọn chọn là có thể có kết quả như ý muốn.
Link file: https://drive.google.com/drive/folders/1hpD6jvBPgaYTGOaQdCyYtNYr4a2ltIbj

Mọi chi tiết tham khảo video sau:

Mình cứ thấy mọi người nói VBA không hợp với con gái.
Trường hợp của bạn là ngoại lệ rồi, cao thủ là đằng khác.

 

[huuthang_bd]

Những dạng này nên dùng phương pháp đệ quy.

 

[anhtuanle123]

thuật toán tính tổ hợp này nếu làm rành sẽ làm đc nhiều việc hay ho đấy ^^
có thể làm đc bài toán dạng này chẳng hạn !
đề bài : Đưa 5 người qua sông, mỗi lần thuyền chở được tối đa 2 người và thời gian đi của từng người là 1s, 3s, 6s, 8s, 12s. Nếu thuyền chở 2 người thuyền sẽ đi theo vận tốc của người chậm hơn. Trong 30s hãy đưa cả gia đình qua sông , hỏi có bao nhiêu cách đưa !
http://9mobi.vn/dap-an-game-qua-song-iq-cau-3-dua-mot-gia-dinh-5-nguoi-qua-song-1020n.aspx

 

[VetMini]

Mình cứ thấy mọi người nói VBA không hợp với con gái.
Trường hợp của bạn là ngoại lệ rồi, cao thủ là đằng khác.

"mọi người" của bạn là giới nào vậy?

 

[NguyenNgocThuHien]

Những dạng này nên dùng phương pháp đệ quy.

Sau khi viết xong code trên em cũng thử viết theo dạng đệ quy, so về tốc độ thấy ngang nhau. Đươc cái là tốc độ viết code cí phần nhanh hơn, dễ hiểu hơn.

 

[NguyenNgocThuHien]

"mọi người" của bạn là giới nào vậy?

Khó trả lời phết đấy anh, vì còn phải chứng minh.

 

[NguyenNgocThuHien]

Mình cứ thấy mọi người nói VBA không hợp với con gái.
Trường hợp của bạn là ngoại lệ rồi, cao thủ là đằng khác.

Uồi, trên Gpe nhiều chị em dùng vba điệu nghệ lắm!

 

[NguyenNgocThuHien]

thuật toán tính tổ hợp này nếu làm rành sẽ làm đc nhiều việc hay ho đấy ^^
có thể làm đc bài toán dạng này chẳng hạn !
đề bài : Đưa 5 người qua sông, mỗi lần thuyền chở được tối đa 2 người và thời gian đi của từng người là 1s, 3s, 6s, 8s, 12s. Nếu thuyền chở 2 người thuyền sẽ đi theo vận tốc của người chậm hơn. Trong 30s hãy đưa cả gia đình qua sông , hỏi có bao nhiêu cách đưa !
http://9mobi.vn/dap-an-game-qua-song-iq-cau-3-dua-mot-gia-dinh-5-nguoi-qua-song-1020n.aspx

Đó là bài toán iq, dùng máy tính có khả thi không anh.

 

[VetMini]

Đó là bài toán iq, dùng máy tính có khả thi không anh.

Khả thi. Bài này tôi thấy có bài giải bằng C++

 

[VetMini]

Sau khi viết xong code trên em cũng thử viết theo dạng đệ quy, so về tốc độ thấy ngang nhau. Đươc cái là tốc độ viết code cí phần nhanh hơn, dễ hiểu hơn.

Trên nguyên tắc, đệ quy phải dễ hiểu hơn. Nếu không dễ hiểu là tại vì dùng lô gic cưỡng ép.

 

[VetMini]

Bài toán qua sông này thực tế là biến dạng của bài toán cổ điển "cầm đèn qua cầu".
(qua sông hay qua cầu gì cũng vậy, vấn đề chính là nguyên tắc 2 qua 1 về, và di chuyển theo tốc độ của người chậm hơn)
Trong bài toán cổ điển, nhóm người đông hơn một chút - khoảng 10 người. Và câu hỏi là câu thách đố "tìm cách hữu hiệu nhất (nhanh nhất)"

 

[NguyenNgocThuHien]

Bài toán qua sông này thực tế là biến dạng của bài toán cổ điển "cầm đèn qua cầu".
(qua sông hay qua cầu gì cũng vậy, vấn đề chính là nguyên tắc 2 qua 1 về, và di chuyển theo tốc độ của người chậm hơn)
Trong bài toán cổ điển, nhóm người đông hơn một chút - khoảng 10 người. Và câu hỏi là câu thách đố "tìm cách hữu hiệu nhất (nhanh nhất)"

Liệt kê các chỉnh hợp, ứng với mỗi chỉnh hợp ta tính tổng thời gian. còn nếu tính xem cách nhanh nhất chắc không cần đến liệt kê.

 

[anhtuanle123]

đúng là chỉnh hợp , tổ hợp thì chậm hơn tẹo vì 1 số trường hợp bị trùng , người thứ 1 và thứ 2 qua sông , thì cũng giống người thứ 2 và thứ 1 qua sông !
quy tắc là 2 người đi 1 người về , 2 người đi và 2 người về cũng đc nhưng ko cần thiết vì nó là ko cần thiết !^^
đếm đc 8 cách qua sông với 29s ,
sao trang web đếm đc 30s nhĩ !

 

[VetMini]

đúng là chỉnh hợp , tổ hợp thì chậm hơn tẹo vì 1 số trường hợp bị trùng , người thứ 1 và thứ 2 qua sông , thì cũng giống người thứ 2 và thứ 1 qua sông !
quy tắc là 2 người đi 1 người về , 2 người đi và 2 người về cũng đc nhưng ko cần thiết vì nó là ko cần thiết !^^
đếm đc 8 cách qua sông với 29s ,
sao trang web đếm đc 30s nhĩ !

Trật rồi bạn ơi. Nó chỉ không cần thiết nếu bạn làm con toán tối ưu. Khi khong làm con toán tối ưu thì mọi trường hợp đều phải tính, chỉ là nếu khả năng thời gian cao quá con số được cho thì bỏ qua.
Trên nguyên tắc, nếu giới hạn thời gian là 100 giây chẳng hạn thì vẫn có thể tính các trường hợp 2 ngừoi đi tới đi lui.

Vả lại, bài toán này nếu đếm số lần thì quá dễ. Phải tính ra thuật toán tìm ra cách hiệu quả nhất mới khó.

 

[anhtuanle123]

đồng ý , bài này ko phải là tìm tối ưu , mà là tìm sao cho đúng 30s , ko hơn ko kém ^^

 

[NguyenNgocThuHien]

đúng là chỉnh hợp , tổ hợp thì chậm hơn tẹo vì 1 số trường hợp bị trùng , người thứ 1 và thứ 2 qua sông , thì cũng giống người thứ 2 và thứ 1 qua sông !
quy tắc là 2 người đi 1 người về , 2 người đi và 2 người về cũng đc nhưng ko cần thiết vì nó là ko cần thiết !^^
đếm đc 8 cách qua sông với 29s ,
sao trang web đếm đc 30s nhĩ !

Công nhận là đọc code mình viết ra dễ hiểu thật, còn của người khác thì ứ hiểu được, hoa hết mắt.

Có A B C D
Chọn hai người bất kỳ ( A và B chẳng hạn) để qua sông, sau khi qua sông mỗi bên có 2 người.
Bên này ( có A và B) lại chọn ra một người để sang bên kia chở C hoặc D.

Cuối cùng là một bên có một người, một bên có 3 người, 3 người này lại oàn tù tì để chọn một ngươi sang đón người còn lại. Nghe thuật toán cùng loang ngoang ghê.

 

[VetMini]

đồng ý , bài này ko phải là tìm tối ưu , mà là tìm sao cho đúng 30s , ko hơn ko kém ^^

Nếu không phải tối ưu thì nó chỉ là bài toán vét cạn.

 

[anhtuanle123]

chắc là tối ưu đó , vì cách qua sông của trang web ứng với kết quả thứ 7 !^^

 

[anhtuanle123]

bài 1 cũng dùng tổ hợp hoặc chỉnh hợp nè !