
Nguyên bản được gửi bởi
haluxu
Xin chào các anh em,
Mình có 1 bài toán sau, mình đã thực hiện chạy rất tốt nhưng vẫn chưa hài lòng về thuật toán. Các bạn xem rồi tư vấn cho mình có thuật toán nào tối ưu hơn không nhé:
Nhà ga Hà Nội cần bố trí 1 đoàn tàu cho 1 chuyến tàu VIP gồm PERSON_NO người trong đó có VIP_NO người là VIP (VIP_NO <= PERSON_NO). Mỗi người VIP có 1 cái thẻ (card_vip = TRUE). Nếu người bình thường thì card_vip = FALSE. Mỗi toa tàu có thể chở được tối đa 100 người.
Yêu cầu:
- Chuyến tàu này chỉ chở những người có thẻ VIP
- Duyệt từ 1 cho đến PERSON_NO người, chọn trong những người đó người nào có thẻ card_vip = TRUE thì đưa lên tàu. Sắp xếp người vào các toa tàu cho đến khi hết người vip thì thôi. Mỗi lần sắp xếp xong 1 toa tàu thì nối toa ấy vào đoàn tàu
- Nếu chưa phải là người VIP cuối cùng thì toa đó có một cái cờ màu xanh (flag = FALSE). Nếu là người VIP cuối cùng thì toa đó đặt một cái cờ màu đỏ (flag = TRUE) và kết thúc việc sắp xếp bố trí nhồi người VIP vào các toa.
...
Các bác xem có giải thuật nào hay hơn, ngắn gọn và tối ưu hơn không? Rất cảm ơn. Cái em cần là giải thuật nên không cần phải đúng cú pháp lập trình C.
Yêu cầu bài toán quá đơn giản nên cũng chẳng có chỗ nào để tối ưu. Mình thay đổi 1 vài chỗ nhỏ như con muỗi:
Code:
int i = 0, vip_in_one_toa_count = 0, toa_count=0, VIPs_entered = 0;
for (i=1; i<=PERSON_NO && VIPs_entered < VIP_NO; i++) {
if (card_vip == TRUE) {
Đưa người vào toa;
++VIPs_entered;
if ((VIPs_entered % 100 == 0) || VIPs_entered == VIP_NO) {
flag = (VIPs_entered == VIP_NO);
Lắp toa vào đoàn tàu;
//toa_count += 1; không cần; số toa có thể tính bằng 1 phép chia ngoài vòng lặp
}
}
}
Kết thúc việc sắp xếp bố trí người và tàu;