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

1900.edu.vn giới thiệu giải Chuyên đề học tập Tin học 11 Bài 5: Thực hành kĩ thuật quay lui giải bài toán xếp hậu sách Cánh diều hay, ngắn gọn giúp học sinh xem và so sánh lời giải từ đó biết cách làm Chuyên đề học tập Tin học 11. Mời các bạn đón xem:

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

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 lời giải của hai cách đó theo dãy x, hai dãy đó có đặc điểm gì?

Lời giải:

Quân hậu đặt ở ô (i,j) sẽ tấn công các quân hậu đặt ở ô cùng hàng, cùng cột hoặc cùng đường chéo. Cụ thể, quân hậu đặt ở ô (i,j) sẽ tấn công các quân hậu đặt ở:

- Các ô cùng hàng là các ô (i,j'), với 0 ≤ j’ ≤ n-1.

- Các ô cùng cột là các ô (i',j'), với 0 ≤ i' ≤ n-1.

- Các ô cùng đường chéo từ trên bên trái hướng xuống dưới sang bên phải.

- Các ô cùng đường chéo từ dưới bên trái hướng lên bên phải trên.

Hoạt động 2 trang 66 Chuyên đề Tin học 11Em 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.

Lời giải:

Dãy X = (x0,x1,...,xn-1) là 1 hoán vị của dãy (0,1,...,n-1) biểu diễn một cách đặt thỏa mãn nếu với mọi i khác j thì 2 điều kiện sau thỏa mãn: i-xi khác j -xj và i+xi khác j+xj.

Với cách mô tả lời giải bài toán bằng 1 dãy X = (x0,x1,...,xn-1) là hoán vị của dãy (0,1,...n-1), trong đó xi là chỉ số cột của quấn hậu trên hàng thứ i (0 ≤ i ≤ n-1), ta có thể giải quyết bài toán bằng cách sử dụng kĩ thuật quay lui để liệt kê tất cả các hoán vị của dãy (0,1,...,n-1). Với mỗi hoán vị đó, tiến hành kiểm tra để chọn nghiệm.

Hoạt động 3 trang 67 Chuyên đề Tin học 11Tì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, giải thích ý nghĩa các hàm checkprintSolutionpermutation và chạy thử nghiệm với n = 4, 5, 8 và 10.

Lời giải:

Nhập chương trình sau và đọc kết quả xuất ra màn hình.

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 11Bà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 lời giải bài tập Chuyên đề học tập Tin học lớp 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

 

Câu hỏi liên quan

Quân hậu đặt ở ô (i,j) sẽ tấn công các quân hậu đặt ở ô cùng hàng, cùng cột hoặc cùng đường chéo. Cụ thể, quân hậu đặt ở ô (i,j) sẽ tấn công các quân hậu đặt ở: - Các ô cùng hàng là các ô (i,j'), với 0 ≤ j’ ≤ n-1. - Các ô cùng cột là các ô (i',j'), với 0 ≤ i' ≤ n-1. - Các ô cùng đường chéo từ trên bên trái hướng xuống dưới sang bên phải. - Các ô cùng đường chéo từ dưới bên trái hướng lên bên phải trên.
Xem thêm
Dãy X = (x0,x1,...,xn-1) là 1 hoán vị của dãy (0,1,...,n-1) biểu diễn một cách đặt thỏa mãn nếu với mọi i khác j thì 2 điều kiện sau thỏa mãn: i-xi khác j -xj và i+xi khác j+xj. Với cách mô tả lời giải bài toán bằng 1 dãy X = (x0,x1,...,xn-1) là hoán vị của dãy (0,1,...n-1), trong đó xi là chỉ số cột của quấn hậu trên hàng thứ i (0 ≤ i ≤ n-1), ta có thể giải quyết bài toán bằng cách sử dụng kĩ thuật quay lui để liệt kê tất cả các hoán vị của dãy (0,1,...,n-1). Với mỗi hoán vị đó, tiến hành kiểm tra để chọn nghiệm.
Xem thêm
Xem tất cả hỏi đáp với chuyên mục: Thực hành kĩ thuật quay lui giải bài toán xếp hậu
Bình luận (0)

Đăng nhập để có thể bình luận

Chưa có bình luận nào. Bạn hãy là người đầu tiên cho tôi biết ý kiến!