ỔN ĐỊNH LỚP VÀ KIỂM TRA SĨ SỐ
11/10
.Ổn định lớp và kiểm tra sĩ số.
Ngày dạy : 21/10
.Kiểm tra bài cũ:
-Câu hỏi: Hãy nêu ý tưởng của bài toán tìm GTLN?
.Bài mới:
HOẠT ĐỘNG CỦA GIÁO VIÊN VÀ HỌC
SINH
NỘI DUNG
Hoạt động: Viết chương trình sử dụng mảng 1 chiều.
GV: Trình bày phương pháp tìm kiếm nhị phân.
Ví dụ 3 : Tìm kiếm nhị phân .
Cho dãy số nguyên: k= {5,7,10,17,21, 29} với
-
Input : Dãy số A
1
, A
2
,………, A
N
đã được sắp
khóa X=21.
xếp tăng dần .
HS:
Trả lời câu hỏi của giáo viên: Input,
-
Output : Có hay không chỉ số i mà A[i] = k
Output.
hoặc thông báo không tìm thấy .
GV: Hãy xác định khóa X có nằm trong dãy K
-
Ý tưởng :
hay không? Xác định Input và Output?
Thuật toán tìm kiếm nhị phân trong SGK lớp 10 .
Chương trình như sau :
HS:
Chia đôi 1 mảng đã sắp xếp rồi so sánh
phần tử giữa lớn hơn hay nhỏ hơn giá trị X cần
Program sapxep ;
Uses crt ;
tìm ở bên phải hay bên trái của mảng.
var A : Array[1..250] of integer ;
GV: Hướng dẫn học sinh hiểu những đoạn câu
lệnh trong thuật toán tìm kiếm nhị phân ở ví dụ
n,i,k : Integer ;
dau,cuoi,giua : Integer ;
3 SGK trang 58.
TK : boolean ;
HS:
Theo dõi SGK trang 58.
Begin
clrscr ;
Write('Nhap so ptu mang n = ') ;
Readln(n) ;
For i := 1 to n do
Begin
Write('A[',i,'] = ') ;
readln(A[i]) ;
End ;
Write('nhap so can tim k : ') ;
Readln(k);
dau := 1 ; cuoi := n ;
TK := false ;
while (dau <= cuoi) and Not TK Do
giua := (dau+cuoi) div 2 ;
If A[giua] = k then TK := true
Else
If a[giua]>k then cuoi := giua - 1
Else dau := giua + 1 ;
If TK then write('Chi so la : ',giua)
else write(' Khong tim thay ');
readln ;
End .
.Củng cố:
-Ý tưởng giải bài toán tìm kiếm nhị phân.
.Dặn dò bài tập về nhà:
-Chuẩn bị bài mới: mảng hai chiều.
.Rút kinh nghiệm bổ sung:
...
------
Tiết : 22
Ngày soạn :