Nội dung bài viết

    Xem thêm

    Bài toán Xếp hậu mở rộng. Trên bản cờ vua kích thước n x n có một ô (u, v) bị cấm

    Trả lời Vận dụng trang 67 Chuyên đề Tin học 11 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 Tin học 11.

    1 362 18/07/2023
    Trang trước
    Chia sẻ
    Trang sau  

    Giải Chuyên đề Tin học 11 Cánh diều Bài 5: Thực hành kĩ thuật quay lui giải bài toán xếp hậu

    Vận dụng trang 67 Chuyên đề Tin học 11: Bài toán Xếp hậu mở rộng.

    Trên bản cờ vua kích thước n x n có một ô (u, v) bị cấm, cần đặt n quân hậu lên bàn cờ sao cho không có hai quân nào tấn công nhau và không có quân nào đặt vào ô (u, v) bị cấm.

    Lời giải:

    Ký hiệu quân hậu đứng ở ô nằm trên hàng thứ i của lời giải là Q[i, j]. Các chỉ số dòng cột đánh từ trên xuống dưới, trái sang phải theo cách đánh số trong ma trận. Trong một ma trân vuông:

    Các phần tử nằm trên cùng hàng có chỉ số hàng bằng nhau;

    Các phần tử nằm trên cùng cột có chỉ số cột bằng nhau;

    Các phần tử nằm trên cùng một đường chéo song song với đường chéo chính có hiệu chỉ số hàng với chỉ số cột bằng nhau;

    Các phần tử nằm trên cùng một đường chéo song song với đường chéo phụ có tổng chỉ số hàng với chỉ số cột bằng nhau;

    Vì thế ta gọi các đường chéo song song với đường chéo chính là đường chéo trừ (hay hiệu), các đường chéo song song với đường chéo phụ là đường chéo cộng (hay tổng).

    Do đó, mỗi lời giải có thể được biểu diễn bởi dãy Q[1,i1],Q[2,i2],...,Q[n, in],thỏa mãn các điều kiện:

    Các chỉ số cột i1, i2,..., in đôi một khác nhau, hay chúng lập thành một hoán vị của các số 1, 2,.., n.

    Tổng chỉ số dòng và cột của các quân hậu 1+i1, 2+i2,..., n+in đôi một khác nhau;

    Hiệu chỉ số dòng và cột của các quân hậu 1-i1, 2-i2,...,n-in đôi một khác nhau.

    Xem thêm giải bài tập Chuyên đề Tin học 11 Cánh diều hay, chi tiết khác:

    Hoạt động 1 trang 66 Chuyên đề Tin học 11: Với n = 4 có hai cách đặt 4 quân hậu thoả mãn, em hãy chỉ ra hai dãy số biểu diễn

    Hoạt động 2 trang 66 Chuyên đề Tin học 11: Em hãy đưa ra điều kiện để kiểm tra hai quân hậu đặt ở hai ô (u1,v1) và (u2,v2) tấn công nhau.

    Hoạt động 3 trang 67 Chuyên đề Tin học 11: Tìm hiểu chương trình giải quyết bài toán xếp hậu bằng kĩ thuật quay lui trong Hình 4

    Vận dụng trang 67 Chuyên đề Tin học 11: Bài toán Xếp hậu mở rộng.

    Xem thêm giải bài tập Chuyên đề Tin học 11 Cánh diều hay, chi tiết khác:

    Bài 1: Kĩ thuật duyệt

    Bài 2: Kĩ thuật quay lui

    Bài 3: Thực hành kĩ thuật quay lui

    Bài 4: Thực hành tổng hợp kĩ thuật duyệt

    Bài 6: Dự án: Xây dựng chương trình sử dụng kĩ thuật duyệt

    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 362 18/07/2023
    Trang trước
    Chia sẻ
    Trang sau  

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