Giáo án điện tử chuyên đề Khoa học máy tính 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

CHÀO MỪNG CÁC EM ĐẾN VỚI

TIẾT HỌC NGÀY HÔM NAY!

KHỞI ĐỘNG

“Cần đặt n quân hậu lên bàn cờ vua kích thước n×n, sao cho không có hai quân hậu nào tấn công nhau (tức là không có hai quân nào cùng hàng, cùng cột hoặc cùng đường chéo).”

Em hãy thiết lập chương trình giải bài toán trên?

BÀI 5.

THỰC HÀNH KĨ THUẬT QUAY LUI

GIẢI BÀI TOÁN XẾP HẬU

NHIỆM VỤ 1

Bước 1: Thiết kế thuật toán theo kĩ thuật quay lui

Hình 3. Khả năng tấn công của quân hậu

Ví dụ:

Với n=8 thì X=(0,4,7,5,2,6,1,3).

Hoạt động 1

Với n = 4 có hai cách đặt 4 quân hậu thỏa 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ì?

Hai dãy (1, 3, 0, 2); (2, 0, 3, 1) biểu diễn cách đặt 4 quân hậu. Đây là hai hoán vị của 0, 1, 2, 3.

Hoạt động 2

Bước 2: Xây dựng chương trình giải bài toán

Hình 4. Chương trình giải bài toán xếp hậu

Hoạt động 3

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, giải thích ý nghĩa các hàm check, printSolution, permutation và chạy thử nghiệm với n = 4, 5, 8 và 10.

LUYỆN TẬP

Câu 1: Bài toán “Xếp hậu” sử dụng kĩ thuật gì?

A. Kĩ thuật quay lui.

B. Kĩ thuật đệ quy.

C. Kĩ thuật chia để trị.

D. Không có đáp án đúng.

A. Kĩ thuật quay lui.

Câu 2: Điều kiện của bài toán “Xếp hậu” là gì?

Câu 3: Chạy chương trình bài toán Xếp hậu với dự liệu đầu vào n=3. Kết quả của bài toán là:

A. 4.

B.3

C. 2.

D. 1.

D. 1.

Câu 4: Trong chương trình sau, các lệnh này dùng để làm gì?

A. Tính tổng số cách xếp quân.

B.Viết số cách xếp quân hậu.

C. Kiểm tra vị trí của quân hậu.

D. Liệt kê vị trí xếp quân hậu.

C. Kiểm tra vị trí của quân hậu.

Câu 5: Trong chương trình sau, câu lệnh này dùng để làm gì?

A. Tính tổng số cách xếp quân.

B.Viết số cách xếp quân hậu.

C. Kiểm tra vị trí của quân hậu.

D. Liệt kê vị trí xếp quân hậu.

D. Liệt kê vị trí xếp quân hậu.

VẬN DỤNG

--------------- Còn tiếp ---------------