Giải thuật sắp xếp những người đủ tiêu chuẩn có thể lên tàu

haluxu · 14-08-2011, 09:55 PM

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.

Giải thuật của em như sau:

Code:

int i = 0, vip_in_one_toa_count = 0, toa_count=0; 

for (i=1; i<=PERSON_NO; i++) {
     if (card_vip == TRUE) {

          Đưa người vào toa;

          vip_in_one_toa_count += 1;
          
          if ((vip_in_one_toa_count == 100) && (toa_count*100 + vip_in_one_toa_count < VIP_NO)) {

               flag = FALSE;

               Lắp toa vào đoàn tàu;

               toa_count += 1;

               vip_in_one_toa_count = 0;
          }
     }
}
flag = TRUE;
Lắp toa vào đoàn tàu;

Kết thúc việc sắp xếp bố trí người và tàu;

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.

fbchicken · 15-08-2011, 02:47 AM

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;

haluxu · 15-08-2011, 06:51 PM

Nguyên bản được gửi bởi fbchicken

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;

Mình thấy code của bạn bổ sung như thế thì có vẻ gọn lại được mỗi phần gán giá trị flag. Còn lại trong vòng for bạn đã tăng thêm 1 lần so sánh so với code của mình rồi.
Ví dụ code của bạn là:

Code:

for (i=1; i<=PERSON_NO && VIPs_entered < VIP_NO; i++) {
     if (card_vip == TRUE) {

          ...

          if ((VIPs_entered % 100 == 0) || VIPs_entered == VIP_NO) {

          ...

          }
     }
}

Còn code của mình là:

Code:

for (i=1; i<=PERSON_NO; i++) {
     if (card_vip == TRUE) {
         
          ...
          
          if ((vip_in_one_toa_count == 100) && (toa_count*100 + vip_in_one_toa_count < VIP_NO)) {

          ...
          }
     }
}

Rõ ràng là mình chỉ so sánh 2 lần, còn bạn so sánh 3 lần. Nếu vòng for lặp rất nhiều lần thì sẽ ảnh hưởng đến performance của chương trình.
Anyway rất cảm ơn bạn đã cho mình một hướng nhìn mới. Có bạn nào có thuật toán nào khác nữa không, càng ít so sánh càng tốt

haluxu · 15-08-2011, 07:59 PM

Đọc kỹ lại thấy code của bạn vẫn chưa ok lắm rồi, trong vòng for bạn đang có thêm kiểm tra 1 điều kiện nữa là

Code:

       VIPs_entered == VIP_NO

Vị chi bạn đã có kiểm tra tới 4 điều kiện.

birthis · 15-08-2011, 09:07 PM

Trời, tính từng câu lệnh như bạn thì có thể thử cách này. Vì đã biết trước được số vip và số người tối đa trên mỗi toa nên bạn có thể tạm thời bỏ câu lệnh

Code:

toa_count*100 + vip_in_one_toa_count < VIP_NO

sang 1 bên. Trước khi vào vòng lặp, bạn sẽ tính sẵn số toa cần thiết để nhét hết số vip này. Khi tiến vào vòng lặp bạn chỉ việc kiểm tra xem toa đã đầy hay chưa. Nếu toa đầy thì mới kiểm tra xem đã đủ số toa hay chưa, nếu còn thiếu thì cứ tiếp tục vòng lặp. Lưu ý là toa cuối cùng có thể chứa số lẻ các khách vip, vì vậy bạn dùng vòng lặp riêng để đưa số khách còn lại này vào toa.

Triển khai là như thế này:

C Code:

Select All | Show/Hide

int i = 0, vip_in_one_toa_count = 0, toa_count=0;
int so_toa_can_thiet = so_vip/max_so_nguoi_tren_1_toa;
if (so_toa_can_thiet > 0){
for (i=1;;i++) {
if (card_vip == TRUE) {
//Đưa người vào toa;
vip_in_one_toa_count += 1;
if ((vip_in_one_toa_count == 100))) {
//Lắp toa vào đoàn tàu;
toa_count += 1;
if (toa_count == so_toa_can_thiet) break;
}
}
}
}
//Đưa nốt số vip còn lại vào toa cuối cùng
for (;i<=PERSON_NO;i++){
if (card_vip == TRUE) {
//Đưa người vào toa;
}
}
//Lắp toa vào đoàn tàu
//Kết thúc việc sắp xếp bố trí người và tàu;

haluxu · 15-08-2011, 09:54 PM

Nguyên bản được gửi bởi birthis

Triển khai là như thế này:

C Code:

Select All | Show/Hide

int i = 0, vip_in_one_toa_count = 0, toa_count=0;
int so_toa_can_thiet = so_vip/max_so_nguoi_tren_1_toa;
if (so_toa_can_thiet > 0){
for (i=1;;i++) {
if (card_vip == TRUE) {
//Đưa người vào toa;
vip_in_one_toa_count += 1;
if ((vip_in_one_toa_count == 100))) {
//Lắp toa vào đoàn tàu;
toa_count += 1;
if (toa_count == so_toa_can_thiet) break;
}
}
}
}
//Đưa nốt số vip còn lại vào toa cuối cùng
for (;i<=PERSON_NO;i++){
if (card_vip == TRUE) {
//Đưa người vào toa;
}
}
//Lắp toa vào đoàn tàu
//Kết thúc việc sắp xếp bố trí người và tàu;

Cảm ơn bạn, như vậy thì theo mình nghĩ i nên được khởi tạo = 1 ngay từ đầu vì nếu so_toa_can_thiet = 0 thì vòng lặp sau sẽ được thực hiện đúng.

Code:

//Đưa nốt số vip còn lại vào toa cuối cùng
for (;i<=PERSON_NO;i++){
    if (card_vip == TRUE) {
              //Đưa người vào toa;
         }
}

Nhưng còn 1 yêu cầu của bài toán nữa là đặt cho mỗi toa 1 cờ flag = TRUE nếu toa cuối, = FALSE nếu chưa là toa cuối. Với lại mình nghĩ giải thuật của bạn với của mình tốc độ như nhau, nhưng có vẻ như bạn code dài hơn mình thì phải.

Cái khó của mình là khi show code cho khách hàng họ xem vẫn chưa đồng ý là tối ưu và tiết kiệm code. Trên thực tế bài toán của mình không phải là đoàn tàu, mình chỉ biến tấu ra cho dễ hiểu và PERSON_NO của mình có giá trị max lên tới 4 byte cơ. Đây chỉ là một function nhỏ của hàm main. Cả chương trình chỉ có duy nhất 1 out most process. Nếu function nhỏ của mình chạy lâu thì khi out most process của mình nhận được tín hiệu cần xử lý việc khác nó sẽ không xử lý được cho đến khi function nhỏ của mình chạy xong. Vì vậy mình rất cần tối ưu hóa chương trình. Khách hàng họ yêu cầu trong vòng for của mình chỉ kiểm tra duy nhất một lệnh if thôi. Hic hic

birthis · 15-08-2011, 10:18 PM

uh nhỉ, mình quên mất là trong lệnh if của bạn có toán tử &&.
Nhưng mà: - Trong code của mình đã bỏ đi câu lệnh kiểm tra i<=PERSON_NO
- Và 1 số phép tính toán như nhân, cộng (ở câu lệnh ở trong lệnh if, phía sau toán tử &&).
- Mình chia code ra, thì code dài hơn nhưng mà hiệu năng thì không thay đổi (có thể là hơn).
- Việc thêm flag vào thì quá dễ.
- Chỉ dùng 1 lệnh if ? Có thể ư ?

haluxu · 15-08-2011, 10:44 PM

Nguyên bản được gửi bởi birthis

uh nhỉ, mình quên mất là trong lệnh if của bạn có toán tử &&.
Nhưng mà: - Trong code của mình đã bỏ đi câu lệnh kiểm tra i<=PERSON_NO
- Và 1 số phép tính toán như nhân, cộng (ở câu lệnh ở trong lệnh if, phía sau toán tử &&).
- Mình chia code ra, thì code dài hơn nhưng mà hiệu năng thì không thay đổi (có thể là hơn).
- Việc thêm flag vào thì quá dễ.
- Chỉ dùng 1 lệnh if ? Có thể ư ?

You're right, code của bạn tối ưu hơn. Nhưng thêm flag thế nào cho chuẩn nếu so_vip chia hết cho max_so_nguoi_tren_1_toa?
Ví dụ so_vip = 100, 200, 300 thì toa cuối cùng làm sao set flag = TRUE? Làm sao để có thể nhận ra đó là toa cuối cùng?

- Chỉ dùng 1 lệnh if? Mình đang băn khoăn kg biết có thể hay không?

Thank you so much

birthis · 15-08-2011, 10:50 PM

Nguyên bản được gửi bởi haluxu

You're right, code của bạn tối ưu hơn. Nhưng thêm flag thế nào cho chuẩn nếu so_vip chia hết cho max_so_nguoi_tren_1_toa?
Ví dụ so_vip = 100, 200, 300 thì toa cuối cùng làm sao set flag = TRUE? Làm sao để có thể nhận ra đó là toa cuối cùng?

- Chỉ dùng 1 lệnh if? Mình đang băn khoăn kg biết có thể hay không?

Thank you so much

- Theo mình thì thêm flag = false vào trong hàm for thứ nhất, ở cùng đoạn với toa_count += 1;
Còn flag = true thì thêm vào dưới vòng for thứ 2 vì vòng for thứ 2 tức là toa cuối rồi. À quên, nếu chia hết thì mình chưa nghĩ tới. hì hì
- Nếu yêu cầu của bạn là trong vòng for chỉ được dùng 1 lệnh if, và nếu có thêm điều kiện là được dùng hàm, thì việc nhồi nhét, biến đổi để có được 1 lệnh if là có thể. Nhưng mà hiệu năng thì không thay đổi có khi còn chậm hơn,

và không được sáng sủa code nữa.

-Giải pháp cho thắc mắc trên là thai nghén thêm 1 lệnh if nữa (chỉ thừa lệnh if thôi, còn hiệu năng thì không ảnh hưởng mấy).

haluxu · 16-08-2011, 12:28 AM

Sau một hồi loay hoay thì mình đổi phương pháp, check xem nếu cho người mới vào thì có full hay không rồi mới cho người vào
Giải thuật mình như sau, các bạn xem có ổn không nhé:

Code:

int i = 1, VIPs_entered_next = 1; 

memset(toa);

for (i=1; i<=PERSON_NO; i++) {
     if (card_vip == TRUE) {       
                   
          if (VIPs_entered_next > 100) {
               flag = FALSE;
               Lap_toa_vao_doan_tau();
			   
	       memset(toa);
               VIPs_entered_next = 1;
          }
		  
          Dua_nguoi_vao_toa();
	  VIPs_entered_next += 1;
     }
}
flag = TRUE;
Lap_toa_vao_doan_tau();

Ket_thuc_bo_tri_nguoi();

Đề tài: Giải thuật sắp xếp những người đủ tiêu chuẩn có thể lên tàu

Các công cụ đề tài

Display

Giải thuật sắp xếp những người đủ tiêu chuẩn có thể lên tàu

Giải thuật sắp xếp những người đủ tiêu chuẩn có thể lên tàu

Các đề tài tương tự

Quần thon eo giảm mỡ bụng tiêu chuẩn xuất Nhật

SIM tích hợp NFC sẽ là tiêu chuẩn toàn cầu

làm thế nào khi chọn nào tiêu đề thì hiện lên nội dung chi tiết về tiêu đề đó

Thiết kế giải thuật để chuẩn hoá xâu S không còn 2 ký tự giống nhau đứng liền

Quyền hạn của bạn