Giáo án Tin học 10 - Tiết 10 - Bài 4: Bài toán và thuật toán

bài 4: Bài toán và thuật toán (Tiết 14) Ngày soạn: 20/10/07 I- Mục đích và yêu cầu. - Nắm được cách xây dựng thuật toán tìm kiếm nhị phân - Phương pháp : Diễn giảng, giải thích - Đồ dùng: Sơ đồ, GAĐT II- Nội dung. 1. ổn định tổ chức lớp. Lớp Sĩ số Vắng Ghi chú 10A5 42 10A6 48 10A7 2. Kiểm tra bài cũ. Câu 1: Nêu thuật toán tìm kiếm tuần tự, diễn tả bằng 2 cách? 3. Bài mới. Nội dung Hoạt động của GV và HS Thuật toán Tìm kiếm nhị phân (Binary Search) ã Xác định bài toán - Input: Dãy A là dãy tăng gồm N số nguyên đôi một khác nhau a1, a2,..., aN và một số nguyên k; - Output: Chỉ số i mà ai = k hoặc thông báo không có số hạng nào của dãy A có giá trị bằng k. ã ý tưởng + Nếu aGiua = k thì Giua là chỉ số cần tìm. Việc tìm kiếm kết thúc. + Nếu aGiua > k thì do dãy A là dãy đã được sắp xếp nên việc tìm kiếm tiếp theo chỉ xét trên dãy a1, a2,..., aGiua–1 (phạm vi tìm kiếm mới bằng khoảng một nửa phạm vi tìm kiếm trước đó). GV: H/s hãy chỉ ra hai yếu tố để xđ bài toán GV: Sử dụng tính chất dãy A là dãy tăng, ta tìm cách thu hẹp nhanh phạm vi tìm kiếm sau mỗi lần so sánh khoá với số hạng được chọn. Để làm điều đó, ta chọn số hạng aGiua ở "giữa dãy" để so sánh với k, troKhi đó, chỉ xảy ra một trong ba trường hợp sau:  + Nếu aGiua < k thì thực hiện tìm kiếm trên dãy aGiua+1, aGiua+2,..., aN. Quá trình trên sẽ được lặp lại một số lần cho đến khi hoặc đã tìm thấy khoá k trong dãy A hoặc phạm vi tìm kiếm bằng rỗng. ng đó Giua = . ã Thuật toán a) Cách liệt kê Nhập N, các số hạng a1, a2,..., aN và khoá k; Dau<— 1, Cuoi <— N; Giua <— ; Nếu aGiua = k thì thông báo chỉ số Giua, rồi kết thúc; Nếu aGiua > k thì đặt Cuoi = Giua – 1 rồi chuyển đến bước 7; Dau <— Giua + 1; Nếu Dau > Cuoi thì thông báo dãy A không có số hạng có giá trị bằng k, rồi kết thúc; Quay lại bước 3. a) Cách vẽ sơ đồ khối VD: GV: Tuỳ thuộc aGiua > k hoặc aGiua < k mà chỉ số đầu hoặc chỉ số cuối của dãy ở bước tìm kiếm tiếp theo sẽ thay đổi. Để thực hiện điều đó, trong thuật toán chỉ sử dụng các biến nguyên tương ứng Dau và Cuoi có giá trị khởi tạo Dau = 1 và Cuoi = N. GV: Treo bảng phụ, hoặc chiếu bằng máy chiếu GV: Nhìn sơ đồ khối và diễn giải GV: Dựa vào sơ đồ khối, hs liệt kê các bước theo sơ đồ. Dưới đây là ví dụ mô phỏng các bước thực hiện thuật toán trên. k = 21, N =10 k = 25, N =10 i 1 2 3 4 5 6 7 8 9 10 i 1 2 3 4 5 6 7 8 9 10 A 2 4 5 6 9 21 22 30 31 33 A 2 4 5 6 9 21 22 30 31 33 Dau 1 6 6 Dau 1 6 6 7 8 Cuoi 10 10 7 Cuoi 10 10 7 7 7 Giua 5 8 6 Giua 5 8 6 7 aGiua 9 30 21 aGiua 9 30 21 22 Lượt 0 1 2 Lượt 0 1 2 3 4 ở lượt thứ hai thì aGiua = k. Vậy chỉ số cần tìm là i = Giua = 6. Tại lượt thứ tư Dau > Cuoi nên kết luận trong dãy A không có số hạng nào có giá trị là 25 cả. 4. củng cố: - Nắm vững được thuật toán tìm kiếm nhị phân 5. Bài tập về nhà: Bài tập: 1, 2, 3 (44) III. Rút kinh nhgiệm giờ dạy.