Bài giảng môn Tin 7 bài 2 sách Cánh diều: Tìm kiếm nhị phân

"Bài giảng môn Tin 7 bài 2 sách Cánh diều: Tìm kiếm nhị phân" có nội dung về: chia đôi dần để tìm kiếm một số trong dãy số đã sắp thứ tự; Thuật toán tìm kiếm nhị phân; Phương pháp chia để trị với bài toán tìm kiếm;...Mời quý thầy cô cùng các em tham khảo chi tiết giáo án tại đây nhé.
Nội dung trích xuất từ tài liệu:
Bài giảng môn Tin 7 bài 2 sách Cánh diều: Tìm kiếm nhị phân BÀI2TÌMKIẾMNHỊPHÂN MỞĐẦU Nếuphảitìmmộtsốtrongdãyđãsắpxếptheo thứtựtăngdầnhoặcgiảmdần,emcócáchnào tìmnhanhhơntìmkiếm tuầntựkhông? HOẠTĐỘNGCó8thẻ,mỗithẻghimộtsốnguyêntrênđó.Tấtcảcácthẻđượcsắpxếpthànhdãytheothứtựkhônggiảmcủacácsốghitrênđóvàđặtsấpmặtghisốxuốngbànđểemkhôngnhìnthấy.Côgiáođọcmộtsố,gọilàXchẳnghạn.Cầntrảlờicâuhỏi:CóhaykhôngmộtthẻghisốX?Hãysửdụng ítnhấtsốlầnlậtmộtthẻlênxemmàvẫntrảlờiđượccâuhỏi.BạnThanhAnchorằngchỉcầnkhôngquá3 lần lật thẻ là trả lời được. Em đồng ý với Thanh An không? Vìsao?Câu trả lời: Đồng ý với ý kiến của bạn Thanh An vì chúng ta chỉ cầnchia đôi dần dãy số đã sắp thứ tự và lần lượt tìm kiếm trongphạm vi phù hợp để tìm ra kết quả mà chúng ta mong muốnthì chỉ cần 3 lần là có thể tìm ra kết quả.1.ChiađôidầnđểtìmkiếmmộtsốtrongdãysốđãsắpthứtựÝtưởng:chiađôidầnđểtìmmộtsốtrongmộtdãysốVídụ1: Tìmx=44trongdãy8phầntửđãsắpxếpthứtựkhônggiảmMinhhọacácbước: a1 a2 a3 a4 a5 a6 a7 a8 Xuấtphát 6 12 18 42 44 55 67 94 Bước1 42 44 55 67 94 Bước2 44 55 Bươc3 44 Môphỏngthuậttoántìmkiếmnhịphânx=44 a1 a2 a3 a4 a5 a6 a7 a8 a 6 12 18 42 44 44 55 67 94 i 1 2 3 4 5 6 7 8Lượtthứnhất:agiữalàa4=42;4244vùngtìmkiếmthuhẹptrongphạmvilàa5Lượtthứba:agiữalàa5=44;44=44=x Vậysốcầntìmlài=5.Vídụ2:Tìmx=21trongdãy10phầntửđãsắpxếpthứtựkhônggiảm A 2 4 5 6 9 21 22 30 31 33 i 1 2 3 4 5 6 7 8 9 10 Lượtthứnhất:agiữalàa5=9;921 vùngtìmkiếmthuhẹptrongphạmvitừa6a7; Lượtthứba:agiữalàa6=21;21=21 Vậysốcầntìmlài=6. 2.ThuậttoántìmkiếmnhịphânThuậttoántìmkiếmnhịphânlàthuậttoántìmkiếmxtrongdãyđãsắp thứ tự với ý tưởng chia đôi dần để giảm nhanh phạm vi tìmkiếm.Môtảthuậttoán:Bước1.PhạmvitìmkiếmlàdãybanđầuBước2.LặpkhivẫncònPhạmvitìmkiếma)XácđịnhphầntửamởgiữaPhạmvitìmkiếmb)Nếux=am:ThôngbáovịtrítìmthấyxởvịtrímKếtthúcthuậttoánTráilại:LoạibỏnửadãychắcchắnkhôngchứaxPhạmvitìmkiếm=nửadãycònlạiHếtnhánhHếtlặpBước3.(Đãhếtdãysốmàkhôngthấyx):Thôngbáokhôngcóxtrongdãy GhinhớThuật toán tìm kiếm nhị phân chỉ ápdụngđượcchodãyđãsắpthứtự TÌNHHUỐNG Emhãyquansát đoạnvideosauvàchobiếtýnghĩacủa câuchuyện? 3.PhươngphápchiađểtrịvớibàitoántìmkiếmĐểgiảimộtbàitoánlớn,ngườitatìmcáchchiabàitoánbanđầurathànhcácbàitoánnhỏhơnrồigiảinhữngbàitoánnhỏhơnsẽdễhơn.Cáchlàmnàygọilà“chiađểtrị”Thuậttoántìmkiếmnhịphânchiabàitoánbanđầuthànhhaibàitoánconnhỏhơnvàchỉphảitiếptụcgiảimộttronghaibàitoánconđó.Ápdụngliêntiếpcáchnàychođếnkhinhậnđượckếtquả. LUYỆNTẬPBài 1. Cho dãy số 5, 11, 18, 39, 41, 52, 63, 70. Hãy mô tả diễnbiếntừngbướctìmkiếmnhịphânđểtìmkiếmx=60trongdãytrên.Gợi ý: Có thể trình bày thông tin mô tả dưới dạng bảng nhưtrongbàihọcBài2.Emhãymôtảcáchtracứu,tìmgiảinghĩamộttừtrongtừđiển.Cóthểgọicáchtìmđólàápdụngthuậttoántìmkiếmnhịphânkhông? VẬNDỤNGCâu1.HãymôtảquytrìnhchiađôidầnđểthựchiệntìmkiếmnhịphânCâu1.Theoem,cóphảivớibấtcứdãysốnàocũngcóthểápdụngđượcthuậttoántìmkiếmnhịphânkhông?Giảithíchtạisao? ...