Trang bìa
Trang bìa
Ảnh
CHUYÊN ĐỀ 2 THỰC HÀNH THIẾT KẾ THUẬT TOÁN THEO KĨ THUẬT CHIA ĐỂ TRỊ
BÀI 1 Ý TƯỞNG CHIA ĐỂ TRỊ
Khái niệm
Yêu cầu
Hình vẽ
Học xong bài này, em sẽ" * Nêu được ý tưởng kỹ thuật chia để trị và thu hẹp phạm vi tìm kiếm . * Hiểu được một số bài toán sử dụng kỹ thuật chia để trị. * Cài đặt được thuật toán tìm kiếm nhị phân và vòng lặp.
Thực hành
Hình vẽ
Trong sách Tin học 7, em đã học thật toán tìm kiếm nhị phân. Thuật toán này là một kỹ thuật thu hẹp phạm vi tìm kiếm trong phương pháp chia để trị. Em hãy quan sát dãy 9 số 9 được sắp xếp tăng dần sau: 4 7 8 20 21 22 36 77 81 Số 21 ở vị trí chính giữa của dãy, các số bên trái của số 21 luôn nhỏ hơn 21 và các số bên phải của số 21 luôn lớn hơn 21. Do đó, nếu muốn tìm một số x nhỏ hơn 21 thì chỉ cần thu hẹp phạm vi tìm kiếm vào một nửa của dãy, theo em đó là nửa dãy bên trái hay nửa dãy bên phải của số 21?
Ảnh
Kỹ thuật chia để trị
Yêu cầu 1
Hình vẽ
Hai mô tả sau đây chỉ ra phương pháp hiệu quả giải quyết bài toán bổ và đếm số hạt dưa bằng ý tưởng kỹ thuật chia để trị. Em hãy tìm hiểu bài toán sau đây và rút ra ý tưởng chủ đạo của kỹ thuật chia để trị để giải quyết bài toán
Ảnh
Bài toán bổ dưa và đếm số hạt
Hôm nay là sinh nhật của Thanh An, có tất cả 8 bạn tham dự. Thanh An có một quả dưa hấu muốn chia thành 8 miếng dưa đều nhau và muốn biết tổng số hạt của quả dưa này. Để các miếng dưa có thể đều nhau Thanh An nghĩ ra cách bổ đôi theo từng lượt (Hình 1) Lượt 1: Bổ đôi quả dưa thành hai miếng.(A/B) Lượt 2: Bổ đôi mỗi miếng A và B thành hai miếng (A.1/A.2) và (B.1, B.2). Lượt 3: Bổ đôi mỗi miếng (A.1/A.2) và (B.1, B.2). thành hai miếng (A.1/ A.1.2), (A.2/A.2.2), (B.1/B1.1), (B.2/B2.2)
Ảnh
Hình 1. Minh họa quá trình bổ các miếng dưa làm đôi
Nhận xét
Nhận xét: 1. Chia nhỏ miếng dưa thành hai miếng nhỏ. 2. Xử lý từng miếng bằng cách chia nhỏ tiếp mỗi miếng dưa thành hai miếng nhỏ hơn, tiếp tục như vậy đến khi số lượng miếng dưa mong muốn. Để biết tổng số hạt của quả dưa hấu Hình 2: Cộng dồn số hạt của từng miếng dưa, rồi cộng dồn số hạt của từng cặp miếng dưa,cộng dồn số hạt từng cặp của hai miếng dưa.
Ảnh
Hình 2 minh họa quá trình cộng dồn số hạt của các miếng dưa
Nhận xét
Cách giải quyết bài toán thể hiện ý tưởng chia để trị bao gồm ba bước: 1. Bước 1: Chia Chia bài toán ban đầu phức tạp thành hai hoặc nhiều bài toán con đơn giản hơn, tiếp tục chia mỗi bài toán con thành các bài toán con đơn giản hơn nữa và cứ như thế cho đến khi đạt được các bài toán con dù đơn giản mà chúng được giải quyết một cách dễ dàng. 2. Bước 2. Trị: Giải quyết các bài toán con một cách đệ quy. Kết quả là các lời giải của bài toán con. 3. Bước 3. Kết hợp: Kết hợp các lời giải của bài toán con để có được lời giải của bài toán ban đầu.
Yêu cầu 2
Hình vẽ
Trong các bài toán tìm kiếm trên một không gian xác định, thu hẹp gần phạm vi tìm kiếm là một kỹ thuật của Ý tưởng chia để trị. Em hãy tìm hiểu bài toán sau đây và cho biết ý tưởng chia để chị được thể hiện trong kỹ thuật thu hẹp phạm vi tìm kiếm
Ảnh
Bài toán tím điểm du lịc
Thanh An là một thanh niên sống ở Hà Nội và rất thích đi du lịch khám phá Để lên kế hoạch cho kỳ nghỉ lần này, Thanh An quan sát 25 tỉnh thành được liệt kê trên lược đồ một số địa điểm du lịch ở miền Bắc Việt Nam Hình 3 để chọn địa điểm phù hợp nhằm hạn chế số lượng điểm tìm kiếm. 1. Tiêu chí đầu tiên: Thanh An nhìn vào hai vùng của miền Bắc là: đồng bằng sông Hồng và trung du miền núi phía Bắc => Quyết định chọn vùng trung du và miền núi phía Bắc vì vùng này từ trước đến nay ít đi du lịch hơn. => Trên bản đồ chỉ còn số lượng địa điểm 15 tỉnh. 2. Tiêu chí thứ hai: Chỉ chọn những địa điểm du lịch nổi tiếng đã được in đậm trên bản đồ => Số lượng địa điểm trên bản đồ chỉ còn 5 tỉnh. 3. Tiêu chí thứ ba: Chọn địa điểm du lịch xa Hà Nội nhất, do có kỳ nghỉ dài ngày. Kết quả là tìm được ra một địa điểm: Cột cờ Lũng Cú - Hà Giang.
Bài toán tím điểm du lịch
Ảnh
Hình 3. Lược đồ một số địa điểm du lịch ở miền Bắc Việt Nam
Nhận xét
Nhận xét : Thu hẹp dần phạm vi tìm kiếm là một kỹ thuật của chia để trị. Kỹ thuật này được áp dụng trong các bài toán có thể loại bỏ đi những phần không gian tìm kiếm mà chắc chắn nghiệm của bài toán không nằm trong đó để giảm bớt độ phức tạp tính toán của thuật toán
Thực hành
Với bài toán tìm địa điểm du lịch, em hãy đảo thứ tự các tiêu chí thay đổi một số tiêu chí tìm địa điểm du lịch và quan sát các kết quả trung gian để thu được kết quả cuối cùng
thuật toán tìm kiếm nhị phân
Bài toán 1
Ảnh
Thực hành
Quan sát sơ đồ khối ở Hình 4 và đọc hiểu chương trình tìm kiếm nhị phân trên dãy số tăng dần trong Hình 5. Em hãy kiểm thử chương trình với các bộ dữ liệu thử nghiệm
Ảnh
Hình 4. Sơ đồ khối mô tả thuật toán tìm kiếm nhị phân trên dãy số tăng dần
Thực hành
Ảnh
Hình 5. Chương trình tìm kiếm nhị phân trên dãy số tăng dần và màn hình kết quả chạy một số bộ dữ liệu thử nghiệm
Bài toán 2
Ảnh
Thực hành
Ảnh
Hình 6. Chương trình tìm kiếm nhị phân trên dãy số tăng dần cho bài thực hành và màn hình kết quả chạy một số bộ dữ liệu thử nghiêm
Bài tập
Ứng dụng Sửa
Hình vẽ
Em hãy viết chương trình tìm kiếm nhị phân giá trị x trong dãy số không gian A có n phần tử, các phần tử có thể trùng nhau, kết quả hiển thị chỉ số nhỏ nhất i sao cho A latex(x-1) = x hoặc hiển thị thông báo không tìm thấy x
Ảnh
Câu hỏi
Hình vẽ
Câu 1. Trong thuật toán tìm kiếm nhị phân, tìm từ một phần tử có giá trị x trong dãy số có 20 phần tử, em hãy cho biết sau hai bước lặp chia đôi để tìm kiếm mà vẫn chưa tìm được giá trị x đó thì độ lớn không gian tìm kiếm còn lại (tức là độ dài đoạn dãy số cần tìm) là bao nhiêu. A.2 B.4 C.5 D.8 Câu 2 . Hai công thức tính số y trong chương trình của Hình 5 và Hình 6 có khác nhau. Em hãy cho biết hai chương trình này có cùng kết quả tìm kiếm không.
Ảnh
Bàihọc
Tóm tắt
Hình vẽ
Tóm tắt bài học. * Ý tưởng của chia để trị: Chia bài toán ban đầu (phức tạp) thành hai hoặc nhiều bài toán con (đơn giản hơn). Sau đó giải quyết các bài toán con và có được lời giải của các bài toán con. Cuối cùng. kết hợp các lời giải của bài toán con để có được lời giải của bài toán ban đầu . * Tìm kiếm nhị phân là một thuật toán của chia để trị để thu hẹp phạm vi tìm kiếm. Tại mỗi bước lặp ,phạm vi tìm kiếm bị giảm một nửa.
Cảm ơn
Thank You
Ảnh