Bài tập Toán rời rạc - Bài thực hành số 9
Toán Rời Rạc
Thực hành 9
Có n chàng trai và n cô gái. Mỗi chàng trai m xếp hạng các cô gái dưới dạng một dãy
w1, w2, . . . , wn.
Ta nói rằng chàng trai m thích cô wi hơn cô wj nếu cô wi đứng trước cô wj trong dãy này.
Ta gọi dãy này là danh sách ưu tiên của m. Tương tự, mỗi cô gái cũng có một danh sách
ưu tiên của mình.
Cần tìm cách ghép cặp mỗi chàng trai với một cô gái để tổ thức đám cưới sao cho không
tồn tại hai người khác giới thích nhau hơn vợ/chồng của họ. Những cuộc hôn nhân như
vậy gọi là ”bền vững”.
• Dữ liệu vào gồm:
– Dòng đầu tiên là số n.
– n dòng tiếp theo, mỗi dòng gồm n số nguyên là danh sách ưu tiên của mỗi chàng
trai.
– n dòng tiếp theo, mỗi dòng gồm một dãy n số nguyên là danh sách ưu tiên của
mỗi cô gái.
• Dữ liệu ra gồm: n cặp i, j thể hiện sẽ tổ chức đám cưới cho chàng trai i và cô gái j
đảm bảo họ có cuộc hôn nhân bền vững.
Ví dụ: Xét bảng dữ liệu vào và ra như sau:
Dữ liệu vào
Dữ liệu ra
5
3
1
4
1
1
2
2
3
3
2
5
5
2
4
4
1
3
1
2
5
4
4
5
5
3
5
2
4
3
1
1
2
3
4
5
3
5
4
1
2
5
2
3
2
3
2
1
5
3
4
1
4
1
4
1
4
3
2
5
5
1
• Dòng đầu tiên ở cột Dữ liệu vào chỉ ra rằng có 5 chàng trai và 5 cô gái.
• 5 dòng tiếp theo lần lượt là danh sách ưu tiên của chàng trai 1, 2,. . ., 5 đối với các
cô gái. Ví dụ, bảng trên chỉ ra rằng: chàng 1 thích
– cô 3 hơn cô 2,
– cô 2 hơn cô 5,
– cô 5 hơn cô 1,
– cô 1 hơn cô 4.
• 5 dòng tiếp theo lần lượt là danh sách ưu tiên của cô 1, cô 2,…, cô 5 đối với các chàng
trai. Ví dụ, bảng trên chỉ ra rằng: cô 1 thích
– chàng 3 hơn chàng 5,
– chàng 5 hơn chàng 2,
– chàng 2 hơn chàng 1,
– chàng 1 hơn chàng 4.
• Còn cột Dữ liệu ra chỉ ra rằng ta có thể ghép chàng 5 với cô 1, chàng 2 với cô 2,
chàng 4 với cô 3, chàng 3 với cô 4, và chàng 1 với cô 5 để các cuộc hôn nhân đều bền
vững.
2
Algorithm 1: Thuật toán Gale-Shapley
Khởi tạo mọi chàng trai m ∈ M và mọi cô gái w ∈ W là độc thân;
while có một chàng trai m độc thân và vẫn chưa đính hôn với cô gái nào do
Chọn chàng trai m này;
Xét w là cô gái m thích nhất trong danh sách những cô mà m chưa đề nghị cưới;
if w là độc thân then
(m, w) đính hôn;
else
if w thích m′ hơn m then
m lại trở thành độc thân;
/* w hiện tại đang đính hôn với m′ */
else
/* w thích m hơn m′ */
(m, w) đính hôn với nhau;
m′ trở thành độc thân;
return tập S gồm các cặp đính hôn;
3
3 trang
16160
Free
Bạn đang xem tài liệu "Bài tập Toán rời rạc - Bài thực hành số 9", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
File đính kèm:
- bai_tap_toan_roi_rac_bai_thuc_hanh_so_9.pdf
