Nội dung bài viết

    Xem thêm

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

    Với giải bài tập Chuyên đề Tin học 11 Bài 16: Thực hành thiết kế thuật toán theo kĩ thuậ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 16.

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

    Giải Chuyên đề Tin học 11 Bài 16: Thực hành thiết kế thuật toán theo kĩ thuật quay lui

    Khởi động trang 68 Chuyên đề Tin học 11: Chắc em đã nghe nói nhiều bài toán tìm đường đi trong mê cung. Nếu áp dụng kĩ thuật duyệt quay lui cho bài toán này thì làm thế nào để tìm ra các bước đi tiếp theo từ một vị trí?

    Lời giải:

    Để tìm ra các bước đi tiếp theo từ một vị trí trong mê cung khi áp dụng kĩ thuật duyệt quay lui, chúng ta cần kiểm tra các ô xung quanh ô hiện tại xem có thể đi được không. Nếu ô đó chưa được đi qua và là ô đích hoặc có thể đi đến ô đích từ ô đó thì chúng ta chọn ô đó làm ô tiếp theo và tiếp tục tìm đường đi từ ô đó. Nếu không có ô nào thỏa mãn điều kiện trên, chúng ta quay lại ô trước đó và tiếp tục kiểm tra các ô xung quanh ô đó. Quá trình này được lặp lại cho đến khi tìm được đường đi hoặc đã duyệt qua tất cả các ô mà không tìm được đường đi.

    Luyện tập

    Luyện tập 1 trang 70 Chuyên đề Tin học 11: Nếu sửa yêu cầu đề bài đặt vị trí xuất phát tại ô giữa của mê cung (ví dụ vị trí m//2. n//2), vị trí thoát của mê cung là ô trái trên hoặc phải dưới của mê cung thì cần sửa chương trình như thế nào?

    Lời giải:

    Để điểm bắt đầu tại m//2 và n//2, em chỉ cần thay đổi giá trị của biến x và y khi gọi hàm solveMaze. Thay vì truyền 0, 0 vào hàm solveMaze, em có thể truyền m//2, n//2:

    Nếu sửa yêu cầu đề bài đặt vị trí xuất phát tại ô giữa của mê cung (ví dụ vị trí m//2. n//2)

    Luyện tập 2 trang 70 Chuyên đề Tin học 11: Trên dữ liệu đầu ra của bài toán chưa thể hiện thông tin của các ô là tường. Hãy sửa lại chương trình để trên dữ liệu đầu ra các ô là tường sẽ được đánh dấu bằng "x".

    Lời giải:

    - Em cần sửa hàm writemaze in dữ liệu đầu ra và hàm soveMaze đặt giá trị tại các ô là 2 nếu ở đó là đường đi

    - Hai hàm cần sửa như sau:

    Trên dữ liệu đầu ra của bài toán chưa thể hiện thông tin của các ô là tường

    Trên dữ liệu đầu ra của bài toán chưa thể hiện thông tin của các ô là tường

    Vận dụng

    Vận dụng 1 trang 70 Chuyên đề Tin học 11: Cải tiến nhiệm vụ thực hành để chương trình in ra màn hình tất cả các đường đi để thoát ra khỏi mê cung

    Lời giải:

    Để in ra tất cả các đường đi trong mê cung, bạn có thể sử dụng một hàm đệ quy để tìm và in ra tất cả các đường đi hợp lệ.

    Cải tiến nhiệm vụ thực hành để chương trình in ra màn hình tất cả các đường đi để thoát ra khỏi mê cung

    Cải tiến nhiệm vụ thực hành để chương trình in ra màn hình tất cả các đường đi để thoát ra khỏi mê cung

    Vận dụng 2 trang 70 Chuyên đề Tin học 11: Giải bài toán xếp Hậu tổng quát m hàng n cột trong đó m và n là các số tự nhiên bất kì (m≥n)

    Lời giải:

    Để giải bài toán này, có thể sử dụng thuật toán quay lui (backtracking) để tìm tất cả các cách xếp Hậu một cách hợp lệ trên bàn cờ.

    Em có thể tham khảo lời giải sau:

    Giải bài toán xếp Hậu tổng quát m hàng n cột trong đó m và n là các số tự nhiên bất kì (m≥n)

    Giải bài toán xếp Hậu tổng quát m hàng n cột trong đó m và n là các số tự nhiên bất kì (m≥n)

    Vận dụng 3 trang 70 Chuyên đề Tin học 11: Bài toán “Mã đi tuần” được phát biểu như sau: cho vị trí ban đầu của quân mã trên bàn cờ vua 8×8, hãy tìm một hành trình của quân mã sao cho nó đi hết các ô bàn cờ mà không đi qua bất kì ô nào hai lần. Hãy dùng chiến lược quay lui để tìm lời giải cho bài toán này

    Lời giải:

    - Bài toán yêu cầu tìm một hành trình của quân mã đi qua tất cả các ô trên bàn cờ mà không đi qua bất kỳ ô nào hai lần.

    - Ta sẽ thử tất cả các bước di chuyển hợp lệ của quân mã từ một ô đang xét và đi tiếp cho đến khi quân mã đã đi qua tất cả các ô trên bàn cờ.

    Tham khảo bài làm sau:

     

    Bài toán Mã đi tuần được phát biểu như sau cho vị trí ban đầu của quân mã

    Bài toán Mã đi tuần được phát biểu như sau cho vị trí ban đầu của quân mã

    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 14: Thực hành kĩ thuật duyệt quay lui

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

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

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