Nội dung bài viết

    Xem thêm

    Sách bài tập Tin học 11 Bài 9 (Cánh diều): Lập trình sắp xếp nhanh

    Với giải sách bài tập Tin học 11 Bài 9: Lập trình sắp xếp nhanh sách Cánh diều hay nhất, chi tiết sẽ giúp học sinh dễ dàng làm bài tập trong SBT Tin học 11 Bài 9.

    1 311 18/10/2023
    Trang trước
    Chia sẻ
    Trang sau  

    Giải SBT Tin học 11 Bài 9: Lập trình sắp xếp nhanh

    Câu Fcs37 trang 61 SBT Tin học 11: Hãy xác định độ phức tạp của thuật toán Quick Sort trong trường hợp xấu nhất.

    Lời giải:

    Độ phức tạp của thuật toán Quick Sort trong trường hợp xấu nhất: O(n2).

    Câu Fcs38 trang 61 SBT Tin học 11: Mã lệnh Python sau đây thể hiện hàm sắp xếp nhanh sử dụng phân đoạn Lomuto, được trích dẫn từ Hình 3 trong sách giáo khoa Tin học 11 – Khoa học máy tính.

    def quickSort(a, lo, hi):

    if lo < hi:

    p = phandoan Lomuto (a, lo, hi) quickSort (a, lo, p 1) quickSort(a, p+1, hi)

    Có thể thấy rằng trong phần cài đặt của hàm quickSort, ta lại gọi chính nó hai lần. Kĩ thuật này được gọi là đệ quy. Em hãy giải thích tại sao hàm quickSort không chạy vô hạn với một bộ tham số hợp lệ, dù nó sẽ liên tục gọi lại chính nó.

    Lời giải:

    Em tránh được việc đệ quy vô hạn vì phần cài đặt luôn đảm bảo điều kiện dừng là lo 2 hi. Điều kiện này chắc chắn sẽ xảy ra vì kích thước của đoạn [lo, hi] sẽ luôn bị thu hẹp qua từng lớp phân đoạn.

    Câu Fcs39 trang 61 SBT Tin học 11: Sửa lại cách cài đặt thuật toán Quick Sort để sắp xếp một danh sách tuple (ưu tiên khoá bên trái trước, nếu khoá bên trái bằng nhau thì so sánh khoá bên phải).

    Lời giải:

    Giả sử em cần sắp thứ tự một danh sách a. Thay vì trực tiếp so sánh bằng toán tử qua biểu thức (a[j] < pivot), em có thể định nghĩa hàm less_than_or_equal(a, b) trả về một giá trị boolean thể hiện tiêu chuẩn so sánh mà em muốn áp dụng với tuple a và tuple b, rồi thay thế điều kiện ở hàm phân đoạn if a[j] <= pivot thành if less_than_or_equal(a[j], pivot).

    Một cách cài đặt hàm so sánh:

    Sửa lại cách cài đặt thuật toán Quick Sort để sắp xếp một danh sách tuple

    Câu Fcs40 trang 61 SBT Tin học 11: Một công ty có n nhân viên. Đã tới cuối tháng, người chủ nhận thấy tháng này có khá nhiều nhân viên vắng làm. Ông đã kiểm tra danh sách chấm công và biết được số ngày mỗi nhân viên đã đi làm trong tháng. Sau đó là danh sách xin nghỉ phép gồm m dòng.

    Hãy lập trình để xác định xem có bao nhiêu nhân viên vắng không phép và liệt kê ra các nhân viên đó theo thứ tự số buổi vắng không phép giảm dần.

    Dữ liệu: Nhập từ thiết bị vào chuẩn:

    • Dòng đầu tiên chứa hai số nguyên dương n, m.

    • Dòng thứ hai chứa n số nguyên b[i] là số ngày đi làm của nhân viên có số hiệu là i (các nhân viên được đánh số 1, 2, 3,..., ).

    m dòng cuối cùng, mỗi dòng chứa thông tin dưới dạng “a d” tức là người a xin nghỉ phép vào ngày d (1 <aŚn, 1<d<30) (giả sử tháng đang hỏi có 30 ngày). Dữ liệu vào đảm bảo trong cùng một ngày, mỗi nhân viên chỉ xin phép tối đa một lần.

    Kết quả: Hiển thị ở thiết bị ra chuẩn:

    • Dòng đầu chứa số lượng nhân viên đã vắng không phép.

    • Dòng thứ hai chứa các chỉ số của các nhân viên vắng (được sắp xếp theo số lượng buổi vắng không phép giảm dần).

    Một công ty có n nhân viên Đã tới cuối tháng người chủ nhận thấy tháng này

    Lời giải:

    - Trước tiên, cần phải tính số ngày nghỉ không phép, rồi sau đó ta thực hiện sắp xếp sau.

    Số ngày nghỉ chính là 30 trừ cho số ngày đi làm. Sau đó với mỗi lần xin phép, em trừ đi, như vậy sẽ có được số ngày vắng không phép.

    - Vì cần in ra số hiệu của các nhân viên nên em sắp xếp trên chỉ số thứ tự, thay vì sắp xếp trên giá trị.

    Một công ty có n nhân viên Đã tới cuối tháng người chủ nhận thấy tháng này

    Xem thêm các lời giải sách bài tập Tin học lớp 11 Cánh diều hay, chi tiết khác:

    Bài 10, 11, 12, 13, 14: Thiết kế chương trình từ trên xuống và phương pháp mô đun hoá. Thực hành thiết kế và lập trình theo mô đun. Thực hành về thư viện các hàm tự định nghĩa

    Bài 15: Cấu trúc dữ liệu danh sách liên kết và ứng dụng

    Bài 1: Một số thao tác chỉnh sửa ảnh và hỗ trợ chỉnh sửa ảnh trong phần mềm GIMP

    Bài 2: Tẩy xoá ảnh trong GIMP

    Bài 3: Tạo ảnh động trong GIMP

    Tham khảo các loạt bài Tin học 11 khác:

    Bài viết cùng lớp mới nhất

    Xem thêm
    1 311 18/10/2023
    Trang trước
    Chia sẻ
    Trang sau  

    Xem thêm các chương trình khác: