Giáo án điện tử chuyên đề Khoa học máy tính 11 cánh diều Bài 1: Kĩ thuật duyệt

XIN CHÀO MỪNG CÁC EM

ĐẾN VỚI BÀI HỌC MỚI!

KHỞI ĐỘNG

Để bảo mật thông tin khi trao đổi, một nhóm bạn đã thống nhất mã hóa các số nguyên dương bằng các thanh ngang và chấm tròn, trong đó mỗi thanh ngang có giá trị là 1, mỗi chấm tròn có giá trị là 3. Em hãy cho biết đáp án nào dưới đây biểu diễn cho số 8.

• Phương án A: có 2 thanh ngang và 1 chấm tròn: 1 + 1 + 3 = 5.
• Phương án B: có 2 thanh ngang và 2 chấm tròn: 1 + 1 + 3 + 3 = 8.
• Phương án C: có 3 thanh ngang và 1 chấm tròn: 1 + 1 + 1 + 3 = 6.
• Phương án D: có 3 thanh ngang và 2 chấm tròn: 1 + 1 + 1 + 3 + 3 = 9.

GỢI Ý

BÀI 1.

KĨ THUẬT DUYỆT

CHUYÊN ĐỀ 3. THỰC HÀNH THIẾT KẾ THUẬT TOÁN THEO KĨ THUẬT DUYỆT

NỘI DUNG BÀI HỌC

1

Ý tưởng

kĩ thuật duyệt

2

Bài toán Chọn mua đồ dùng

học tập

3

Các bước thực hiện kĩ thuật duyệt

PHẦN 1: Ý TƯỞNG KĨ THUẬT DUYỆT

Kĩ thuật duyệt là một kĩ thuật đơn giản và được sử dụng để giải quyết nhiều bài toán tin học.

“

Ý tưởng của kĩ thuật duyệt là gì?

Để tìm đáp án cho một bài toán, ta có thể thử tất cả các trường hợp xảy ra rồi chọn phương án đúng.

Kĩ thuật duyệt

Hoạt động 1

Cho biết phương trình x3 – 2x2 + x – 2 = 0 chỉ có một nghiệm duy nhất, nghiệm đó là một trong các trường hợp dưới đây. Em hãy cho biết đâu là nghiệm nguyên dương của phương trình, giải thích cách làm và trình bày ưu nhược điểm của cách làm đó.

A. 1

B. -1

C. 2

D. -2

B là đáp án đúng

Ưu điểm

Luôn tìm được đáp án đúng, cách làm đơn giản và chính xác.

Nhược điểm

Mất thời gian.

PHẦN 2: BÀI TOÁN CHỌN MUA ĐỒ DÙNG HỌC TẬP

Thảo luận nhóm đôi: Nghiên cứu Bài toán mua đồ dùng học tập và mô tả thuật toán.

Hình 2. Sơ đồ khối giải bài toán Chọn mua đồ dùng học tập

Em hãy thực hành trên máy và kiểm tra thử với các bộ dữ liệu mẫu và bộ dữ liệu tự tạo thêm.

Hình 3. Chương trình cho thuật toán ở Hình 2

Bảng 1. Một số bộ dữ liệu thử nghiệm cho Hoạt động 2

PHẦN 3: CÁC BƯỚC THỰC HIỆN KĨ THUẬT DUYỆT

Nghiên cứu bài toán “Chọn mua hai đồ dùng học tập” và trả lời câu hỏi:

• Trong bài toán này, cần bao nhiêu chỉ số để mô tả đồ dùng được chọn? Có thể biểu diễn cặp chỉ số như thế nào?
• Có bao nhiêu khả năng có thể xảy ra?

CÁC BƯỚC THỰC HIỆN KĨ THUẬT DUYỆT

1. Mô tả lời giải của bài toán: Biểu diễn từng thành phần của lời giải bằng các biến và chỉ rõ miền giá trị của chúng.

2. Kiểm tra và chọn nghiệm: Liệt kê tất cả các khả năng theo cách đã mô tả, với mỗi khả năng kiểm tra điều kiện để chọn nghiệm.

LUYỆN TẬP

Câu 1: Đáp án nào không phải ưu điểm của kĩ thuật duyệt:

A. Đảm bảo tìm ra nghiệm đúng.

B. Cách làm đơn giản.

C. Chính xác

D. Thời gian thực thi lâu.

D. Thời gian thực thi lâu.

Câu 2: Các bước thực hiện kĩ thuật duyệt lần lượt là:

A. Mô tả lời giải của bài toán, kiểm tra và chọn nghiệm.

B. Kiểm tra và mô tả lời giải của bài toán, Chọn nghiệm.

C. Kiểm tra và chọn nghiệm, mô tả lời giải của bài toán.

D. Chọn nghiệm và mô tả lời giải của bài toán, kiểm tra.

A. Mô tả lời giải của bài toán, kiểm tra và chọn nghiệm.

Câu 3: Mô tả lời giải của bài toán thực hiện như thế nào?

A. Tóm tắt bài toán.

B. Biểu diễn từng thành phần của lời giải bằng các biến và chỉ rõ miền giá trị của chúng.

C. Liệt kê tất cả các khả năng.

D. Kiểm tra điều kiện để chọn nghiệm.

B. Biểu diễn từng thành phần của lời giải bằng các biến và chỉ rõ miền giá trị của chúng.

Câu 4: Đối với thuật toán và dữ liệu được cho như sau:

Dữ liệu vào: 4 50

35 26 37 40

7 7 6 6

Hãy chọn đáp án đúng:

A. Chọn mua đồ dùng số 1.

B. Chọn mua đồ dùng số 2.

C. Chọn mua đồ dùng số 3.

D. Chọn mua đồ dùng số 4.

B. Chọn mua đồ dùng số 2.

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