Giải chuyên đề Tin 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 có đáp án
38 người thi tuần này 4.6 452 lượt thi 4 câu hỏi
Bạn cần đăng ký gói VIP ( giá chỉ từ 250K ) để làm bài, xem đáp án và lời giải chi tiết không giới hạn.
🔥 Học sinh cũng đã học
Bộ 3 đề thi cuối kì 2 Tin học 11 Kết nối tri thức có đáp án - Đề 3
Bộ 3 đề thi cuối kì 2 Tin học 11 Kết nối tri thức có đáp án - Đề 2
Bộ 3 đề thi cuối kì 2 Tin học 11 Kết nối tri thức có đáp án - Đề 1
Đề thi giữa kì 2 Tin học 11 Kết nối tri thức có đáp án - Đề 3
Đề thi giữa kì 2 Tin học 11 Kết nối tri thức có đáp án - Đề 2
Đề thi giữa kì 2 Tin học 11 Kết nối tri thức có đáp án - Đề 1
Bộ 4 đề thi giữa kì 1 Tin học 11 Cánh diều có đáp án - Đề 4
Bộ 4 đề thi giữa kì 1 Tin học 11 Cánh diều có đáp án - Đề 3
Danh sách câu hỏi:
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
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 1 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+x1 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
Lời giải
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.
Nhắn tin Zalo
Hỏi bài tập