PDA

View Full Version : Giúp tôi với ......



tieudongtadn
25-09-2004, 23:57
Cho m bi đỏ, n bi xanh được đặt trong m + n + k ( k>=0) ô. Viết chương trình in ra các cách sắp xếp không trùng nhau.

songok
26-09-2004, 07:49
Theo y tui nhung bai nhu vay dung cac giai thuat thu sai ( heuristic...) nhung ban khong noi ro khong trung nhau o day la 2 bi lien tiep khong trung nhau, hay la 2 cach sap xep ko trung nhau, gioi han cua m, n va k ?

minhlazy
26-09-2004, 07:58
Bài này có thể sử dụng thuật toán generate để sinh dãy nhị phân với bi xanh=0 và bi đỏ=1 sau đó tìm cách chèn các ô trống vào vị trí thích hợp. Không biết ý kiến các bạn thế nào?

black hole
27-09-2004, 12:05
Bài này có thể sử dụng thuật toán generate để sinh dãy nhị phân với bi xanh=0 và bi đỏ=1 sau đó tìm cách chèn các ô trống vào vị trí thích hợp. Không biết ý kiến các bạn thế nào?

nếu thế sao không sinh ra dãy ở hệ cơ số 3 luôn đi, 2 là màu đỏ, 1 là màu xanh, 0 là trống.
Nhưng nói chung là không được đâu, dạng này thì đúng nhưng chậm lắm.
vì hệ cơ số 3 có m+n+k chữ số ( giả sử m+n+k = 30) thì cũng cớ 3^30 = 205891132094649 trường hợp! Khiếp không

tieudongtadn
27-09-2004, 23:48
Đây là bài toán thực tế mà tôi cần phải giải quyết đấy các bác, nên đòi hỏi thuật toán phải tối ưu. m+n+k <=20 thôi!!!
Số bi đỏ chạy từ 1-> 20
Số bi xanh chạy từ 0 đến -> (20 - số bi đỏ)
Tôi dùng phương pháp số liền kề
VD : Cò 2 bi đỏ, 3 bi xanh
Tôi đặt bi đỏ là 0, Bi xanh là 1, o còn lại đặt 3
Tôi có dãy số sau
0011133333333333333333333
tôi dùng thuật toán tìm số liền kề của số trên tôi được dãy số:00113333.....31
Sau đó gọi đệ qui cho dãy số vừa tìm được

Bác nào có phương pháp nào hay hơn chỉ giúp tôi với....cảm ơn.