Bài tập thực hành Toán rời rạc - Thực hành 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 2 5 1 4 5 1 1 2 5 3 4 2 2 4 3 2 1 5 4 3 1 3 4 2 5 3 4 1 2 4 5 3 1 5 3 5 2 1 4 5 2 1 4 3 4 3 5 1 2 1 2 3 4 5 2 3 4 1 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 2M và mọi cô gái w 2W 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 /* w hiện tại đang đính hôn với m0 */ if w thích m0 hơn m then m lại trở thành độc thân; else /* w thích m hơn m0 */ (m;w) đính hôn với nhau; m0 trở thành độc thân; return tập S gồm các cặp đính hôn; 3