Nội dung bài viết

    Xem thêm

    Chuyên đề Tin học 11 Bài 10 (Kết nối tri thức): Thực hành giải toán bằng kĩ thuật chia để trị

    Với giải bài tập Chuyên đề Tin học 11 Bài 10: Thực hành giải toán bằng kĩ thuật chia để trị sách Kết nối tri thức hay nhất, chi tiết giúp học sinh dễ dàng làm bài tập Chuyên đề học tập Tin học 11 Bài 10.

    1 338 20/08/2023
    Trang trước
    Chia sẻ
    Trang sau  

    Giải Chuyên đề Tin học 11 Bài 10: Thực hành giải toán bằng kĩ thuật chia để trị

    Khởi động trang 45 Chuyên đề Tin học 11: Khi làm việc với các danh sách mảng, nhiều trường hợp đòi hỏi cần kiểm tra các danh sách mảng đã được sắp thứ tự để áp dụng thuật toán phù hợp. Cho một dãy số, theo em làm thế nào để xác định dãy số đã được sắp xếp theo thứ tự tăng dần hoặc giảm dần?

    Lời giải:

    Để xác định dãy số đã được sắp xếp theo thứ tự tăng dần hoặc giảm dần, ta có thể sử dụng thuật toán kiểm tra sự sắp xếp. Các bước thực hiện như sau:

    1. Duyệt qua từng phần tử của dãy số, bắt đầu từ phần tử thứ 2.

    2. Kiểm tra xem phần tử hiện tại có lớn hơn (nếu kiểm tra tăng dần) hoặc nhỏ hơn (nếu kiểm tra giảm dần) phần tử trước đó không.

    3. Nếu có ít nhất một phần tử không đúng thứ tự, tức là dãy số không được sắp xếp theo thứ tự tăng dần (giảm dần).

    4. Nếu tất cả các phần tử đều đúng thứ tự, dãy số đã được sắp xếp theo thứ tự tăng dần (giảm dần).

    Luyện tập

    Luyện tập trang 47 Chuyên đề Tin học 11: Nâng cấp chương trình của nhiệm vụ 1 với yêu cầu bổ sung: Cần đưa ra kết quả là số lượng các cặp nghịch đảo và toàn bộ dãy các cặp chỉ số nghịch đảo đã tìm thấy. Ví dụ với A = [4, 5, 2, 10, 4] thì chương trình sẽ đưa ra giá trị 4 và dãy [(4, 2), (5, 2), (5, 4), (1, 4)]

    Lời giải:

    Để giải quyết bài toán đếm số cặp nghịch đảo của dãy số, ta có thể sử dụng một thuật toán đơn giản như sau:

    - Duyệt qua từng phần tử của dãy và đối chiếu với các phần tử sau nó để tìm các cặp nghịch đảo.

    - Nếu phần tử tại vị trí i lớn hơn phần tử tại vị trí j, ta tăng biến đếm số cặp nghịch đảo lên 1 và lưu cặp chỉ số (i, j) vào danh sách các cặp nghịch đảo.

    - Trả về giá trị biến đếm số cặp nghịch đảo và danh sách các cặp chỉ số nghịch đảo.

    Nâng cấp chương trình của nhiệm vụ 1 với yêu cầu bổ sun

    - Kết quả như sau:

    Nâng cấp chương trình của nhiệm vụ 1 với yêu cầu bổ sun

    Vận dụng

    Vận dụng 1 trang 47 Chuyên đề Tin học 11: Cho dãy số A, cần tìm phần tử mốt (mode) của A. Phần tử mốt là phần tử có số lần xuất hiện nhiều nhất trong A. Nếu tồn tại nhiều thì chỉ yêu cầu tìm ra một phần tử mốt. Yêu cầu sử dụng kĩ thuật chia để trị.

    Lời giải:

    Để tìm phần tử xuất hiện nhiều lần nhất trong dãy, ta có thể sử dụng phương pháp chia để trị (divide and conquer) bằng cách chia dãy thành hai phần và tìm phần tử xuất hiện nhiều lần nhất trong mỗi phần, sau đó so sánh và lấy phần tử xuất hiện nhiều lần nhất trong cả hai phần.

    Cho dãy số A, cần tìm phần tử mốt (mode) của A

    Ví dụ:

    Cho dãy số A, cần tìm phần tử mốt (mode) của A

    Kết quả: “Phần tử xuất hiện nhiều nhất là 5, số lần xuất hiện là 3”

    Vận dụng 2 trang 47 Chuyên đề Tin học 11: Cho một dãy số bất kì A[0], A[1]..., A[n – 1]. Một tổng con được định nghĩa là tổng của một dãy con liên tục dạng . Bài toán yêu cầu tìm và chỉ ra một tổng con và dãy con tương ứng có giá trị lớn nhất. Yêu cầu sử dụng kĩ thuật chia để trị.

    Lời giải:

    Em có thể áp dụng kỹ thuật chia để trị như sau:

    1. Chia dãy số ban đầu thành hai dãy con bằng cách chia nó ở giữa.

    2. Giải quyết hai dãy con bằng cách đệ quy áp dụng cùng thuật toán.

    3. Tìm tổng con lớn nhất chứa phần tử ở giữa của dãy số ban đầu. Ta thực hiện điều này bằng cách tính tổng của phần tử đó cùng các phần tử liền trước và liền sau nó, rồi lưu lại tổng lớn nhất tìm được.

    4. Tìm tổng con lớn nhất nằm hoàn toàn trong một trong hai dãy con đã giải quyết ở bước 5. Ta thực hiện điều này bằng cách đệ quy áp dụng lại thuật toán trên hai dãy con đó.

    6. Tìm tổng con lớn nhất giữa phần tử ở giữa dãy con trái và phần tử ở giữa dãy con phải. Ta thực hiện điều này bằng cách tính tổng của phần tử giữa dãy con trái và phần tử giữa dãy con phải, rồi lưu lại tổng lớn nhất tìm được.

    Cho một dãy số bất kì A[0], A[1]..., A[n – 1]

    Ví dụ:

    Cho một dãy số bất kì A[0], A[1]..., A[n – 1]

    Kết quả như sau:

    Cho một dãy số bất kì A[0], A[1]..., A[n – 1]

    Xem thêm các bài giải Chuyên đề Tin học 11 sách Kết nối tri thức hay, chi tiết khác:

    Bài 8: Thực hành thiết thuật toán tìm kiếm theo kĩ thuật chia để trị

    Bài 9: Sắp xếp trộn

    Bài 11: Bài toán tìm kiếm theo kĩ thuật duyệt

    Bài 12: Thực hành kĩ thuật duyệt cho bài toán tìm kiếm

    Bài 13: Kĩ thuật duyệt quay lui

    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 338 20/08/2023
    Trang trước
    Chia sẻ
    Trang sau  

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