Ngày soạn : 10/9/2010
Tiết : 15,16,17 BÀI DẠY



MỤC TIÊU :
Kiến thức :
Hiểu được thuật toán tìm kiếm tuần tự
Thuật toán tìm kiếm nhị phân
được một số thuật toán cho các bài toán
Kỹ năng :
- ra được Input và Output của một số bài toán đưa ra.
- Xây dựng thuật toán cho một số bài toán đơn giản: Bài toán tìm kiếm tuần tự
tưởng, tình cảm :
Các kiến thức trên góp phần phát triển khả năng tư duy khi giải quyết các vấn đề trong khoa học cũng như trong cuộc sống
Nghiêm túc trong học tập để tìm hiểu phương pháp giải bài toán trong tin học từ dễ đến khó.
PHÁP VÀ PHƯƠNG TIỆN DẠY HỌC
pháp :
Phát vấn
Làm việc nhóm
Thuyết trình
Phương tiện :
Giáo viên : Sách + giáo án + phụ vẽ thuật toán
Học sinh :sách giáo khoa
TIẾN TRÌNH GIỜ DẠY
Ổn định lớp
Kiểm tra bài cũ :
Câu hỏi 1 : Trình bày thuật toán sắp xếp một dãy số
Câu hỏi2 :
Tiến trình dạy học :

TG
Hoạt động của giáo viên
Hoạt động của học sinh
Nội dung ghi bảng


15

5’
: Xác định bài toán


Hãy xác định Input và Output của bài toán?

+ Input: Dãy A gồm N số nguyên khác nhau a1, a2, ... , aN
+ 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 có giá trị bằng k.
ghi chép, nghe giảng

Bài toán tìm kiếm
Cho dãy A gồm N số nguyên 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ố đó.
- Số nguyên k được gọi là khóa tìm kiếm.
- Xác định bài toán:
Thuật toán tìm kiếm tuần tự


7’
: Nêu ý tưởng bài toán


HS đứng tại chỗ nêu ý tưởng giải bài toán
Đứng tại chỗ nêu ý tưởng giải bài toán
- Ý tưởng giải thuật:
Lần lượt từ số hạng thứ nhất, so sánh giá trị của số hạng đang xét với khóa cho đến khi gặp 1 số hạng bằng khóa hoặc khi xét hết dãy mà không có giá trị nào bằng khóa.

15’
: Viết thuật toán


Cho HS hoạt động theo nhóm , sau đó trình bày thuật toán
Trình bày thuật toán
- Thuật toán:
+ Phương pháp liệt kê:
Bước 1: Nhập N, các số hạng a1, a2, a3, ..., aN và khóa k;
Bước 2: i (1 ;
Bước 3: Nếu ai = k thì chỉ số i rồi kết thúc;
Bước 4: i ( i + 1;
Bước 5: 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;
Bước 6: Quay lại bước 3;


10’
: Chuyển thuật toán liệt kê sang sơ đồ khối


Hs lên bảng dựa theo thuật toán viết cách liệt kê chuyển sang sơ đồ khối
bảng diễn tả thuật toán



16

5’
: Xác định bài toán


Hôm trước chúng ta đã xây dựng thuật toán cho bài toán tìm kiếm tuần tự. Hôm nay chúng ra tiếp tục xây dựng thuật toán cho bài toán tìm kiếm nhị phân:
Hãy xác định Input và Output của bài toán?

Input: Dãy A gồm N số nguyên khác nhau a1, a2, ... , aN không giảm và 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 có giá trị bằng k.
ghi chép, nghe giảng

Ví dụ về thuật toán

Bài toán tìm kiếm
Cho dãy A gồm N số nguyên a1, a2, ... , aN đã được sắp xếp không giảm 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ố đó.
- Số nguyên k được gọi là khóa tìm kiếm.
Thuật toán tìm kiếm nhị phân


7’
: Nêu ý tưởng bài toán


HS đứng tại chỗ nêu ý tưởng giải bài toán
Đứng tại chỗ nêu ý tưởng giải bài toán
Ý tưởng giải thuật:
+ Chọn agiữa ở giữa dãy số để so sánh với k.
giữa =

* Nếu agiữa = k thì giữa là chỉ số cần tìm.
* Nếu agiữa>k thì ta chỉ xét khoảng a1, a2, ..., agiữa-1
* Nếu agiữa