Từ 1 tới 10 trên tổng số 10 kết quả

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

  1. #1
    Ngày gia nhập
    03 2011
    Bài viết
    8

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

    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.

  2. #2
    Ngày gia nhập
    07 2011
    Bài viết
    160

    Trích dẫn Nguyên bản được gửi bởi haluxu Xem bài viết
    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;

  3. #3
    Ngày gia nhập
    03 2011
    Bài viết
    8

    Trích dẫn Nguyên bản được gửi bởi fbchicken Xem bài viết
    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

  4. #4
    Ngày gia nhập
    03 2011
    Bài viết
    8

    Đọ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.

  5. #5
    Ngày gia nhập
    03 2010
    Nơi ở
    Nơi nào đó trong vũ trụ
    Bài viết
    550

    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:
    1. int i = 0, vip_in_one_toa_count = 0, toa_count=0;
    2. int so_toa_can_thiet = so_vip/max_so_nguoi_tren_1_toa;
    3. if (so_toa_can_thiet > 0){
    4.     for (i=1;;i++) {
    5.          if (card_vip == TRUE) {
    6.  
    7.               //Đưa người vào toa;
    8.  
    9.               vip_in_one_toa_count += 1;
    10.  
    11.               if ((vip_in_one_toa_count == 100))) {
    12.                    
    13.                    //Lắp toa vào đoàn tàu;
    14.  
    15.                    toa_count += 1;
    16.                    if (toa_count == so_toa_can_thiet) break;
    17.               }
    18.          }
    19.     }
    20. }
    21. //Đưa nốt số vip còn lại vào toa cuối cùng
    22. for (;i<=PERSON_NO;i++){
    23.     if (card_vip == TRUE) {
    24.               //Đưa người vào toa;
    25.          }
    26. }
    27. //Lắp toa vào đoàn tàu
    28. //Kết thúc việc sắp xếp bố trí người và tàu;
    Đã được chỉnh sửa lần cuối bởi birthis : 15-08-2011 lúc 09:17 PM. Lý do: Thêm tí code
    Gió thu lạnh lẽo hắt hiu lòng!

  6. #6
    Ngày gia nhập
    03 2011
    Bài viết
    8

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

    Trích dẫn Nguyên bản được gửi bởi birthis Xem bài viết
    Triển khai là như thế này:

    C Code:
    1. int i = 0, vip_in_one_toa_count = 0, toa_count=0;
    2. int so_toa_can_thiet = so_vip/max_so_nguoi_tren_1_toa;
    3. if (so_toa_can_thiet > 0){
    4.     for (i=1;;i++) {
    5.          if (card_vip == TRUE) {
    6.  
    7.               //Đưa người vào toa;
    8.  
    9.               vip_in_one_toa_count += 1;
    10.  
    11.               if ((vip_in_one_toa_count == 100))) {
    12.                    
    13.                    //Lắp toa vào đoàn tàu;
    14.  
    15.                    toa_count += 1;
    16.                    if (toa_count == so_toa_can_thiet) break;
    17.               }
    18.          }
    19.     }
    20. }
    21. //Đưa nốt số vip còn lại vào toa cuối cùng
    22. for (;i<=PERSON_NO;i++){
    23.     if (card_vip == TRUE) {
    24.               //Đưa người vào toa;
    25.          }
    26. }
    27. //Lắp toa vào đoàn tàu
    28. //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

  7. #7
    Ngày gia nhập
    03 2010
    Nơi ở
    Nơi nào đó trong vũ trụ
    Bài viết
    550

    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ể ư ?
    Gió thu lạnh lẽo hắt hiu lòng!

  8. #8
    Ngày gia nhập
    03 2011
    Bài viết
    8

    Trích dẫn Nguyên bản được gửi bởi birthis Xem bài viết
    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

  9. #9
    Ngày gia nhập
    03 2010
    Nơi ở
    Nơi nào đó trong vũ trụ
    Bài viết
    550

    Trích dẫn Nguyên bản được gửi bởi haluxu Xem bài viết
    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).
    Đã được chỉnh sửa lần cuối bởi birthis : 15-08-2011 lúc 11:02 PM.
    Gió thu lạnh lẽo hắt hiu lòng!

  10. #10
    Ngày gia nhập
    03 2011
    Bài viết
    8

    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();

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

  1. Quần thon eo giảm mỡ bụng tiêu chuẩn xuất Nhật
    Gửi bởi cnatngoan trong diễn đàn Giới thiệu website, sản phẩm của bạn
    Trả lời: 0
    Bài viết cuối: 28-01-2013, 09:42 PM
  2. SIM tích hợp NFC sẽ là tiêu chuẩn toàn cầu
    Gửi bởi simdep2013 trong diễn đàn Giới thiệu website, sản phẩm của bạn
    Trả lời: 0
    Bài viết cuối: 22-11-2011, 09:04 AM
  3. 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 đề đó
    Gửi bởi thuan trong diễn đàn Thắc mắc lập trình ASP.NET
    Trả lời: 2
    Bài viết cuối: 11-08-2011, 07:18 AM
  4. 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
    Gửi bởi wlforever trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 0
    Bài viết cuối: 28-12-2010, 06:23 PM

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

  • Bạn không thể gửi đề tài mới
  • Bạn không thể gửi bài trả lời
  • Bạn không thể gửi các đính kèm
  • Bạn không thể chỉnh sửa bài viết của bạn