Giáo án chuyên đề Khoa học máy tính 11 cánh diều CĐ3 Bài 2: Kĩ thuật quy lui.

HOẠT ĐỘNG CỦA GV VÀ HS

SẢN PHẨM DỰ KIẾN

Bước 1: GV chuyển giao nhiệm vụ học tập

- GV yêu cầu HS thảo luận cặp đôi, nghiên cứu Bài toán tổng quát mua đồ dùng học tập và hoàn thành yêu cầu phần hoạt động.

- GV mời 1 HS đứng tại chỗ trả lời.

- GV nhận xét, kết luận “Để giải quyết bài toán Mua đồ tổng quát bằng kĩ thuật duyệt ta có thể xét toàn bộ dãy bit độ dài , mỗi dãy bit tương ứng với một phương án mua”.

Bước 2: Thực hiện nhiệm vụ

- HS tìm hiểu thông tin sách CĐHT, thực hiện nhiệm vụ và thảo luận trả lời câu hỏi.

Bước 3: Báo cáo, thảo luận

- Đại diện nhóm HS báo cáo.

- Một số HS nhóm khác nhận xét, bổ sung cho bạn.

Bước 4: Kết luận, nhận định

- GV nhận xét kết quả thảo luận nhóm, thái độ làm việc của các HS.

- GV tổng quát lại kiến thức trọng tâm và yêu cầu HS ghi chép đầy đủ vào vở.

1. Bài toán Mua đồ tổng quát

Hoạt động 1

Lời giải bài toán này có thể biểu diễn bằng 1 dãy bit độ dài  (là số lượng đồ vật), trong đó bit thứ  () bằng 1 hoặc 0 tương ứng là vật thứ  được chọn hoặc không chọn.

Ví dụ: dãy bit (1, 0, 0, 1, 0) tương ứng với cách chọn đồ dùng số 0 và 3 với tổng giá là 10 + 9 = 19 (nghìn đồng) và mức độ yêu thích là 7 + 6 = 13; dãy bit (1, 1, 0, 0, 1) tương ứng với cách chọn đồ dùng số 0, 1 và 4 có tổng giá là 10 + 5 + 5 = 20 (nghìn đồng) và mức độ yêu thích là 7 + 2 + 3 = 12.

HOẠT ĐỘNG CỦA GV VÀ HS

SẢN PHẨM DỰ KIẾN

Bước 1: GV chuyển giao nhiệm vụ học tập

- GV yêu cầu HS thảo luận cặp đôi, tìm hiểu chương trình liệt kê dãy bit độ dài  bằng kĩ thuật đệ quy và hoàn thành yêu cầu hoạt động 2.

-     GV yêu cầu HS tìm hiểu SCĐ đưa ra cách xây dựng dãy nhị phân theo thuật toán đệ quy.

- GV giải thích cho HS quá trình xây dựng các dãy nhị phân với độ dài

- GV tổng hợp, giải thích cụ thể trên các lệnh của chương trình và nhận định “Để trả lời số lượng dãy bit nhị phân độ dài , ta có thể tính theo công thức ”.

- GV yêu cầu HS dùng kết quả trên để kiểm tra chương trình.

Bước 2: Thực hiện nhiệm vụ

- HS tìm hiểu thông tin sách CĐHT, thực hiện nhiệm vụ và thảo luận trả lời câu hỏi.

Bước 3: Báo cáo, thảo luận

- Đại diện nhóm HS báo cáo.

- Một số HS nhóm khác nhận xét, bổ sung cho bạn.

Bước 4: Kết luận, nhận định

- GV nhận xét kết quả thảo luận nhóm, thái độ làm việc của các HS.

- GV tổng quát lại kiến thức trọng tâm và yêu cầu HS ghi chép đầy đủ vào vở.

2. Liệt kê dãy bit độ dài  bằng kĩ thuật đệ quy

Hoạt động 2

Dãy bit độ dài  có dạng ,  trong đó  bằng 0 hoặc  có thể mô tả theo cách đệ quy như sau:

-  Nếu  thì phần tử đầu tiên của dãy bằng 0 hoặc 1 và  phần tử sau là dãy bit độ dài .

-  Ngược lại, nếu  thì dãy bit độ dài  là dãy rỗng.

Việc xây dựng các dãy nhị phân theo thuật toán đệ quy như sau:

1. Bắt đầu từ  rỗng, lệnh  và gọi thủ tục đệ quy backtrack(0) để xây dựng bắt đầu từ phần tử 0.

2. Thành phần  sẽ lần lượt nhận giá trị 0 và 1 bằng lệnh for v in range(2): Với mỗi giá trị của  vào cuối . Sau đó tiếp túc gọi đệ quy để xây dựng các thành phần còn lại (từ thành phần  đến thành phần ).

3, Để xét được khả năng tiếp theo, hành động quay lui được thực hiện bằng cách loại bỏ ghi nhận thành phần cuối cùng của  bằng lệnh x.pop(). Việc quay lui cũng được diễn ra khi đang xây dựng thành phần  mà  đã lần lượt nhận cả hai giá trị 0 và 1, khi đó thành phần  sẽ bị loại khỏi  và lùi về để xét khả năng tiếp theo cho thành phần .

Dãy trong hình chữ nhật là dãy bit trong quá trình xây dựng, số trong hình ô van là thứ tự gọi đệ quy trong quá trình xây dựng.

HOẠT ĐỘNG CỦA GV VÀ HS

SẢN PHẨM DỰ KIẾN

Bước 1: GV chuyển giao nhiệm vụ học tập

- GV yêu cầu HS thảo luận cặp đôi, nghiên cứu cách xây dựng lời giải của bài toán có dạng:

 với  (trong đó  là tập các giá trị có thể của .

- GV khái quát, giải thích kĩ thuật quay lui.

- GV yêu cầu HS tìm hiểu mô hình kĩ thuật quay lui.

Bước 2: Thực hiện nhiệm vụ

- HS tìm hiểu thông tin sách CĐHT, thực hiện nhiệm vụ và thảo luận trả lời câu hỏi.

Bước 3: Báo cáo, thảo luận

- Đại diện nhóm HS báo cáo.

- Một số HS nhóm khác nhận xét, bổ sung cho bạn.

Bước 4: Kết luận, nhận định

- GV nhận xét kết quả thảo luận nhóm, thái độ làm việc của các HS.

- GV tổng quát lại kiến thức trọng tâm và yêu cầu HS ghi chép đầy đủ vào vở.

3. Kĩ thuật quay lui

Xây dựng lời giải dần từng bước:

1. Bắt đầu từ lời giải rỗng [].

2. Giả sử, hiện tại đang xây dựng được  thành phần , để xây dựng thành phần , cần xét từng khả năng trong .

- Nếu xây dựng xong lời giải thì lời giải sẽ được kiểm tra đánh giá và chọn nghiệm. Nếu chưa xây dựng xong lời giải thì xây dựng tiếp thành phần .

- Nếu đã xét xong các khả năng cho thành phần  thì quay lui xét khả năng tiếp theo của thành phần .

Quá trình sẽ dừng lại khi tất cả các khả năng lựa chọn của các thành phần của lời giải đều đã được xét.

-     Khi cài đặt kĩ thuật quay lui, người ta sử dụng kĩ thuật để quy để xây dựng tất các các khả năng của lời giải, với mỗi khả năng kiểm tra đánh giá để chọn nghiệm.