SỞ GIÁO DỤC VÀ ĐÀO TẠO THANH HÓA TRƯỜNG THPT NHƯ THANH SÁNG KIẾN KINH NGHIỆM ỨNG DỤNG THUẬT TOÁN CHẶT NHỊ PHÂN ĐỂ GIẢI MỘT SỐ BÀI TỐN TÌM KIẾM Người thực hiện: Lê Thị Liễu Chức vụ: Giáo viên SKKN thuộc lĩnh vực (mơn): Tin học THANH HỐ NĂM 2018 MỤC LỤC MỞ ĐẦU 1.1 Lí chọn đề tài 1.2 Mục đích nghiên cứu .1 1.3 Đối tượng nghiên cứu 1.4 Phương pháp nghiên cứu .1 NỘI DUNG…………………………………………………………………… … 2.1 Cơ sở lý luận 2 Thực trạng vấn đề .2 2.3 Ứng dụng thuật toán “Chặt nhị phân” 2.4 Hiệu 31 Kết luận, Kiến nghị 32 MỞ ĐẦU 1.1 Lí chọn đề tài Các tốn tìm kiếm chiếm phần lớn tập Tin học, Có nhiều phương pháp tìm kiếm để giải tốn tìm kiếm nhị phân phương pháp tốt thời gian thực nhanh Thuật tốn tìm kiếm nhị phân lại trình bày ngắn gọn, sơ lược sách giáo khoa 10, 11 khơng có ví dụ vận dụng dẫn đến học sinh khó ứng dụng để làm tập Trên thực tế gặp dạng tốn tìm kiếm học sinh dễ dàng tìm cách giải chưa tìm cách giải tối ưu để lấy hết điểm Đó lí để tơi chọn đề tài “ỨNG DỤNG THUẬT TỐN CHẶT NHỊ PHÂN ĐỂ GIẢI MỘT SỐ BÀI TỐN TÌM KIẾM” 1.2 Mục đích nghiên cứu Giúp học sinh vận dụng thuật toán chặt nhị phân để giải số toán 1.3 Đối tượng nghiên cứu - Thuật toán chặt nhị phân - Một số ví dụ vận dụng, đánh giá độ phức tạp thuật toán 1.4 Phương pháp nghiên cứu - Nghiên cứu sách, báo, tài liệu điện tử - Áp dụng vào giảng dạy bồi dưỡng HSG Tin học 11 NỘI DUNG 2.1 Cơ sở lý luận  Bài tốn tìm kiếm dạng đơn giản SGK lớp 10: Cho dãy A gồm N số nguyên khác nhau: a1, a2,…,aN số nguyên K Cần biết có hay khơng số i mà ai=K (1