Giáo án Tin học 10 - Tiết 13 - 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 13) Ngày soạn: 10/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 - Thuật toán tìm kiếm tuần tự. - 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ũ. 3. Bài mới. Nội dung Hoạt động của GV và HS Ví dụ 3. Bài toán tìm kiếm Dưới đây ta chỉ xét bài toán tìm kiếm dạng đơn giản sau: Cho dãy A gồm N số nguyên, đôi một khác nhau: a1, a2,..., aN và một số nguyên k. Cần biết có hay không chỉ số i (1 Ê i Ê N) mà ai = k. Nếu có hãy cho biết chỉ số đó. Ví dụ, cho dãy A gồm các số: 5, 7, 1, 4, 2, 9, 8, 11, 25, 51. Với khoá k = 2, trong dãy trên có số hạng a5 có giá trị bằng k. Vậy chỉ số cần tìm là i = 5. Với khoá k = 6 thì không có số hạng nào Thuật toán Tìm kiếm tuần tự (Sequential Search) ã Xác định bài toán - Input: Dãy A gồm N số nguyên đôi một khác nhau a1, a2,..., aN và 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. của dãy A có giá trị bằng k. ã ý tưởng: Tìm kiếm tuần tự được thực hiện một cách tự nhiên. Lần lượt từ số hạng thứ nhất, ta so sánh giá trị số hạng đang xét với khoá cho đến khi hoặc gặp một số hạng bằng khoá hoặc dãy đã được xét hết và không có giá trị nào bằng khoá. Trong trường hợp thứ hai dãy A không có số hạng nào bằng khoá. ã Thuật toán a) Cách liệt kê Nhập N, các số hạng a1, a2,..., aN và khoá k; i <- 1; Nếu ai = k thì thông báo chỉ số i, rồi kết thúc; i <- i + 1; Nếu i > N thì thông báo dãy A không có số hạng nào có giá trị bằng k, rồi kết thúc; Bước 6 Quay lại bước 3. GV: Tìm kiếm là việc thường làm của mỗi người, chẳng hạn tìm cuốn sách giáo khoa Tin học 10 trên giá sách để chuẩn bị cho giờ học ngày hôm sau, tìm chiếc áo sơ mi mới màu trắng trong tủ quần áo,… Nói một cách tổng quát là cần tìm một đối tượng cụ thể nào đó trong tập các đối tượng cho trước. GV: Số nguyên k được gọi là khoá tìm kiếm (gọi tắt là khoá). GV: Lấy ví dụ trong thực tế về bài toán tìm kiếm 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ơ đồ. GV cùng HS thực hiện mô phỏng với thuật toán k = 2 và N = 10 k = 6 và N = 10 A 5 7 1 4 2 9 8 11 25 51 A 5 7 1 4 2 9 8 11 25 51 i 1 2 3 4 5 - - - - - i 1 2 3 4 5 6 7 8 9 10 11 Với i = 5 thì a5 = 2. Với mọi i từ 1 đến 10 không có ai có giá trị bằng 6. 4. củng cố: - Nắm được cách xây dựng thuật toán tìm kiếm - Thuật toán tìm kiếm tuần tự. 5. Bài tập về nhà: Bài tập: 1, 2, 3, 4, 5, 6 SGK (27) III. Rút kinh nhgiệm giờ dạy.