Trang bìa
Trang bìa
Ảnh
CHUYÊN ĐỀ 3: THỰC HÀNH THIẾT KẾ THUẬT TOÁN THEO KĨ THUẬT DUYỆT
BÀI 1: KĨ THUẬT DUYỆT
Mở đầu
Bài học
Hình vẽ
Học xong bài này, em sẽ: - Nêu được ý tưởn của kĩ thuật duyệt. - Tìm hiểu được một số bài toán sử dụng kĩ thuật duyệt. - Biết được các bước cần thực hiện khi giải toán bằng kĩ thuật duyệt.
Yêu cầu
Để 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ò có trá trị là 3. Em hãy cho biết đáp án nào sau đây biểu diễn cho số 8
Ảnh
Ý tưởng kĩ thuật duyệt
Ý tưởng
Để 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. Các làm như vậy được gọi là kĩ thuật duyệt. Con người chỉ sử dụng kĩ thuật duyệt khi giải những bài toán có ít trường hợp Ưu điểm: luôn tìm ra nghiệm đúng, cách làm này đơn giản và chính xác Nhược điểm: thời gian thực thi lâu nếu số trường hợp phải thử lớn.
Bài tập
Bài tập trắc nghiệm
Cho biết phương trình latex( x^3 - 2x^2 + x - 2 = 0) chỉ có một nghiệm nguyên 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 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
1
-1
2
-2
Bài toán Chọn mua đồ dùng học tập
Bài toán
Đầu năm học mới, Hồng cùng mẹ đã đặt mua trực tuyến các đồ dùng học tập cần thiết. Để thưởng cho Hồng vì thành tích học tập năm trước, mẹ cho phép Hồng lựa chọn thêm một đồ dùng nữa không có giá trị vượt quá T (đồng). Trên trang web hiện ra n đồ dùng, các đồ dùng được đánh số từ 0 đến n - 1 với mức giá tương ứng là latex( p_0, p_1, ..., p_(n-1)) và có mực độ yêu thích của Hồng tương ứng là latex( s_0, s_1, ..., s_(n-1)). Em hãy lập trình nhập vào hai số nguyên n, T cùng với 2 dãy latex( p_0, p_1, ..., p_(n-1)) và latex( s_0, s_1, ..., s_(n-1)), đưa ra một đồ dùng có giá trị không vượt quá T( đồng) mà Hồng yêu thích nhất.
Sơ đồ khối
Ảnh
Bài tập
Em hãy tìm hiểu chương trình viết trên ngôn ngữ lập trình Python giải bài toán trên, soạn thảo và chạy với bộ dữ liệu thử nghiệm trong Bảng 1.
Ảnh
Bài giải
Ảnh
Các bước thực hiện kĩ thuật duyệt
Bước
Để giải bài toán bằng kĩ thuật duyệt cần thực hiện các bước sau: 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
Câu 1
Câu 1: Chương trình trong Hình 4 giải bài toán Chọn mua hai đồ dùng học tập. Em hãy cho biết dấu (?) cần được thay bằng gì để chương trình chạy đúng. Em hãy soạn thảo, hoàn thiện chương trình và chạy với các bộ dữ liệu thử nghiệm trong bảng 2.
Ảnh
Câu 1
Ảnh
Câu 2
Xét phương trình latex(ax^5 + bx + c = 0 )với a,b,c là các hằng số nguyên khác 0 có giá trị tuyệt đối không vượt quá latex(10^6). Theo lược đồ Hoocne, nghiệm nguyên của đa thức sẽ là ước của c. Em hãy lập trình nhập vào ba số nguyên a,b,c. Sau đó, lập trình tìm tất cả các nghiệm nguyên của phương trình và chạy với các bộ dữ liệu thử nghiệm trong Bảng 3
Ảnh
Câu 3
Một lớp học nhảy có n bạn nam và n bạn nữ. Bạn nam thứ i ( latex(0 le i le n - 1)) có chiều cao là latex(b_i) (cm), bạn nữ thứ j (latex(0 le j le n - 1)) có chiều cao là latex(g_j)(cm). Trong một buổi học, thầy giáo muốn chọn ra một đôi nhảy gồm một bạn nam và một bạn nữ để trình diễn mà bạn nam cao hơn bạn nữa và chênh lệch độ cao của hai bạn là nhỏ nhất. Em hãy lập trình nhập vào hai dãy số latex(b_0,b_1,....,b_(n-1)) và latex(g_0,g_1,....,g_(n-1)), đưa ra hai số tương ứng là chiều cao của bạn nam và bạn nữ được chọn. Sau đó, chạy chương trình với các bộ dữ liệu trong Bảng 4.
Câu 3
Ảnh
Kết thúc
Tóm tắt bài học
Hình vẽ
Kĩ thuật duyệt được dùng để giải quyết nhiều bài toán. Ưu điểm của kĩ thuật duyệt là luôn đảm bảo tìm ra nghiệm đúng, nhưng thời gian thực thi lâu nếu số trường hợp phải thử lớn Hai bước cần thực hiện để giải bài toán bằng kĩ thuật duyệt: mô tả lời giải của bài toán; kiểm tra và chọn nghiệm.
TÓM TẮT BÀI HỌC
Tạm biệt
Ảnh