Giáo án môn cấu trúc dữ liệu và giải thuật

TRƯỜNG CAO ĐẲNG CÔNG NGHIỆP TUY HÒA
HỘI THI GIÁO VIÊN DẠY GIỎI CẤP TRƯỜNG, NĂM 2010
















Họ và tên giáo viên: TRẦN THỊ ĐANG TÂM
Môn học: CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT
Tên bài giảng: TÌM KIẾM NHỊ PHÂN
Đơn vị: KHOA CÔNG NGHỆ THÔNG TIN.

TP.Tuy Hòa, Tháng 5/2010
Giáo án số:…15…..số tiết: 1 Tổng số tiết đã giảng: 69
(Thực hiện ngày 26 tháng 5 năm 2010)
Tên bài học: CHƯƠNG 4: SẮP XẾP VÀ TÌM KIẾM (tiếp theo)
A. MỤC TIÊU
Qua bài học này học sinh có khả năng:
- Xác định được ý tưởng của giải thuật tìm kiếm nhị phân
- Trình bày được các bước thực hiện giải thuật.
- Áp dụng giải thuật viết chương trình cài đặt các bài tập liên quan.
B. PHƯƠNG TIỆN, ĐỒ DÙNG DẠY HỌC:
Bảng, phấn, máy chiếu, máy tính xách tay, giáo án, bài giảng, đề cương chi tiết, bút chỉ laser.
C. TIẾN TRÌNH LÊN LỚP
I. Ổn định lớp: (Thời gian: 1 phút)




Lớp: CĐTin31A






1 tiết



Số người học vắng
- Có lý do
Tên:





- Không có lý do
Tên:





II. Kiểm tra bài cũ: (Thời gian: 5 phút)

Dự kiến người học được kiểm tra
Lớp: CĐTin31A

Họ và tên
Nguyễn Thị Thanh Thúy
Nguyễn Thanh Hội

Điểm




* Câu hỏi kiểm tra: Hãy viết hàm cài đặt giải thuật tìm kiếm tuần tự một giá trị X có kiểu số nguyên trên danh sách đặc A có n phần tử đã có thứ tự tăng dần. Nếu có thì trả về true, ngược lại thì trả về false. (Giả sử dãy số có kiểu số nguyên đã được định nghĩa sẵn)

III. Giảng bài mới:

Các nội dung giảng
Thời gian
(Phút)
Phương pháp
Hoạt động của người dạy
Hoạt động của người học
Phương tiện, đồ dùng, dạy học

Chương 4: SẮP XẾP VÀ TÌM KIẾM (tiếp theo)
4.4. Tìm kiếm (tiếp theo)
4.4.1. Tìm kiếm tuần tự (đã học)
4.4.2. Tìm kiếm nhị phân.
* Mục đích: Nhằm giới thiệu, mô phỏng và cài đặt giải thuật tìm kiếm nhị phân. Qua đó Học sinh có khả năng áp dụng giải thuật vào giải quyết các bài toán.
* Nội dung:
a. Ý tưởng giải thuật:









b. giải thuật.



Ví dụ 1: Tìm kiếm một giá trị là X=41 trên dãy số:
3 4 16 19 22 41 46 51 63 71
Ví dụ 2: Tìm kiếm một giá trị là X=45 trên dãy số:
3 4 16 19 22 41 46 51 63 71


c. Cài đặt giải thuật






d. Bài tập áp dụng:
Viết chương trình nhập vào từ bàn phím một dãy số nguyên gồm có n phần tử và một số nguyên X. Hãy cho biết vị trí tìm thấy phần tử có giá trị X khi áp dụng giải thuật tìm kiếm nhị phân. (Giả sử dãy số khi nhập đã có thứ tự tăng dần).




* Kết quả: Học sinh xác định được ý tưởng, trình bày được các bước thực hiện giải thuật và áp dụng giải thuật viết chương trình cài đặt các bài tập cụ thể.







3 phút




4 phút









3 phút



3 phút



3 phút





8 phút






12 phút







- Thuyết trình, diễn giải, trực quan


- Thuyết trình, trực quan, phát vấn.







- Thuyết trình, diễn giải, trực quan.

- Thuyết trình, diễn giải, phát vấn, trực quan

- Thuyết trình, diễn giải, trực quan, phát vấn



- Thuyết trình, diễn giải, trực quan.




- Thuyết trình, diễn giải, trực quan, phát vấn.







- Đặt vấn đề.




- Thuyết trình về ý tưởng thực hiện của giải thuật.

-