Giáo á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: c Đơ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. - Phát vấn: Dựa vào ý tưởng giải thuật hãy cho biết giải thuật này áp dụng được cho danh sách liên kết không? Tại sao? - Nhận xét câu trả lời của học sinh. - Nêu và phân tích các bước thực hiện của giải thuật. - Phân tích và mô phỏng giải thuật tìm kiếm nhị phân trên ví dụ 1 - Thuyết trình, kết hợp với phát vấn học sinh xác định các giá trị trong giải thuật kết hợp mô phỏng giải thuật tìm kiếm nhị phân trên ví dụ 2 - Nhắc lại giải thuật. - Viết và phân tích hàm cài đặt giải thuật trên máy tính. - Trình chiếu cài đặt giải thuật bằng hàm. - Phân tích yêu cầu và đưa ra các chức năng cần thực hiện. - Gọi học sinh lên thực hiện từng chức năng trên bảng. - Nhận xét bài làm của học sinh. - Cho chạy chương trình để xem kết quả trong trường hợp danh sách có thứ tự và không có thứ tự . - Lắng nghe, quan sát, ghi chép và ghi nhận ý tưởng thực hiện - Trả lời phát vấn - Lắng nghe giáo viên nhận xét và ghi nhớ. - Lắng nghe, ghi chép và tiếp thu bài học. - Ghi nhận các bước. - Lắng nghe, ghi chép và lĩnh hội kiến thức. - Quan sát ví dụ 1. - Quan sát ví dụ 2 - Suy nghĩ và xác định các giá trị có trong giải thuật và trả lời phát vấn. - Lắng nghe, suy nghĩ, quan sát trên máy chiếu, lĩnh hội kiến thức. - Lắng nghe, quan sát và ghi chép, tiếp thu bài học. - Suy nghĩ phân tích bài toán. - Suy nghĩ viết chương trình theo từng chức năng. - Thực hiện yêu cầu của giáo viên trên bảng. - Quan sát và nhận xét bài làm của bạn. - Lắng nghe, ghi chép và xem kết quả chương trình. Bảng, Phấn, máy tính, máy chiếu. * Củng cố bài học: (Thời gian: 2 phút) Nội dung: Các bước thực hiện giải thuật tìm kiếm nhị phân. Phương pháp: Thuyết trình IV. Giao nhiệm vụ về nhà cho người học: (Thời gian: 1 Phút) - Cài đặt giải thuật toán tìm kiếm nhị phân bằng cách sử dụng giải thuật đệ quy - Cài đặt giải thuật bằng cách sử dụng thủ tục. - Trình bày các bước thực hiện giải thuật tìm kiếm nhị phân. - Làm bài tập 3 chương 4 trang 78 trong bài giảng. - Đọc trước bài cây nhị phân tìm kiếm, chú ý các giải thuật trên cây. D. RÚT KINH NGHIỆM SAU TIẾT GIẢNG: Ngày 26 tháng 5 năm 2010 TỔ BỘ MÔN DUYỆT GIÁO VIÊN GIẢNG