Giáo án Tin học 10 tiết 13: Bài toán và thuật toán

Ngày soạn : 14/10/2006	Tiết thứ : 13 
Ngày giảng: 16/10/2006	Tên bài giảng: Đ4. Bài toán và thuật toán 
Mục đích, yêu cầu
1. Kiến thức.
- Nắm được nhu cầu tìm kiếm và các khái niệm liên quan trong tìm kiếm
- Nắm được giải thuật tìm kiếm tuần tự. 2. Kỹ năng.
Xây dựng được thuật toán giải một số bài toán đơn giản : Thuật toán tìm kiếm tuần tự bằng sơ đồ khối hoặc liệt kê các bước.
3. Thái độ.
- Thông qua thuật toán để rèn luyện tư duy cho HS. 
- Có thể nói rằng các kiến thức này không chỉ giúp ích cho HS tiếp tục học Tin học về sau mà quan trọng hơn là góp phần phát triển trí tuệ, khả năng tư duy để giải quyết vấn đề cho HS trong học tập cũng như trong công việc phục vụ xã hội.
Nội dung
Kiểm tra bài cũ (10’):
Mô phỏng thuật toán sáp xếp bằng tráo đổi để sắp xếp dãy sau thành dãy giảm
9	 8	1	4	7	5	2	10
1	 7	 3	 12	 6	 8	 22	16 
Vào bài mới(3’) : 
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.
Dưới đây ta chỉ xét bài toán tìm kiếm dạng đơn giản sau:
3. Nội dung bài mới : 
Nội dung
Hoạt động của giáo viên và học sinh
TG
Ví dụ 3. Bài toán tìm kiếm
Cho dãy A gồm N số nguyênkhá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 của dãy A có giá trị bằng k. 
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 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.
ã ý 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;
Quay lại bước 3.
b) Sơ đồ khối
ã Ví dụ mô phỏng các bước thực hiện của thuật toán trê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.
GV: Để xem điểm môn tin của học sinh Lan lớp 10T, ta cần làm như thế nào?
HS: Tìm người có tên Lan trong cột Họ và tên trong sổ điểm rồi xem điểm tương ứng.
HS: Xem kết quả thi, xem thời khóa biểu,...
GV: Trong thực tế còn có những tình huống nào tương tự?
GV: Trong thực tế, nhu cầu tìm kiếm rất lớn. Liệu có một cách giải quyết chung cho tất cả hay không?
Khi ra mạng tìm kiếm thông tin, máy tính thực hiện rất nhanh. Phải chăng có một cách thức nào đó áp dụng cho mọi trường hợp?
GV: Để đơn giản, ta xét 1 ví dụ sau. Yêu cầu HS đứng lên đọc bài toán ở phần SGK in nghiêng
GV: Yêu cầu HS xác định bài toán
Gv: XD ý tưởng. Các em hãy đề xuất ý tưởng để giải quyết bài toán? dựa trên ví dụ.
Nếu hs không trả lời được, hỏi tiếp như sau:
GV. Đặt câu hỏi: 
+ Để tìm số điện thoại cố định của một người quen trong danh bạ khi biết họ và tên, em làm thế nào?
+ Phạm vi tra cứu?
+ Khi xét 1 tên trong danh bạ, ta cần làm gì?
HS: Tra trong danh bạ theo tên. So sánh với tên của người cần tìm. Nếu giống tên cần tìm thì cho số điện thoại cần tìm. Nếu hết tên mà vẫn chưa thấy giống thì kết luận không có.
HS: So sánh tên người đó với tên cần tìm. Xét từ đầu đến cuối.
Phương pháp: vấn đáp
GV: Có thể áp dụng cách này cho ví dụ về dãy số ở trên được không?
HS: Có. Ta so sánh k với lần lượt các phần tử trong dãy cho đến khi thấy hoặc hết.
CH: Khi xem xét phần tử thứ i (tức ai), ta có những thao tác gì với nó?
HS: So sánh ai với k Nếu:
ai = k thì KL vị trí của ptử
ai k thì xét tiếp pt tiếp theo bằng cách tăng lên i + 1
GV: Ta tăng i lên 1 đơn vị thì ai lúc này có gì khác ai trước khi tăng i?
HS: Đó là phần tử kế tiếp trong dãy.
HS: mô tả
GV: Để xét phần tử tiếp theo ta tăng i.
CH: Ta bắt đầu giải thuật từ phần tử nào cho đến phần tử nào?
TL: Từ a1 cho đến an
CH: Hãy mô tả ý tưởng đó thành các bước
Sau đó:
GV: Chính xác hóa giải thuật bằng hai cách (liệt kê và sơ đồ khối)
GV: Với cách sơ đồ khối ta nên gọi một HS lên bảng trình bày.
HS: Dựa trên cách liệt kê.
GV: Kết hợp với HS để minh hoạ ví dụ này.
Nên đưa ra phương án i để HS tự so sánh và nhận ra kết quả.
5’
3’
7’
10’
5’
5’
IV. Củng cố, bài tập: (3’)
1. Củng cố: 
Đặc trưng nhất của giải thuật tìm kiếm tuần tự? TL Xét lần lượt từ đầu đến cuối.
Ta có thể xét từ cuối về đầu được không? TL: Tương tự nhưng ta giảm i và so sánh i với 1.
Ta có thể áp dụng giải thuật trên cho rất nhiều bài toán có dạng tìm một đối tượng cụ thể trong một tập các đối tượng cho trước.
2. Bài tập:
B1. Viết giải thuật tìm các số nguyên tố trong dãy số nguyên dương a1, ..., an.
B2. Viết giải thuật tìm số lớn thứ nhì trong dãy a1, ..., an.
CH: Nếu dãy a1, ..., an đã được sắp xếp theo thứ tự tăng thì có thể có cách nào tìm kiếm nhanh hơn không?
V. Rút khinh nghiệm giảng dạy: