I. Mục đích yêu cầu
1.Mục đích
ã Hiểu được thuật toán tìm kiếm tuần tự.
ã Hình thành phát triển tư duy logic, tư duy giải thuật.Góp phần phát triển nhân cách con người trong xã hội tin học
2.Yêu cầu
ã Nắm bắt được các bước của thuật toán tìm kiếm tuần tự.
ã Hiểu và thực hiện được thuật toán tìm kiếm tuần tự
II. Phương pháp và đồ dùng học tập
1. Phương pháp: Thuyết trình và đặt câu hỏi gợi ý cho học sinh
Đồ dùng học tập: Sách giáo khoa, sách giá
Bạn đang xem tài liệu "Giáo án môn Tin học 10 - Tiết 14: Bài toán tìm kiếm tuần tự", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên
Đ4:Bài toán và thuật toán Tiết 14: Bài toán tìm kiếm tuần tự Ngày soạn: Ngày dạy: Người soạn: Phạm Đình Thanh GVHD: Lê Bích Liên Mục đích yêu cầu 1.Mục đích Hiểu được thuật toán tìm kiếm tuần tự. Hình thành phát triển tư duy logic, tư duy giải thuật.Góp phần phát triển nhân cách con người trong xã hội tin học 2.Yêu cầu Nắm bắt được các bước của thuật toán tìm kiếm tuần tự. Hiểu và thực hiện được thuật toán tìm kiếm tuần tự II. Phương pháp và đồ dùng học tập Phương pháp: Thuyết trình và đặt câu hỏi gợi ý cho học sinh Đồ dùng học tập: Sách giáo khoa, sách giáo viên III. Nội dung bài giảng *Bảng phân phối : Nội dung Thời gian ổn định lớp Kiẻm tra bài cũ 1’ 10’ Đặt vấn đề Xác định bài toán ý tưởng Thuật toán + Liệt kê + Sơ đồ khối Ví dụ mô phỏng 1’ 4’ 5’ 15’ 10’ 5’ 5’ Củng cố 4’ 1. ổn định lớp Lớp:......Sí số:........Vắng:.........Có phép:.Không phép: 2.Kiểm tra bài cũ: Câu hỏi: Hãy xác định bài toán và nêu thuật toán bằng phương pháp liệt kê của thuật toán sắp xếp bằng tráo đổi. Đáp án: Xác định bài toán: Input: Dãy A gồm n số nguyên a1,a2,,aN. Output: Dãy A đươc sắp xếp lại thành dãy không giảm. Thuật toán bằng cách liệt kê: B1: Nhập N, các số hạng a1,a2,,aN; B2: M ò N; B3: Nếu MM thì quay lại bước 3; B7: Nếu ai> ai+1 thì tráo đổi ai và ai+1 cho nhau; B8: Quay lại bước 5. 3.Bài mới: Đặt vấn đề: Tìm kiếm là việc thường xảy ra trong cuộc sống, chẳng hạn cần tìm cuốn sách giáo khoa Tin học 10 trên giá sách, cần tìm một học sinh trong danh sách một lớp học,...Hôm nay chúng ta sẽ tìm hiểu một thuật toán mới – Thuật toán tìm kiếm tuần tự. Nội dung Hoạt động của giáo viên và hoạt động của học sinh Bài toán Cho dãy A gồm N số nguyên 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ố đó. Số nguyên k được gọi là khóa tìm kiếm. 1.Xác định bài toán Input:Dãy số A gồm N số nguyên khác nhau a1,a2,...,aN và số nguyên k. Output: Chỉ số mà ai=k hoặc thông báo không có số hạng nào của A có giá trị bằng k. 2. ý 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á. 3.Thuật toán a] Cách liệt kê B1: Nhập N, các số hạng a1,a2,...,aNvà khoá k; B2: iò 1; B3: Nếu ai =k thì thông báo chỉ số i, rồi kết thúc; B4: i ò i+1; B5: 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 B6:Quay lại bước 3. b]Sơ đồ khối 4.Ví dụ +Với k=2; N=10 và dãy: 5,7,1,4,2,9,8,11,25,51 +Với k=6; N=10 và dãy: 5,7,1,4,2,9,8,11,25,51 GV: Nêu ví dụ: Cho dãy số A gồm các số:5,7,1,4,2,9,8,11,25,51. GV: Với k=2 trong dãy trên số hạng thứ mấy có giá trị bằng k? Chỉ số i cần tìm là bao nhiêu? HS: a5 =k; i=5. GV: Với k=6 trong dãy trên số hạng thứ mấy có giá trị bằng k? Chỉ số i cần tìm là bao nhiêu? HS: Không có số hạng nào; không có i GV: Để hiểu được việc tìm một số hạng trong dãy số nguyên bằng hay không bằng khoá k hay không ta đi vào bài hôm nay. GV:Em nào có thể xác định Input và Out put của bài toán trên HS: ứng tại chỗ trả lời GV: Nhận xét và viết lên bảng câu trả lời. GV: Chú ý k là khoá để tìm kiếm. GV:Lấy ví dụ minh hoạ +k=4 và N=5, dãy a: 5,7,1,4,6. A 5 7 1 4 6 i 1 2 3 4 5 GV: Ta thấy với các giá trị với mỗi giá trị của a tương ứng với chỉ số i tương ứng. Ta lần lượt xét từ đầu với i=1 đến cuối dãy i=5. Thì tại i=4 thì a4=k=4. +k=6 và N=5,dãy a: 4,11,3,9,7. A 4 11 3 9 7 i 1 2 3 4 5 6 GV: Ta làm tương tự như ví dụ trên thì thấy với mọi i từ 1 đến 5 không có ai có gá trị bằng 6. Từ hai ví dụ trên em nào có thể nêu ý tưởng của bài toán. HS: Trả lời GV: Nhận xét câu trả lời học sinh và đọc lại ý tưởng cho học sinh ghi bài. HS: Ghi ý tưởng vào vở. GV: Từ ý tưởng và ví dụ ở trên em nào có thể nêu được thuật toán bằng cách liệt kê? HS: Lên bảng trình bày GV:Nhận xét và sửa lại lỗi cho học sinh. GV:Giải thích rõ hơn về thuật toán. B1: Đầu tiên phải nhập N,dãy số,và khoá k. B2: Gán iò 1 có nghĩa là xét số hạng đầu tiên trong dãy. B3: Kiểm tra xem ai có bằng k không. Lúc này ta đang kiểm tra a1=k ? Nếu bằng thì đã tìm thấy thông bó ra chỉ số i và dừng thuật toán ngược lài ta sang B4. B4: Ta kiểm tra số hang tiếp theo bằng cách tăng iò i+1; B4: Nếu số hạng tiếp theo mà có chỉ số lớn hơn N[ i>N] tức là dãy đã được kiểm tra hết mà không có phần tử nào bằng khoá. Lúc này ta dừng thuật toá và thông báo không tìm thấy i để ai=k. Ngược lại i