Đạ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

    Admin
    Quản trị viên
    Quản trị viên
    Bài toán:
    Khi đầu bài cho dãy X1, X2, ..., Xn yêu cầu sắp xếp các phần tử theo thứ tự.
    Nếu yêu cầu sắp xếp không tăng → phải hiểu là sau khi sắp xếp xong X'1 ≥ X'2 ≥ X'3 ≥... ≥ X'n
    Nếu yêu cầu sắp xếp không giảm → phải hiểu là sau khi sắp xếp
    xong X'1 ≤ X'2 ≤ X'3 ≤... ≥ X'n
    trong đó X'i là X mới.

    Giải quyết bài toán theo phương pháp sắp xếp theo phân đoạn.
    [You must be registered and logged in to see this link.]
    * Phân tích:
    - Chọn một khoá ngẫu nhiên làm chốt. Mọi phần tử nhỏ hơn giá trị của chốt được xếp vào vị trí trước chốt, mọi phần tử lớn hơn chốt được xếp vào sau chốt.
    - So sánh các phần tử trong dãy với chốt, đổi vị trí cho nhau nếu lớn hơn chốt mà nằm trước chốt và nhỏ hơn chốt mà nằm sau chốt.
    - Khi việc đổi chỗ thực hiện xong thì dãy khoá phân làm 2 đoạn.
    + Một đoạn gồm các khoá nhỏ hơn chốt.
    + Một đoạn gồm các khoá lớn hơn chốt
    +Khoá chốt ở giữa 2 đoạn cũng là vị trí thực của nó.
    - Quá trình lặp lại với 2 đoạn nhỏ, đén khi gặp 1 đoạn chỉ gồm 2 phần tử.

    * Ví dụ:

    * Giải thuật sắp xếp:
    Proc Quick_sort (l, k: chỉ số trên dưới)
    1. temp ; Xk; i = l; j = k;
    2. while i <= j do
                                  a. while (i ≤ j) & Xi ≤ temp do i ++
                                  b. while (i ≤ j) & Xj ≥ temp do j--
                                  c. if i < j then Đổi chỗ (Xi, Xj)
    3. Đổi chỗ (Xk, Xj)
    4. Quick_sort (l, j - 1);
    Quick_sort ( j+1, k)
    End

    Ở đây phần 4 gọi đệ quy 2 lần khác nhau. Cần học và nắm rõ thuật sắp xếp này.

    https://khmt.123.st

    2[Hướng dẫn]Thuật toán sắp xếp phân đoạn Empty [Thắc mắc] Wed Jun 01, 2011 11:30 am

    Tuan Diep

    Tuan Diep
    Thành viên bắt đầu chia sẻ
    Thành viên bắt đầu chia sẻ
    không có đk If như của thầy thì trường hợp 1 pt k=L thì đệ quy thế nào? `)

    Admin

    Admin
    Quản trị viên
    Quản trị viên

    https://khmt.123.st

    Admin

    Admin
    Quản trị viên
    Quản trị viên
    Bản quyền mô phỏng của Khoa học Máy tính
    Computer Science
    Faculty of Information Technology - Hanoi National University of Education

    Nếu bạn không thấy mô phỏng hiện ra, nghĩa là máy bạn chưa cài java. Bạn
    phải thực hiện cài java vào máy bằng cách nhấn vào đường link sau:
    [You must be registered and logged in to see this link.]
    Sau đó cứ việc nháy OK để java cài vào máy.

    Tất cả các trang mô phỏng cơ sở, sẽ được viết theo dạng java cho nó nhẹ, nên bạn hãy cài java để xem nhé!

    Hiện tại tôi có thể hướng dẫn các bạn mô phỏng bằng Flash nhưng không có
    thời gian nhiều. Chắc là nếu thi đỗ được, chúng ta sẽ làm lại toàn bộ
    mô phỏng dạng này bằng flash cho đẹp.

    Đường link tham khảo các bài viết bằng sử dụng Flash căn bản (nếu không
    hiện tiếng Việt, xin chọn từ thựcđơn View, codepage ISO8859-1 (cái này
    tôi viết lâu rồi, từ hồi chưa chuẩn hoá unicode):
    [You must be registered and logged in to see this link.]

    Nháy tham khảo: [You must be registered and logged in to see this link.]
    Giáo trình sử dụng: [You must be registered and logged in to see this link.]

    https://khmt.123.st

    hoagiapk

    hoagiapk
    Thành viên ít chịu khó
    Thành viên ít chịu khó
    Chào Anh!
    Anh có thể giải thích khi ta chọn phần tử chốt giữa a[r], a[l] và a[(l+r)/2] thì có gì khác nhau, tốt xấu như thế nào, trường hợp nào thì nên chọn vị trí chốt nào tương ứng ? cám ơn Anh!

    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 https://khmt.123.st

    Free forum | ©phpBB | Free forum support | Báo cáo lạm dụng | Thảo luận mới nhất