Nội dung bài viết

    Xem thêm

    Chuyên đề Tin học 11 Bài 14 (Kết nối tri thức): Thực hành kĩ thuật duyệt quay lui

    Với giải bài tập Chuyên đề Tin học 11 Bài 14: Thực hành kĩ thuật duyệt quay lui 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 14.

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

    Giải Chuyên đề Tin học 11 Bài 14: Thực hành kĩ thuật duyệt quay lui

    Khởi động trang 61 Chuyên đề Tin học 11: Theo em kĩ thuật duyệt quay lui thường được áp dụng cho những loại bài toán nào? Em có thể nêu ra một vài ví dụ không?

    Lời giải:

    Kỹ thuật duyệt quay lui thường được áp dụng cho các bài toán tìm kiếm toàn bộ các cấu hình khả thi, những bài toán có tính khả thi cao nhưng lại khó tìm cách giải chính xác.

    Ví dụ về các bài toán thường được giải bằng kỹ thuật duyệt quay lui bao gồm:

    - Tìm kiếm đường đi trong đồ thị

    - Liệt kê tất cả các tập con của một tập hợp

    - Tìm đường đi mê cung

    - Tìm kiếm các giải pháp tối ưu trong các bài toán tối ưu hóa rời rạc

    - Giải bài toán Sudoku

    - Giải các bài toán liên quan đến xếp hậu

    Luyện tập

    Luyện tập 1 trang 62 Chuyên đề Tin học 11: Sửa lại chương trình trong Nhiệm vụ 1 với yêu cầu thay đổi là cần in ra kết quả là các xâu kí tự chỉ bao gồm các kí tự “A”, “T”, “G”, “X”.

    Lời giải:

    Thay vì in từng phần tử của mảng A, chúng ta nối chúng lại để tạo thành một xâu kí tự bằng phương thức join().

    Sửa lại chương trình trong Nhiệm vụ 1 với yêu cầu thay đổi

    Kết quả thu được nếu n = 4:

    Sửa lại chương trình trong Nhiệm vụ 1 với yêu cầu thay đổi

    Luyện tập 2 trang 62 Chuyên đề Tin học 11: Trong Nhiệm vụ 2, động tác "quay lui" nằm ở đâu? Việc hoán vị được thực hiện như thế nào?

    Lời giải:

    Động tác quay lui nằm ở dòng 10, 11. Động tác "quay lui" thường được thực hiện khi một chuỗi ký tự hoặc một danh sách các phần tử đã được xây dựng để tạo thành câu, nhưng không phù hợp với yêu cầu hoặc điều kiện nào đó. Khi đó, chúng ta sẽ "quay lui" trở lại và thử các giá trị khác cho phần tử tiếp theo để xây dựng câu.

    Trong Nhiệm vụ 2, động tác quay lui nằm ở đâu? Việc hoán vị được thực hiện như thế nào?

    Việc hoán vị được thực hiện như sau: Việc hoán vị các phần tử được thực hiện bằng cách sử dụng một vòng lặp for để duyệt qua tất cả các phần tử trong tập hợp và đưa chúng vào vị trí kế tiếp của chuỗi hoặc danh sách đã được xây dựng. Sau đó, tiếp tục đệ quy để thêm phần tử tiếp theo cho chuỗi hoặc danh sách. Khi đã xây dựng được đầy đủ số phần tử cần thiết, chuỗi hoặc danh sách này được sử dụng để tạo thành một câu hoàn chỉnh. Khi không tìm được chuỗi hoặc danh sách phù hợp, chúng ta sẽ "quay lui" trở lại và thử các giá trị khác cho phần tử tiếp theo.

    Vận dụng

    Vận dụng 1 trang 62 Chuyên đề Tin học 11: Viết chương trình sử dụng kĩ thuật duyệt quay lui để kiểm tra xem một biểu thức có hợp lệ về sử dụng các dấu ngoặc đơn hay không.

    Lời giải:

    Để kiểm tra xem một biểu thức có hợp lệ về sử dụng các dấu ngoặc đơn hay không, chúng ta có thể sử dụng kĩ thuật duyệt quay lui để kiểm tra. Cụ thể, chúng ta sẽ duyệt qua từng ký tự trong biểu thức và sử dụng một stack (ngăn xếp) để lưu trữ các dấu ngoặc đơn.

    Viết chương trình sử dụng kĩ thuật duyệt quay lui để kiểm tra xem một biểu thức

    Vận dụng 2 trang 62 Chuyên đề Tin học 11: Viết chương trình in ra tất cả các hoán vị của tập hợp S = {1, 2, ..., n} với n được nhập từ bàn phím.

    Lời giải:

    Ý tưởng chính là ta sẽ chọn lần lượt các phần tử trong tập hợp S để tạo thành một hoán vị, và ta sẽ tiếp tục chọn các phần tử còn lại trong tập hợp cho đến khi hoàn thành hoán vị.

    Viết chương trình in ra tất cả các hoán vị của tập hợp S = {1, 2, ..., n}

    Vận dụng 3 trang 63 Chuyên đề Tin học 11: Cho các hệ sốHãy viết chương trình sinh tất cả các đa thức bậc k có thể thành lập từ các hệ sốHãy viết chương trình sinh tất cả các đa thức bậc k có thể thành lập từ các hệ số trên, mỗi hệ số sử dụng một lần. Một ví dụ của đa thức trên làHãy viết chương trình sinh tất cả các đa thức bậc k có thể thành lập từ các hệ số

    Lời giải:

    Để giải quyết bài toán này, ta có thể sử dụng kĩ thuật quay lui để sinh ra các đa thức bậc k. Mỗi lần sinh ra một đa thức, ta cập nhật lại danh sách các hệ số đã sử dụng bằng cách loại bỏ hệ số đang được sử dụng để không sử dụng lại trong các lần kế tiếp.

    Hãy viết chương trình sinh tất cả các đa thức bậc k có thể thành lập từ các hệ số

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

    Bài 15: Bài toán xếp hậu

    Bài 16: Thực hành thiết kế thuật toán theo kĩ thuậ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 294 20/08/2023
    Trang trước
    Chia sẻ
    Trang sau  

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