Giáo án môn Tin học 10 - Bài 4: Bài toán và thuật toán

<span class='text_page_counter'>(1)</span>Bµi 4: bµi to¸n vµ thuËt to¸n (tiÕt 6) Người soạn: Nguyễn Thị Huê SV líp: SP Tin K40 Ngµy so¹n: 25/9/2008 Giáo viên hướng dẫn: Nguyễn Văn Trường I. Mục đích – Yêu cầu - HiÓu vµ thùc hiÖn ®­îc thuËt to¸n t×m kiÕm nhÞ ph©n. - Biết cách xây dựng thuật toán đó. - Hình thành kĩ năng tư duy logic để giải quyết các bài toán và vấn đề trong thùc tÕ. II. C«ng t¸c chuÈn bÞ. Giáo viên chuẩn bị bảng phụ mô tả sơ đồ khối thuật toán tìm kiếm nhị phân. III. Néi dung 1. ổn định tổ chức lớp (1 phút) SÜ sè:. V¾ng:. Cã phÐp:. Kh«ng phÐp:. 2. KiÓm tra bµi cò. (6 phót) * C©u hái: Cho d·y sè nguyªn sau vµ kho¸ k= 27, em h·y thùc hiÖn thuËt toán tìm kiếm tuần tự và đưa ra kết quả dưới dạng mảng mô phỏng? D·y sè: 7, 5, 23, 27, 17, 32, 1 * §¸p ¸n: B¶ng m« pháng: A. 7. 5. 23 27 17. 32 1. i. 1. 2. 3. -. -. Ai = k Sai Sai Sai Sai §óng -. -. 4. 5. ?. -1Lop10.com.

<span class='text_page_counter'>(2)</span> KÕt qu¶ thùc hiÖn thuËt to¸n: Th«ng b¸o chØ sè cÇn t×m: i = 5. 3. Bµi míi Hoạt động của GV. Hoạt động của HS. Đặt vấn đề: Bài toán tìm kiếm rất phổ biÕn trong thùc tÕ. VÝ dô: t×m thuª bao trong danh b¹ ®iÖn tho¹i, t×m häc sinh trong danh s¸ch, … Ta còng cã thÓ t×m kiÕm theo nhiÒu c¸ch kh¸c nhau. ë tiÕt trước các em đã được tìm hiểu về thuật to¸n t×m kiÕm tuÇn tù, tiÕp theo chóng ta cïng t×m hiÓu mét thuËt to¸n t×m kiÕm n÷a: t×m kiÕm nhÞ ph©n. - C¸c em h·y më SGK trang 42.. Bµi 4: Bµi to¸n vµ thuËt to¸n.. Bµi to¸n ®­îc ph¸t biÓu nh­ sau:. (tiÕt 6). Bµi to¸n : “D·y A gåm N sè nguyªn 3. Mét sè vÝ dô vÒ thuËt to¸n. kh¸c nhau: a1,a2,…,aN ®­îc s¾p xÕp VÝ dô 3 (tiÕp): ThuËt tãn t×m t¨ng dÇn vµ sè nguyªn k. CÇn biÕt cã kiÕm nhÞ ph©n. hay kh«ng chØ sè i (1<=i<=N) mµ ai=k. Nếu có hãy cho biết chỉ số đó”. Em hãy xác định Input và Output của - Xác định: bµi to¸n?. + Input: D·y t¨ng gåm N sè nguyªn kh¸c nhau a1, a2,…, aN vµ sè nguyªn k; + Output: ChØ sè i mµ ai=k hoÆc th«ng b¸o kh«ng cã sè h¹ng nµo cña d·y cã gi¸ trÞ b»ng k;. - Em nµo cã thÓ m« t¶ ng¾n gän c¸ch - Tr¶ lêi më trang s¸ch cña m×nh?. -2Lop10.com. Thêi gian.

<span class='text_page_counter'>(3)</span> Ngoµi c¸ch nh­ trªn, ta còng cã thÓ lµm nh­ sau: Em më mét trang bÊt k× trong sách. Nếu trang đó đúng là trang 42 thì thôi. Nếu số trang đó nhỏ hơn 42 thì lại mở từ trang trước đó trở về đầu sách, ngược lại thì mở từ trang sau đó trở về cuối sách. - Với cách làm đó của em thì có thực - Trả lời: Cách đó không thể làm hiện được trên cuốn vở viết bình với quyển vở bình thường vì vở không đánh số trang.. thường không? - ViÖc t×m trang 42 còng gÇn gièng víi ý tưởng của thuật toán tìm kiếm nhị phân. Để xem ý tưởng đó thế nào, chóng ta sÏ cïng ®i t×m hiÓu. ý tưởng thuật toán tìm kiếm nhị phân. - Ghi bµi:. ®­îc ph¸t biÓu nh­ sau:. Sö dông tÝnh chÊt cña mét d·y sè t¨ng. Sö dông tÝnh chÊt d·y A t¨ng. Ta t×m c¸ch thu hÑp ph¹m vi t×m kiÕm So s¸nh aGiua víi k. Víi Giua  sau mçi lÇn so s¸nh kho¸ k víi phÇn tö [(Dau + Cuoi)/2]. Dau  1, tìm kiếm. Phần tử tìm kiếm thường Cuoi  N. ®­îc chän lµ phÇn tö ë gi÷a.. + NÕu aGiua = k th× Giua lµ chØ sè. Víi Giua=[(Dau+Cuoi)/2]; Dau vµ cÇn t×m, kÕt thóc t×m kiÕm. Cuoi là chỉ số tương ứng của phần tử + Nếu aGiua > k thì tìm kiếm tiếp ®Çu vµ cuèi d·y t×m kiÕm. Ban ®Çu trªn d·y a1, a2,…, aGiua-1 + NÕu aGiua < k th× t×m kiÕm tiÕp. khëi t¹o Dau=1, Cuoi=N.. + §Çu tiªn, ta xÐt phÇn tö ë gi÷a, so trªn d·y aGiua +1 , aGiua+2, …, aN + Qu¸ tr×nh kÕt thóc khi t×m thÊy. sánh với k. Nếu đúng bằng k thì dừng.. + NÕu phÇn tö gi÷a lín h¬n k, ta thùc chØ sè i sao cho ai = k hoÆc ph¹m hiÖn l¹i c«ng viÖc t×m kiÕm víi c¸c vi t×m kiÕm b»ng rçng. phần tử từ đầu đến phần tử gần phần tử. -3Lop10.com.

<span class='text_page_counter'>(4)</span> gi÷a nhÊt (t×m ë phÇn ®Çu cuèn s¸ch). + NÕu phÇn tö gi÷a nhá h¬n k th× thùc hiÖn l¹i viÖc t×m kiÕm víi c¸c phÇn tö từ phần tử ngay sau phần tử giữa đến phÇn tö cuèi (t×m ë phÇn sau cuèn s¸ch). + ViÖc t×m kiÕm sÏ dõng nÕu t×m thÊy phần tử k đó trong dãy hoặc phạm vi t×m kiÕm b»ng rçng (kh«ng cßn trang sách nào để tìm nữa). - ThuËt to¸n ®­îc gäi lµ “T×m kiÕm nhÞ ph©n” bëi ta thùc hiÖn viÖc t×m kiÕm b»ng c¸ch chia d·y t×m kiÕm thành 2 dãy con (nhị phân), sau đó lại t×m kiÕm trªn mét trong hai d·y con - Quan s¸t vµ ghi bµi.. đó nếu vẫn chưa tìm thấy.. - Từ ý tưởng ở trên, ta có cách biểu Bước 1: Nhập N, các phần tử a1, diÔn thuËt to¸n ë d¹ng liÖt kª nh­ sau:. a2,…, aN vµ kho¸ k;. (nêu lên các bước).. Bước 2: Dau1, CuoiN; Bước 3: Giua[(Dau+Cuoi)/2]; Bước 4: Nếu aGiua=k thì thông b¸o chØ sè Giua råi kÕt thóc; Bước. 5:. NÕu. aGiua>k. th×. CuoiGiua- 1, rồi chuyển đến bước 7; Bước 6: DauGiua+1; Bước 7: Nếu Dau>Cuoi thì th«ng b¸o d·y A kh«ng cã phµn tö nµo cã gi¸ trÞ b»ng k, råi kÕt -4Lop10.com.

<span class='text_page_counter'>(5)</span> thóc; Bước 8: Quay lại bước 3; - VD 1: N=7, k=5. D·y sè: 2, 4, 5, 21, i. 1. 2. 3. 4. 5. 6. 7. A. 2. 4. 5. 21. 43. 47. 52. Dau. 1. 1. 3.  1, vµ Cuoi lµ phÇn tö cuèi cïng:. Cuoi. 7. 3. 3. Cuoi  N (tøc Cuoi = 7).. Giua. 4. 2. 3. aGiua. 21. 4. 5. aGiua. >. <. =. 1. 2. 3. 43, 47, 52. + Chän Dau lµ phÇn tö ®Çu tiªn: Dau. + XÐt phÇn tö ë gi÷a: Giua  [(Dau+Cuoi)/2], tøc Giua = 4; ThÊy aGiua=21 > k = 5. Thùc hiÖn t×m kiÕm. vµ k LÇn duyÖt. trong nöa ®Çu cña d·y: CuoiGiua-1; tøc Cuoi=3; +. L¹i. Th«ng b¸o chØ sè cÇn t×m xÐt. phÇn. tö. gi÷a: i=Giua=3. Giua[(Dau+Cuoi)/2]; tøc Giua = 2; aGiua=4 < k = 5; Thùc hiÖn t×m kiÕm trong nöa sau cña d·y: DauGiua + 1; tøc Dau=3. +. XÐt. tiÕp. phÇn. tö. ë. gi÷a:. Giua[(Dau+Cuoi)/2]; tøc Giua = 3; aGiua=5 = k ; Th«ng b¸o ra chØ sè cÇn t×m i=Giua=3 råi kÕt thóc t×m kiÕm. - Đưa ra sơ đồ khối của thuật toán và - Quan sát sơ đồ của giáo viên. gi¶i thÝch. §ång thêi gi¶i thÝch sù tương đương giữa sơ đồ khối và các bước liệt kê. - NhËn xÐt: trong thuËt to¸n, viÖc t×m kiÕm thùc chÊt lµ lÆp mét sè lÇn thao t¸c: + Chän phÇn tö ë gi÷a lµm phÇn tö t×m kiÕm.. -5Lop10.com.

<span class='text_page_counter'>(6)</span> + So s¸nh phÇn tö t×m kiÕm víi k. + Căn cứ vào kết quả so sánh để thu hẹp phạm vi tìm kiếm hoặc kết luận đã t× thÊy (kh«ng t×m thÊy) NhËp N, a1, a2,…, aN vµ k. Dau1; CuoiN. Giua  [(Dau+Cuoi)/2]. §. aGiua = k S. §­a ra Giua råi kÕt thóc §. aGiua > k S DauGiua+1. S. Cuoi Giua-1. Dau>Cuoi §. Th«ng b¸o trong d·y kh«ng cã sè h¹ng nµo cã gi¸ trÞ b»ng k råi kÕt thóc. - Hướng dẫn HS tìm hiểu các VD.. - Nghe gi¶ng vµ ghi bµi.. - VD 2: N=8, k=23. D·y sè: 3, 5, 9, 12, 16, 17, 19, 24. B¶ng m« pháng nh­ sau (kÕt hîp víi. -6Lop10.com.

<span class='text_page_counter'>(7)</span> sơ đồ hoặc các bước liệt kê). i. 1. 2. 3. 4. 5. 6. 7. 8. A. 3. 5. 9. 12 16 17 19 24. Dau. 1. 5. 7. 8. 8. Cuoi. 8. 8. 8. 8. 7. Giua. 4. 6. 7. 8. aGiua. 12. 17 19 24. aGiua. <. <. <. >. 1. 2. 3. 4. vµ k LÇn duyÖt. NhËn thÊy r»ng: Dau>Cuoi nªn ph¹m vi t×m kiÕm b»ng rçng, th«ng b¸o: kh«ng t×m thÊy phÇn tö nµo b»ng 23 trong d·y. + VD 3: N=5, k=36. D·y sè: 9, 10, 29, 36, 42. HS tù lµm.. - Lµm VD.. GV nhËn xÐt bµi cña HS.. IV.. Cñng cè (1 phót). - So víi thuËt to¸n t×m kiÕm tuÇn tù, ë thuËt to¸n t×m kiÐm nhÞ ph©n cÇn l­u ý: + D·y sè ban ®Çu lµ d·y t¨ng. + Sè lÇn duyÖt Ýt h¬n. - BTVN: Học các cách biểu diễn bài toán tìm kiếm bằng liệt kê và bằng sơ đồ khối. Mỗi học sinh lấy 2 ví dụ về dãy tăng dần và khoá k, sau đó mô phỏng thuật to¸n t×m kiÕm nhÞ ph©n b»ng b¶ng.. -7Lop10.com.

<span class='text_page_counter'>(8)</span> V. nhận xét của giáo viên hướng dẫn:. ................................................................................................................................. ................................................................................................................................. ................................................................................................................................. ................................................................................................................................ ................................................................................................................................. ................................................................................................................................. ................................................................................................................................. ................................................................................................................................. .................................................................................................................................. -8Lop10.com.

<span class='text_page_counter'>(9)</span>