§4:Bài toán và thuật toán
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ê Thị 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
1. định lớp
Lớp:............Sí số:...................Vắng:...........................
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.


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