Chuyên đề Tin Học 11 KNTT Bài 13. Kĩ thuật duyệt quay lui có đáp án

367 lượt thi 15 câu hỏi

Đề số 1

Đề thi liên quan:

Chuyên đề Tin Học 11 KNTT Bài 1. Đệ quy và hàm đệ quy có đáp án

293 lượt thi

Chuyên đề Tin Học 11 KNTT Bài 2. Thiết kế thuật toán đệ quy có đáp án

285 lượt thi

Chuyên đề Tin Học 11 KNTT Bài 3. Thực hành giải toán theo kĩ thuật đệ quy có đáp án

271 lượt thi

Chuyên đề Tin Học 11 KNTT Bài 4. Tháp Hà Nội có đáp án

245 lượt thi

Chuyên đề Tin Học 11 KNTT Bài 5. Thực hành thiết kế thuật toán theo kĩ thuật đệ quy có đáp án

222 lượt thi

Chuyên đề Tin Học 11 KNTT Bài 6. Ý tưởng và kĩ thuật chia để trị có đáp án

273 lượt thi

Chuyên đề Tin Học 11 KNTT Bài 7. Thiết kế thuật toán theo kĩ thuật chia để trị có đáp án

234 lượt thi

Chuyên đề Tin Học 11 KNTT Bài 8. Thực hành thiết thuật toán tìm kiếm theo kĩ thuật chia để trị có đáp án

251 lượt thi

Chuyên đề Tin Học 11 KNTT Bài 9. Sắp xếp trộn có đáp án

222 lượt thi

Chuyên đề Tin Học 11 KNTT Bài 10. Thực hành giải toán bằng kĩ thuật chia để trí có đáp án

220 lượt thi

Danh sách câu hỏi:

Câu 1:

Chúng ta đã biết từ bài học trước, thiết lập các thuật toán duyệt sẽ phụ thuộc hoàn toàn vào mô hình và cấu trúc của miền dữ liệu cần tìm kiếm. Từ lâu các nhà khoa học đã nhìn thấy rất nhiều bài toán khó không tìm được cách duyệt hữu hiệu, điển hình nhất là bài toán tìm đường đi trong mê cung.

Bài toán tìm đường đi trong mê cung lần đầu tiên được đưa ra trong cuốn sách Récréations Mathématiques của tác giả Édouard Lucas năm 1882 tại Pháp. Cũng trong cuốn sách đó Lucas đã đưa ra phác thảo đầu tiên của một phương pháp giải bài toán tìm đường đi trong mê cung mà bây giờ chúng ta gọi là thuật toán duyệt quay lui, hay đơn giản là thuật toán quay lui (backtracking).

Trong trò chơi mê cung (xem hình) em cần tìm một đường đi xuất phát từ lối vào và ra khỏi mê cung tại lối ra. Em có đề xuất gì để giải bài toán này.

Câu 1:

Đọc, trao đổi và thảo luận về ý tưởng thuật toán quay lui của bài toán tìm đường đi trong mê cung.

Câu 2:

Khi đã thực hiện hết các bước lặp tại dòng 2 ở trên thì hàm có dừng không?

Câu 3:

Lệnh gọi hàm chính của chương trình trên là gì?

Câu 4:

Nếu yêu cầu bổ sung thêm 1 lệnh “Nếu thấy <lối ra> thì thông báo và dừng chương trình” thì lệnh này sẽ đặt ở đâu trong chương trình trên?

Câu 5:

Quan sát, thực hiện và thảo luận các bước thiết kế mô hình tổng quát của kĩ thuật duyệt quay lui.

Câu 6:

Trạng thái "quay lui" của thuật toán trên nằm ở đâu?

Câu 7:

Có cách nào đếm được tất cả các nghiệm từ thuật toán trên được không? Nếu có thì làm cách nào?

Câu 8:

Cùng thực hiện, trao đổi, thảo luận thiết kế chương trình sinh tất cả các dãy nhị phân độ dài n bằng kĩ thuật quay lui.

Câu 9:

Trong chương trình 1, động tác “quay lui” nằm ở đâu?

Câu 10:

Giải thích ý nghĩa của lệnh A.pop() tại dòng 8 của chương trình 2. Vì sao lệnh này không có trong chương trình 1?

Câu 11:

Sửa các chương trình trên bổ sung thêm chức năng: sau khi in ra tất cả các xâu nhị phân thi thông báo tổng số nghiệm.

Câu 12:

Viết chương trình sinh tất cả các xâu (hoặc dãy) bao gồm n kí tự dạng “R”, “G” và "B".

Câu 13:

Viết chương trình sinh tất cả các số hex (hệ đếm 16) có 3 chỉ số.

Câu 14:

Viết chương trình sinh xâu nhị phân thực sự có độ dài n, tức là kết quả in ra phải là các xâu kí tự chứ không phải là danh sách (list) như trong các chương trình trên.

4.6

73 Đánh giá

50%

40%

0%

0%

0%

Bạn vui lòng để lại thông tin để được
TƯ VẤN THÊM

Hoặc gọi Hotline tư vấn: 084 283 45 85
Email: vietjackteam@gmail.com

VietJack