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

Ngày soạn : 14/10/2006	Tiết thứ : 14 
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 nhị phân. 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 nhị phân 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’):
Gọi hai HS lên bảng:
Trình bày thuật toán tìm kiếm nhị phân bằng hai cách: liệt kê và sơ đồ khối.
Lấy một ví dụ minh họa cho thuật toán.
Vào bài mới(3’) : 
Vẫn xét bài toán tìm kiếm một giá trị khoá cho trước có bằng một phần tử trong dãy hay không? Nhưng bài xét ở đây là một dãy tăng. Xuất phát từ tính chất tăng của dãy ta có thể thu hẹp phạm vi tìm bằng một thuật toán khác như sau:
Nội dung bài mới : 
Nội dung
Hoạt động của giáo viên và học sinh
TG
Thuật toán Tìm kiếm nhị phân (Binary Search)
ã Xác định bài toán
- Input: Dãy A là dãy tăng gồm N số nguyên đôi một khác nhau a1, a2,..., aN và một 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: Khi đó, chỉ xảy ra một trong ba trường hợp sau:
- Nếu aGiua = k thì Giua là chỉ số cần tìm. Việc tìm kiếm kết thúc.
- Nếu aGiua > k thì do dãy A là dãy đã được sắp xếp nên việc tìm kiếm tiếp theo chỉ xét trên dãy a1, a2,..., aGiua–1 (phạm vi tìm kiếm mới bằng khoảng một nửa phạm vi tìm kiếm trước đó). 
- Nếu aGiua < k thì thực hiện tìm kiếm trên dãy aGiua+1, aGiua+2,..., aN. 
 Quá trình trên sẽ được lặp lại một số lần cho đến khi hoặc đã tìm thấy khoá k trong dãy A hoặc phạm vi tìm kiếm bằng rỗng.
ã Thuật toán
a) Cách liệt kê
Nhập N, các số hạng a1, a2,..., aN và khoá k;
Dau ơ 1, Cuoi ơ N;
Giua ơ ;
Nếu aGiua = k thì thông báo chỉ số Giua, rồi kết thúc;
Nếu aGiua > k thì đặt Cuoi = Giua – 1 rồi chuyển đến bước 7;
Dau ơ Giua + 1;
Nếu Dau > Cuoi thì thông báo dãy A không có số hạng có giá trị bằng k, rồi kết thúc;
Quay lại bước 3.
Ghi chú:
- Tuỳ thuộc aGiua > k hoặc aGiua < k mà chỉ số đầu hoặc chỉ số cuối của dãy ở bước tìm kiếm tiếp theo sẽ thay đổi. 
- Để thực hiện điều đó, trong thuật toán chỉ sử dụng các biến nguyên tương ứng Dầu và Cuối có giá trị khởi tạo Dau = 1 và Cuoi = N.
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.
i
1
2
3
4
5
6
7
8
9
10
A
2
4
5
6
9
21
22
30
31
33
Dau
1
6
6
Cuoi
10
10
7
Giua
5
8
6
aGiua
9
30
21
Lượt
0
1
2
ở lượt thứ hai thì aGiua = k. Vậy chỉ số cần tìm là i = Giua = 6.
i
1
2
3
4
5
6
7
8
9
10
A
2
4
5
6
9
21
22
30
31
33
Dau
1
6
6
7
8
Cuoi
10
10
7
7
7
Giua
5
8
6
7
aGiua
9
30
21
22
Lượt
0
1
2
3
4
Tại lượt thứ tư Dau > Cuoi nên kết luận trong dãy A không có số hạng nào có giá trị là 25 cả.
GV : Yêu cầu một HS đứng lên đọc bài toán.
GV: Giải thich: 
+ Sử dụng tính chất dãy A là dãy tăng, ta tìm cách thu hẹp nhanh phạm vi tìm kiếm sau mỗi lần so sánh khoá với số hạng được chọn. 
+ Để làm điều đó, ta chọn số hạng aGiua ở "giữa dãy" để so sánh với k, trong đó Giua = .
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: