Kớ kim tra Ngy son: 5/10/2008
Ngy dy : 10/10/2008
Tit theo PPCT: 13
Đ4.Bài toán và thuật toán
I. MC TIấU
1. Kin thc:
- Hiu c khỏi nim thut toỏn l cỏch gii bi toỏn m v nguyờn tc cú th
giao cho mỏy tớnh thc hin.
- Biết biểu diễn thuật toán bằng cách liệt kê, sơ đồ khối.
- Hiểu v thực hiện đ ợc thuật toán tìm kiếm tuần tự.
2. K nng:
- Ch ra c Input v Output ca mt s bi toỏn a ra.
- Xây dựng đợc thuật toán cho một số bài toán đơn giản trong SGK.
3. Thỏi :
- Luyn kh nng t duy lụgic khi gii quyt mt vn no ú.
II.Đồ dùng dạy-học
-Sách giáo khoa, sách giáo viên.
III. HOT NG DY- HC
1. n nh t chc(1):
Kim tra s s.
2. Kiểm tra bài cũ(4 ):
- Câu hỏi: Trình bày ý tởng và viết thuật toán sắp xếp bằng tráo đổi?
3.Nội dung bi mi(38):
Ni dung Tg Hot ng ca GV v HS
3. Mt số vớ d:
Vớ d 3: Bi toỏn tỡm kim
Cho dóy A gm N s nguyờn khỏc
nhau:a
1
, a
2

thng xy ra trong cuc sng.
Chẳng hạn: Có 1 cái bánh đặt trong 5
cái hộp.Làm thế nào để tìm đợc cái
bánh đó?
- HS: Mở lần lợt từng hộp để tìm
- GV: Vậy thuật toán tìm kiếm tuần tự
trong Tin học nh thế nào ta cùng tìm
hiểu?
- Lấy ví dụ trực quan:
Cho dóy A gm: 5, 7, 1, 4, 2, 9, 8, 11,
25, 51. Tỡm i vi a
i
= 2 ?
->i = 5
- Hỏi: Xác định bài toán?
- HS trả lời
- Hỏi: Nghiên cứu SGK nêu ý tởng bài
toán
- Thut toỏn:
* Cỏch lit kờ:
- B1:Nhp N, cỏc s hng a
1
, a
2
,
, a
N
v khoỏ k;
- B2: i
ơ

- c trc thuật toán tìm kiếm nhị phân
RT KINH NGHIM, B SUNG:
....................................................................................................................................
....................................................................................................................................
....................................................................................................................................
....................................................................................................................................
....................................................................................................................................
....................................................................................................................................
ai>aj
i:=1,j:=1.
ai>aj
Đổi chổ ai cho aj
i=n
i:=i+1
Thông báo dãy tăng A