Giáo án môn Tin học 10 - Tiết 14: Bài toán tìm kiếm tuần tự

Đ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 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 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<N thì ta tiếp tục quay lại B3 để tiến hành tìm kiếm.
GV:Thuật toán sẽ dừng khi nào?
HS: Khi tìm thấy số hạng bằng khoá hoặc khi xét hết dãy mà không có phần tử nào bằng khoá.
GV:Treo bảng phụ sơ đồ khối biểu diễn thuật toán:
GV: Giải thích sơ đồ khối
Chỉ ra sự giống nhau giữa sơ đồ khối và cách biểu diễn thuật toán bằng cách liệt kê.
GV: Đưa ra ví dụ sách giáo khoa giúp học sinh hiểu rõ về hai thuật toán.
k=2 và N=10
A
5
7
1
4
2
9
8
11
25
51
i
1
2
3
4
5
Với i=5 thì a5=2;
k=6 và N=10
A
5
7
1
4
2
9
8
11
25
51
i
1
2
3
4
5
6
7
8
9
10
11
 Với mọi i từ 1 đến 10 không có giá trị ai có giá trị bằng 6.
GV: Dựa vào sơ đồ khối (hoặc thuật toán bằng cách liệt kê giải thích ví dụ cho HS .
HS: Quan sát + lắng nghe .
	4.Củng cố và bài tập về nhà
Củng cố: Nắm chắc các bước của thuật toán tìm kiếm tuần tự.
Bài tập về nhà:làm bài 7 sách giáo khoa trang 44 và đọc trước thuật toán tìm kiếm nhị phân
IV.Nhận xét của GVHD