§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

đị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. đị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 M<2 thì đưa ra dãy A được sắp xếp rồi kết thúc;
B4: M ( M-1, i(0;
B5: i( i+1;
B6: Nếu i>M 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