Bạn đang xem tài liệu "Vận dụng thuật toán tìm kiếm nhị phân giải một số bài tập Tin Học", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên
SỞ GIÁO DỤC VÀ ĐÀO TẠO THANH HÓA TRƯỜNG THPT CHUYÊN LAM SƠN SÁNG KIẾN KINH NGHIỆM VẬN DỤNG THUẬT TOÁN TÌM KIẾM NHỊ PHÂN GIẢI MỘT SỐ BÀI TẬP TIN HỌC Người thực hiện: Trịnh Hồng Nam Chức vụ: Giáo viên SKKN thuộc lĩnh vực: Tin học THANH HÓA NĂM 2016 MỤC LỤC ĐẶT VẤN ĐỀ Lý do chọn đề tài Tìm kiếm là một việc thường xảy ra trong cuộc sống. Tìm kiếm luôn là thao tác nền móng cho rất nhiều tác vụ tính toán. Thuật toán tìm kiếm nhị phân là một trong những thuật toán tìm kiếm quan trọng nhất của tin học. Thuật toán này còn được gọi là thuật toán chặt nhị phân hay thuật toán chia đôi được áp dụng rất nhiều trong giải toán, nó làm giảm được nhiều thời gian tìm kiếm, giúp chương trình chạy nhanh hơn. Tuy nhiên, nhận thấy thuật toán này chưa được áp dụng rộng rãi nên tôi lựa chọn đề tài “Vận dụng thuật toán tìm kiếm nhị phân giải một số bài tập Tin học” để tìm hiểu và phát triển thuật toán phổ biến hơn. Mục đích nghiên cứu Trong phạm vi đề tài của mình tôi muốn nghiên cứu một số bài tập tuy không phải mới nhưng khi áp dụng thuật toán tìm kiếm nhị phân thì hiệu quả thuật toán nâng lên rõ rệt, nhằm giúp học sinh hình thành kỹ năng giải bài toán tin học và rèn luyện tư duy thuật toán từ đó rèn luyện tư duy lập trình. Cũng qua đề tài, tôi muốn cùng đồng nghiệp trao đổi, trau dồi chuyên môn nhằm góp phần nâng cao trình độ chuyên môn nghiệp vụ và khả năng mở rộng kiến thức. Với bản thân nghiên cứu đề tài sáng kiến kinh nghiệm là cơ hội tốt để nghiên cứu khoa học làm quen với phương pháp làm khoa học tuy chỉ trong phạm vi hẹp nhưng tôi hy vọng cùng với nổ lực của bản thân và sự giúp đỡ của đồng nghiệp sẽ có những đề tài khoa học tốt, lý thú và hiệu quả. Phạm vi đề tài Đề tài này được áp dụng đối với học sinh khá và giỏi với nhiệm vụ chủ yếu là ôn thi học sinh giỏi và bồi dưỡng kiến thức cho học sinh yêu thích môn tin. Phương pháp nghiên cứu Để hoàn thành đề tài này, tôi đã tiến hành áp dụng một số phương pháp nghiên cứu sau: Phương pháp đặt vấn đề - giải quyết vấn đề, Phương pháp phân tích tổng hợp,Phương pháp so sánh đối chiếu, Phương pháp thực nghiệm. GIẢI QUYẾT VẤN ĐỀ Lý thuyết Nhắc lại thuật toán Thuật toán tìm kiếm nhị phân liên quan đến bài toán sau: “ Cho mảng n phần tử đã được sắp tăng dần và một phần tử x. Tìm xem x có trong mảng hay không” Yêu cầu: Thuật toán này chỉ có thể được dùng khi dãy số được sắp xếp đơn điệu theo thứ tự tăng hoặc giảm dần. Tư tưởng của thuật toán: chọn phần tử ở vị trí giữa làm chốt, chia dãy thành 2 phần có kích thước nhỏ hơn. Sau đó so sánh phần tử cần tìm x với chốt, nếu x lớn hơn chốt tìm ở nửa sau của dãy, nếu x nhỏ hơn chốt tìm ở nửa trước của dãy [áp dụng với dãy tăng], quá trình trên tiếp tục cho tới khi tìm được x hoặc dãy chia không còn phần tử nào. Ví dụ: Cho dãy số: A={-6,1,3,5,8,10,14,16,19,21 }; x=5; dãy gồm 10 phần tử Gọi phần tử chốt là k, ban đầu k=8 Bước 1: k=8, so sánh x với k, xk ta tìm kiếm x ở nửa sau {3,5,8} Bước 3: k=5, so sánh x với k, x=k ta tìm được x kết thúc. Procedure TKNP [x: Item, a1,a2,...,an: Item]; Begin d := 1; {d là điểm đầu của đoạn tìm kiếm} c := n; {c là điểm cuối của đoạn tìm kiếm} tim_thay:=false; while [d