Đại học Lê Quý Đôn - 236 Hoàng Quốc Việt - Hà Nội

Chia sẻ kiến thức mọi mặt của các lớp cao học CNTT, Học viện Kỹ thuật Quân sự




Chào mừng đã đến với forum khmt.123.st
  • Bạn chưa đăng kí (hoặc chưa đăng nhập) nên quyền lợi của bạn sẽ bị hạn chế. Việc đăng kí làm thành viên hoàn toàn miễn phí, sau khi đăngkí bạn có thể post bài, tham gia thảo luận , nhìn thấy link ở những box hạn chế ... và rất nhiều quyền lợi khác. Thủ tục đăng kí rất nhanh chóng và đơn giản, hãy Đăng kí làm thành viên !
  • Nếu bạn quên mật khẩu, xin nhấn vào đây !
  • Nếu bạn gặp trục trặc trong vấn đề đăng kí hoặc không thể đăng nhập, hãy liên hệ với chúng tôi.




  • Xem chủ đề cũ hơn Xem chủ đề mới hơn Go down  Thông điệp [Trang 1 trong tổng số 1 trang]

    Admin


    Quản trị viên
    Quản trị viên
    Đề thầy cho:
    Cho dãy có n bản ghi {X(1),...,X(n) trong mỗi bản ghi đều có trường dữ liệu k nhận 1 trong 3 giá trị {1, 2, 3}
    Xây dựng thuật toán thuộc O(n) để sắp xếp X thành dãy không giảm theo k.
    [You must be registered and logged in to see this image.]
    Lời giải của Phan Thị Hải:
    Proc SX (X: Dãy);
    1) i = 1; j = n;
    2). WHILE i ≤ j DO
              a)WHILE ((i ≤ j) & X(i).k = 1) DO i = i + 1;
              b)WHILE ((i ≤ j) & X(i).k ≠ 1) DO j = j - 1;
              c) IF i < j THEN swap (Xi, Xj);
    3) j = n;
    4) WHILE i ≤ j DO
              a) WHILE ((i ≤ j) & X(i).k = 2) DO i = i + 1;
              b) WHILE ((i ≤ j) & X(i).k ≠ 2) DO j = j - 1;
              c) IF i < j THEN swap (Xi, Xj);
    5) Output (X)

    *Độ phức tạp O(n)



    Được sửa bởi Admin ngày Wed Jul 20, 2011 9:26 am; sửa lần 1.


    ================
    Nếu Khách viếng thăm không đọc được các bài trong Kho bài chuẩn, là do Khách viếng thăm không tham gia được vào nhóm [You must be registered and logged in to see this link.]. Sở dĩ nếu Khách viếng thăm không tham gia được vào nhóm [You must be registered and logged in to see this link.] là vì Khách viếng thăm khai báo thiếu họ, thiếu tên, không dấu hoặc khai báo linh tinh trong trường RN. Đừng xin xỏ uỷ quyền, vì uỷ quyền hoàn toàn tự động cho Thành viên đọc được mọi thứ (không chỉnh bằng tay được), các thành viên khác sẽ không bao giờ được uỷ quyền.
    [You must be registered and logged in to see this image.]
    Trang phục may sẵn rẻ nhất Hà Nội ở 148 Vương Thừa Vũ
    ĐT: 043.568.1938

    [You must be registered and logged in to see this link.]
    [You must be registered and logged in to see this link.]
    http://khmt.123.st

    LeVanDat


    Chuyên viên
    Chuyên viên
    Cách giải quyết bài toán của đ/c Hồng là triệt để, nhưng tôi nghĩ rằng trong khi thi có thể mình không thể nhớ hết các cách giải để tối ưu. Tôi nghĩ rằng cách giải sau đây có thể chấp nhận được và ăn điểm, các đ/c cho ý kiến:

    Procedure SapXep(X: dãy số, n: integer)
    1. Khai báo các mảng A, B, C có n phần tử;
    m := 1; n := 1; q := 1;
    2. For i := 1 to n do
              Case X(i).k of
                        1 : A(m) = X(i); m++;
                        2 : B(n) = X(i); n++;
                        3 : C(q) = X(i); q++;
    3. m --; n --; q--;
    4. For i := 1 to n do
                        If i <= m then X(i) := A(i);
                        If ( i > m ) and (i <= m + n) then X(i) := B(i - m);
                        If i > m + n then X(i) : = C(i - m - n);
    5. Output X;

    Thuật toán này có độ phức tạp O(n). Nhưng chúng ta sử dụng tốn bộ nhớ một tí. Thực ra với thời đại máy tính hiện nay, việc sử dụng bộ nhớ không là vấn đề gì, miễn là chương trình của ta chạy luột là được. Tôi nghĩ rằng phương án này chấp nhận được và ăn điểm.

    Admin: Không biết tôi sửa lại cấu trúc có đúng ý đ/c Đạt không. Khi soạn bài hoặc sửa bài viết cần chú ý:
    [You must be registered and logged in to see this image.]
    ForumSystem sẽ tự thay thành các dấu cách. Mỗi chữ trên bằng 1 tab.



    Được sửa bởi Admin ngày Wed Jun 01, 2011 4:19 am; sửa lần 3. (Reason for editing : Viết lại đúng cấu trúc)


    ================

    mrP


    Thành viên cao cấp
    Thành viên cao cấp
    Tôi thấy cách giải của đ/c Đạt là cũng được, độ phức tạp của thuật toán là O(n). Với cách giải này chúng ta cũng nên cần hỏi lại ý kiến của thầy Tĩnh xem thế nào.


    ================
    [You must be registered and logged in to see this image.]

    hienha


    Chuyên viên
    Chuyên viên
    Tôi không có ý kiến gì về cách giải của cả 2 đ/c. về cách giải của đ/c Đạt thì có thể thấy ngay độ phức tạp của thuật toán. Còn về cách giải của đ/c Hồng, đồng ý là độ phức tạp O(n) nhưng có đ/c nào đánh giá thuật toán cụ thể hơn được k?


    ================

    mrP


    Thành viên cao cấp
    Thành viên cao cấp
    Chỉ xét ví dụ về vòng while này nhé

    2. while i <= j do
              a. while (X(i).k = 1) do i = i+1;
              b. while (X(j).k ≠ 1) do j = j-1;
              c. if i < j then swap (Xi, Xj);




    - số lần đổi chỗ lớn nhất n/2 → bỏ qua câu lệnh 2c

    - Số phép cộng, trừ là n

    - Số phép so sánh: Đây là sự dịch chuyển tương đối của i và j lại gần nhau, để dễ hình dung, ta coi j đứng yên (j=n, i chạy từ 1 → n) (trong trường hợp j-- (của câu lệnh 2b), ta sẽ chuyển thành là i++ (của câu lệnh 2a)), rõ ràng số phép so sánh sẽ là 2n.

    - Tổng cộng lại là 7n/2



    Được sửa bởi mrP ngày Wed Jun 01, 2011 10:57 am; sửa lần 1.


    ================
    [You must be registered and logged in to see this image.]

    hienha


    Chuyên viên
    Chuyên viên
    @Phuong: sao lại bỏ qua 2c. Nếu có n/2 phép đổi chỗ thì trong câu lệnh 2c đã có n/2 phép so sánh và 3*n/2 phép gán rồi. Vả lại các vòng while có liên quan đến nhau, nếu chỉ xét 1 vòng while thì nói làm gì :)


    ================

    sonld1984


    Chuyên viên
    Chuyên viên
    1. Nếu không có điều kiện i ≤ j có thể xảy ra lỗi:
    Nếu dãy X không chứa phần tử 1 sẽ dẫn đến lỗi Over Flow tức là phần tử vượt quá dãy
    2. Điều này các bác nên chú ý cho các thuật toán khác nếu không sẽ bị trường hợp tương tự (Ví dụ : sắp xếp phân đoạn)
    trong sách của thày cũng thiếu điều kiện này
    Anh em cho ý kiến nhé!!


    ================

    sonld1984


    Chuyên viên
    Chuyên viên
    Bác Phương xem lại thuật toán của bác đi
    - Bác nên xem lại ý kiến của em đã viết.
    - Cái của Bác mà không có (i ≤ j) là đứt.


    ================

    sonld1984


    Chuyên viên
    Chuyên viên
    LeVanDat đã viết:Cách giải quyết bài toán của đ/c Hồng là triệt để, nhưng tôi nghĩ rằng trong khi thi có thể mình không thể nhớ hết các cách giải để tối ưu. Tôi nghĩ rằng cách giải sau đây có thể chấp nhận được và ăn điểm, các đ/c cho ý kiến:

    Procedure SapXep(X: dãy số, n: integer)
    1. Khai báo các mảng A, B, C có n phần tử;
    m := 1; n := 1; q := 1;
    2. FOR i := 1 TO n DO
    CASE X(i).k OF
    1 : A(m) = X(i); m++;
    2 : B(n) = X(i); n++;
    3 : C(q) = X(i); q++;
    3. m --; n --; q--;
    4. FOR i := 1 TO n DO
    If i <= m then X(i) := A(i);
    If ( i > m ) and (i <= m + n) then X(i) := B(i - m);
    If i > m + n then X(i) : = C(i - m - n);
    5. Output X;

    Thuật toán này có độ phức tạp O(n). Nhưng chúng ta sử dụng tốn bộ nhớ một tí. Thực ra với thời đại máy tính hiện nay, việc sử dụng bộ nhớ không là vấn đề gì, miễn là chương trình của ta chạy luột là được. Tôi nghĩ rằng phương án này chấp nhận được và ăn điểm.

    Đồng chí Đạt có cách giải khá đơn giản, dễ hiểu, hay, tuy nhiên đồng chí chú ý cách khai báo biến toàn cục với biến
    cục bộ. Tôi thấy đồng chí có hai biến n trùng nhau đấy


    ================

    mrP


    Thành viên cao cấp
    Thành viên cao cấp
    keke, cái này mình cũng chỉ theo sách, mình cũng không lập trình nên không biết có lỗi hay không. Ngay cả sách Đỗ Xuân Lôi, trang 217 viết về thủ tục này cũng không thấy thêm điều kiện i ≤ j. Nếu mà xảy trường hợp lỗi như đ/c Son đã nói thì mình sẽ rút kinh nghiệm và lưu ý cho trường hợp này.
    @Son: Nếu cái của mình đứt, sẽ nối lại. :)

    He he! Đấy là em thấy thế thôi, còn đi thi người ta chắc không chặt chẽ lắm đâu.
    Nhưng em nghĩ cẩn thận vẫn tốt hơn


    ================
    [You must be registered and logged in to see this image.]

    Sponsored content


    Xem chủ đề cũ hơn Xem chủ đề mới hơn Về Đầu Trang  Thông điệp [Trang 1 trong tổng số 1 trang]

    Permissions in this forum:
    Bạn không có quyền trả lời bài viết

     

    Ghi rõ nguồn khi copy các bài viết từ Website này.
    Bản quyền thuộc Khoa học Máy tính. Số lượt truy cập tính đến hiện tại:Website counter
    Modified skin by Nguyễn Anh Cường. Developed by Members of http://khmt.123.st

    Free forum | © PunBB | Free forum support | Liên hệ | Report an abuse | Create a blog