&4. BÀI TOÁN VÀ THUẬT TOÁN
Ngày soạn : 12/10/2007
Tiết : 13
Lớp : 10
I. MỤC ĐÍCH YÊU CẦU (Như tiết 10)
II. CHUẨN BỊ
Thầy:
- Soạn giáo án, nghiên cứu sách giáo khoa, sách bài tập, tài liệu tham khảo.
- Máy tính cá nhân và máy chiếu ( nếu có).
Trò: Đọc trước ở nhà Sách giáo khoa.
III.TIẾN TRÌNH LÊN LỚP.
1. Ổn định tổ chức, kiểm tra sĩ số (1’).
2. Kiểm tra bài cũ (5’).
- Câu hỏi:
Liệt kê các bước của thuật toán sắp xếp bằng tráo đổi?
- Đáp án:
+ 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 B3;
+ B7: Nếu ai >ai+1 thì tráo đổi ai và ai+1 cho nhau;
+ B8: Quay lại B5.
- Đối tượng HS: HS trung bình.
3. Nội dung bài học mới.
Nội dung
Hoạt động của GV
Hoạt động của HS


3. Một số ví dụ về thuật toán.





Ví dụ 3: Bài toán tìm kiếm.
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ố (1≤ i ≤ N) mà ai = k. Nếu có hãy cho biết chỉ số đó.

Thuật toán tìm kiếm tuần tự
* Xác định bài toán:
- Input: Dãy A và 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:
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á.




* Thuật toán:
a) Cách liệt kê:
B1: Nhập N, các số hạng a1,a2,…,aN
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.

















Ví dụ minh hoạ thuật toán:
k = 2 và N = 9
A
5
7
4
2
9
8
11
25
51

i
1
2
3
4
-
-
-
-
-

Với i = 4 thì a4 = 2.
K=6 và N =8
A
5
7
4
2
9
8
11
25


i
1
2
3
4
5
6
7
8
9

Với mọi i từ 1 đến 10 không có giá trị ai bằng 6.
GV: Tìm kiếm là một việc hay gặp trong cuộc sống: như tìm một HS trong danh sách lớp, … 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.
GV:
Nếu ví dụ: Tìm trong 4 HS nam trong lớp ở bàn đầu có em nào có chiều cao 1.65m và chỉ ra bạn đứng ở vị trí thứ mấy(nếu có).


GV: Đó chính là cách tìm kiếm tuần tự.
GV: Yêu cầu HS xác định Input, Output của bài toán:
GV: Gọi HS khác bổ sung.
GV: Đưa ra nhận xét và ghi bảng.

GV: Cách tìm ra bạn có chiều cao 1.65m như trên là ý tưởng của thuật toán tìm kiếm tuần tự.
GV: Yêu cầu HS nêu ý tưởng thuật toán.
GV: Đưa ra ý tưởng bài toán
GV: Từ ý tưởng ta có thế nêu lên các bước của thuật toán theo cách liệt kê:
GV: Để giải bài toán, cần có dữ liệu thì Bước 1 ta phải làm gì?
GV: Để xét duyệt các vị trí lần lượt từ số