Bài giảng môn Tin 7 bài 4 sách Cánh diều: Sắp xếp nổi bọt

"Bài giảng môn Tin 7 bài 4 sách Cánh diều: Sắp xếp nổi bọt" được biên soạn với nội dung trình bày về: ý tưởng sắp xếp bằng cách đổi chỗ các phần tử liền kề; thuật toán sắp xếp nổi bọt; vận dụng kiến thức để giải các bài tập thực hành. Mời quý thầy cô và các em cùng tham khảo chi tiết tại đây.
Nội dung trích xuất từ tài liệu:
Bài giảng môn Tin 7 bài 4 sách Cánh diều: Sắp xếp nổi bọt BÀI4SẮPXẾPNỔIBỌT MỞĐẦU Làm thế nào để chomáytínhbiếtmộtdãyđãcóthứtựtăngdần?Đểmáytínhbiếtmộtdãyđãcóthứtựtăngdần,taphảisắpxếptheothứtựđểmáytínhcóthểnhậndạng. HOẠTĐỘNG 1 Giả sử có một dãy hộp kẹo, mỗi hộpchứa một số kẹo nào đó. Có một chú robotchỉbiếtlàmhaithaotác:SosánhsốkẹotronghaihộpcạnhnhauHoánđổivịtríhaihộpkẹocạnhnhau Theo em, chú robot phải làm thế nào đểxếplạicáchộpsaochosốkẹotrongcáchộptăngdần? Chúrobotphảisosánhlầnlượtcáchộpkẹocạnhnhauởtrongdãy,nếuhộpkẹothứnhấtlớnhơnhộpkẹothứhai thì tiến hành hoán đổi vị trí hai hộp kẹo cạnh nhau.Robot cứ thức hiện lần lượt cho đến khi không đổi chỗcáchộpkẹocạnhnhaunữathìkếtthúccôngviệc.1. Ý tưởng sắp xếp bằng cách đổi chỗ các phần tửliềnkề Ví dụ: Cho dãy 5 hộp kẹo với số lượng kẹo trong mỗi hộp khácnhau,tươngứnglà: 5 1 4 2 8Minhhọa:Giảithích:+ Ởlượtthứnhất,sosánhhaihộpđầutiên,nếusốkẹo ởhộpđứngtrướclớnhơnsốkẹp ởhộp đứngsauthì đổivịtríhaihộpnàychonhau. Tiếp tục như vậy cho đến hết dãy là hết một lượt => ta thuđượchộpcuốilàhộpchứanhiềukẹonhất+Tiếptụccáclượtthứhai,thứba theocáchtrên,cứlặplạinhưvậychođếnkhigặpmộtlượtmàsuốtcảlượt đórobotkhôngphảiđổichỗhaihộpnàothìdãyđãđượcsắpxếpxong. HOẠTĐỘNG 2 Vớidãysốđãchoởvídụtrên,emhãythựchiệnthuậttoánđượcmôtảởdướivàchobiếtđócóphảilàthuậttoánsắpxếpnổibọthaykhông?Lặpkhi(dãychưasắpxếpxong=đúng):a)Thựchiệnmột lượt sosánhcáccặpphầntửliềnkềvàđổichỗkhitráithứtựtăngdầnb)Nếutronglượtvừathựchiệnxongkhôngcóđổichỗ:dãychưasắpxếpxong=saiHếtnhánhHếtlặpThuậttoánđượcmôtảnhưhìnhtrênlàthuậttoánsắpxếpnổibọt.2.ThuậttoánsắpxếpnổibọtỞmỗilượtrobotthựchiệnXuấtpháttừđầudãy,i=1,xétcặp(a1,a2),nếua1>a2(tráithứtựmongmuốn)thìđổichỗchonhau;tráilạikhôngcầnlàmgì.Dịchsangphảimộtvịtrí,xétcặp(a2,a3);sosánhvàđổichỗnếucầnQuátrìnhtiếptục,dịchsangphảimộtvịtrí,xétcặp(ai+1,ai+2)sosánhvàđổichỗnếucần.Khihếtdãythìxongmộtlượtxétcáccặpsốkềnhauđểđổichỗ.Thựchiệnnhiềulượtnhưtrênchođếnkhikhôngcònbấtkìcặpliềnkề(ai,ai+1)nàotráithứtựmongmuốn,tađượcdãyđãsắpxếp. LUYỆNTẬPBài 1. Hãy mô phỏng thuật toán sắp xếp nổi bọt cho một dãy sốnguyên tùy chọn, không ít hơn 5 phần tử. Sau bao nhiêu lượt đi từđầu đến cuối dãy để so sánh và đổi chỗ thì thuật toán kết thúc?Tổngsốcóbaonhiêulầnđổichỗhaiphầntửliềnkề?GợiýVídụ:Chodãysố:15,1,31,9,78,42.Sau2lượtđitừđầuđếncuốidãyđểsosánhvàđổichỗthìthuậttoánkếtthúc.Có4lầnđổichỗhaiphầntừliềnkề.Bài2.1)Trongthuậttoánsắpxếpnổibọtthìdấuhiệuđểbiếtdãychưasắpxếpxonglàgì?2)Theoem,cóphảihìnhbênđãmôtảchitiếtmộtlượtrobotthựchiệnsosánhcáccặpphầntửliềnkềvàđổichỗkhichúngtráithứtựmongmuốnkhông?Lặpvớiitừ1đếnn–1:Nếuai>ai+1:đổichỗaichoai+1HếtnhánhHếtlặpBài3.Theoem,vìsaothuậttoánsắpxếptrênlạicótênlàsắpxếpnổibọt? VẬNDỤNGCâu1.Trongthuậttoánsắpxếpnổibọt,khinàohaiphầntửliềnkềđượcđổichỗ?Câu2.Thuậttoánsắpxếpnổibọtkếtthúckhinào?Câu 3. Khi nào thực hiện thuật toán sắp xếp nổi bọt chỉ cần mộtlượtsosánhcáccặpphầntửliềnkềvàđổichỗ? ...