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>GA: Tin hoïc 10. Tieát 10, 11, 12, 13, 14. GV: Đàng Ngọc Huynh. Ngày soạn: 28/09/2006; ngày giảng: 02/10/2006; Lớp: 10 Baøi: §4. BAØI TOÁN VAØ THUẬT TOÁN Tieát PPCT: 10, 11, 112,13, 14 I. MUÏC TIEÂU BAØI HOÏC: 1. Kiến thức : -Hiểu khái niệm “bài toán” trong Tin học và biết 2 thành phần cơ bản của một bài toán (Input, Output). -Hiểu khái niệm “thuật toán” và 2 cách mô tả các thao tác trong thuật toán (liệt kê, sơ đồ khối). Nắm chắc các biểu tượng thể hiện các thao tác trong sơ đồ khối. -Hiểu được khái niệm sơ lược ban đầu về “ngôn ngữ lập trình”. -Nắm được các thuật ngữ chính trong bài. -Qua bài học, HS hình dung rõ hơn một bước nữa về cách thức hoạt động của máy tính. 2. Kyõ naêng : -Biết cho ví dụ một số bài toán trong Tin học. -Xác định được Input và Output của các bài toán. -Mô tả được các thao tác trong thuật toán của một số bài toán cụ thể bằng 2 cách: liệt kê và dùng sơ đồ khối. 3. Thái độ : Nghiêm túc, cẩn thận, đoàn kết, có tinh thần giúp đỡ nhau trong xây dựng bài học. II. CHUAÅN BÒ: 1. Taøi lieäu, baøi taäp: 2. Duïng cuï, thieát bò: III. TIẾN TRÌNH LÊN LỚP: 1. Ổn định, tổ chức lớp: 2. Kieåm tra baøi cuõ: Caâu hoûi: Đáp án: 1/ -Khaùi nieäm heä thoáng tin hoïc? 1/ (SGK). -Caùc thaønh phaàn cuûa moät heä thoáng tin hoïc? 2/ -CPU laø gì? 2/ (SGK). -Keå teân moät soá thieát bò vaøo?. Lop10.com. Trang 1.

<span class='text_page_counter'>(2)</span> GA: Tin hoïc 10. Tieát 10, 11, 12, 13, 14. GV: Đàng Ngọc Huynh. 3. Baøi giaûng: Hoạt động của Thầy và Trò GV: (ĐVĐ) Để viết được chương trình cho máy tính thực hiện ta cần biết thế nào là bài toán và thuật toán. Hôm nay ta sang baøi 4. Hoạt động 1: -Nội dung: Khái niệm bài toán. -Mục tiêu: HS nắm được khái niệm bài toán. -Caùch tieán haønh: +GV: Trong Toán học ta nhắc nhiều đến khái niệm “bài toán” và ta hiểu đó là những việc mà con người cần phải thực hiện sao cho từ những dữ kiện đã có phải tìm ra hay chứng minh một kết quả nào đó. Vậy khái niệm “bài toán” trong Tin học có gì khác không? Để khẳng định cho vấn đề này, chúng ta xét các yêu cầu sau. +HS: Thaûo luaän caùc yeâu caàu treân baûng.. Noäi dung ghi baûng. §4. BAØI TOÁN VAØ THUẬT TOÁN I/ BAØI TOÁN: 1/ Khái niệm bài toán:. *Xeùt caùc yeâu caàu sau: 1)Giaûi phöông trình baäc hai ax2 + bx + c = 0; 2)Viết 1 dòng chữ ra màn hình máy tính; 3)Tìm giaù trò nhoû nhaát cuûa caùc soá trong moät daõy soá. 4)Tìm ÖCLN cuûa 2 soá nguyeân döông a vaø b; 5)Xếp loại học tập các HS trong lớp. 6)Quaûn lyù caùc caùn boä trong 1 cô quan;. +GV: Trong caùc yeâu caàu treân, yeâu caàu nào được xem như là một bài toán? →Yêu cầu nào được xem như là một bài *Trong phạm vi Toán học? toán? *Trong phaïm vi Tin hoïc? *Keát quaû: +HS: Ñöa ra keàt quaû. -Trong phạm vi Toán học: Yêu cầu 1) và 4) được xem là bài +GV: Nhaän xeùt keát quaû. toán. -Trong phaïm vi Tin hoïc: Tất cả các yêu cầu trên được xem là bài toán.. Lop10.com. Trang 2.

<span class='text_page_counter'>(3)</span> GA: Tin hoïc 10. Tieát 10, 11, 12, 13, 14. GV: Đàng Ngọc Huynh. +GV: Từ kết quả trên, em nào có thể đưa ra khái niệm “bài toán” trong Tin hoïc. *Keát luaän: Trong phạm vi Tin học, bài toán là một việc nào đó ta muốn máy tính thực hiện.. +HS: nêu khái niệm bài toán.. 2. Caùc thaønh phaàn cô baûn cuûa moät baøi toán : Hoạt động 2 : -Noäi dung: Tìm hieåu caùc yeáu toá cô baûn của một bài toán. -Mục tiêu: Giúp HS nắm được 2 yếu tố cơ bản (Input, Output) của một bài toán. * Vấn đề thảo luận: -Caùch tieán haønh: Caùc yếu tố cần quan taâm khi giải một +GV: Ghi vấn đề lên bảng. bài toán trong Toán học? +HS thảo luận vấn đề trên bảng. -Giả thiết (cái đã biết) -Keát luaän (caùi caàn tìm) +GV: Để giải 1 bài toán công việc đầu Trong Tin học : tieân chuùng ta phaûi laøm gì? -Giả thiết Input (Các thông tin đã có) +HS: Trà lời. (xác định đâu là dữ kiện (Đầu vào: Các T.tin đưa vào máy) đã cho và đâu là cái cần tìm). -Keát luaän  Output (Caùc t. tin caàn tìm) (Đầu ra: Các t.tin cần lấy ra từ +GV: Nhận xét câu trả lời của HS, đưa máy) ra kết luận và giới thiệu 2 thành phần *Kết luận : tuơng ứng của một bài toán trong Tin hoïc. Các bài toán được cấu tạo bởi hai yeáu toá cô baûn : -Input : Các thông tin đã có (Caùc giaû thieát) -Output : Caùc thoâng tin caàn tìm (Keát luaän). Lop10.com. Trang 3.

<span class='text_page_counter'>(4)</span> GA: Tin hoïc 10. Tieát 10, 11, 12, 13, 14. GV: Đàng Ngọc Huynh. +GV: Hướng dẫn học sinh tìm Input và Ouput của một số bài toán thông qua các 3. Các ví dụ : Tìm input và output của ví duï. bài toán VD1: Giải phương trình bậc hai ax2+bx+c =0 (a ≠ 0). -Input : Caùc số thực a,b,c (a ≠ 0) -Output : Số thực x thỏa : ax2+bx+c = 0 +HS: Theo dõi sự hướng dẫn của GV và áp dụng giải quyết các bài toán còn VD2: Tìm giaù trò nhoû nhaát cuûa caùc soá laïi. trong moät daõy soá. -Input : Caùc soá trong daõy soá. -Output : Giá trị lớn nhất trong dãy số. VD3: Tìm ước chung lớn nhất của hai số nguyeân dương a vaø b. -Input: Hai số nguyeân dương avaø b. -Output: Ước chung lớn nhất của a vaø b. VD4: Xếp loại học tập caùc học sinh trong lớp. -Input : Bảng đñiểm của học sinh. -Output :Bảng xếp loại học tập cuûa hoïc +GV: Qua các VD trên ta thấy bài toán sinh. được cấu tạo bởi hai yếu tố cơ bản, đó là: VD5: Viết 1 dòng chữ ra màn hình máy tính. *input: Các thông tin đã có. * Output : Các thông tin cần tìm. -Input: Các kí tự. -Output: Một dòng chữ.. Lop10.com. Trang 4.

<span class='text_page_counter'>(5)</span> GA: Tin hoïc 10. Tieát 10, 11, 12, 13, 14. GV: Đàng Ngọc Huynh. Hoạt động 3 : -Nội dung: Khái niệm thuật toán. -Mục tiêu: Giúp HS hiểu và nắm được II. THUẬT TOÁN khái niệm thuật toán. 1. Khái niệm thuật toán: -Caùch tieán haønh: +GV: (ĐVĐ) Chúng ta đã biết khái *Sơ đồ: niện về “bài toán” và các yếu tố cơ bản Bài toán của một bài toán đó là: input, output. Để tìm được output từ input của bài toán, ta Bằng cách nào? Output Input laøm baèng caùch naøo? Hoâm nay chuùng ta (GT) (KL) sang phần tiếp theo. (II. Thuật toán) Giải bài toán. Thuật toán. +GV: Trình bày khái niệm thuật toán thông qua sơ đồ. Hướng dẫn các thao tác cho máy thực hiện để tìm ra lời giải +HS: Lắng nghe và quan sát sơ đồ treân baûng. +GV: Muốn tìm ra kết luận từ giả thiết của bài toán, thì chúng ta phải làm Noùi caùch khaùc : gì? BÀI TOÁN +HS: Đứng tại chỗ trả. (Giải bài toán). THUẬT TOÁN Input. +GV: Yêu cầu HS dựa vào sơ đồ đó phác thảo khái niệm “thuật toán”.. (Thao tác 1Thao tác 2...Thao tác n). Output. *Keát luaän: +HS: Trình bày theo cách hiểu của Thuật toán để giải một bài toán là: baûn thaân. - Một daõy hữu hạn caùc thao taùc. - Caùc thao taùc naøy ñược sắp xếp theo một trình tự xaùc ñịnh. +GV: Nhaän xeùt vaø ñöa ra keát luaän. - Sao cho sau khi thực hiện daõy thao tác đó, từ Input của bài toán ta nhận ñược Output cần tìm.. Lop10.com. Trang 5.

<span class='text_page_counter'>(6)</span> GA: Tin hoïc 10. Tieát 10, 11, 12, 13, 14. Hoạt động 4 : -Noäi dung: Moâ taû caùc thao taùc trong thuật toán. -Mục tiêu : Giúp HS biết được 2 cách mô tả thuật toán: liệt kê và dùng sơ đồ khối. -Caùch tieán haønh: + GV: Đưa ra bài toán giải “Tìm giá trị lớn nhất của dãy số nguyên” và yêu cầu HS xaùc ñònh caùc yeáu toá cô baûn cuûa baøi toán: Input và Output.. GV: Đàng Ngọc Huynh. 2. Mô tả các thao tác trong thuật toán: Coù 2 caùch : Liệt kê và dùng sơ đồ khối. Bài toán : “Tìm giá trị lớn nhất của dãy soá nguyeân”. *Xác định bài toán: -Input: Soá nguyeân döông N vaø daõy N soá nguyeân döông a1, a2, . . . , aN. +GV: Trong Toán học sau bước xác -Output: Giá trị lớn nhất Max của dãy định yêu cầu bài toán, bước kế tiếp số. chuùng ta phaûi laøm coâng vieäc gì? +HS: Trả lời (xác định hướng hay *Ý tưởng: phöông phaùp giaûi) -Khởi tạo giá trị Max = a1; +GV: Đó là ý tưởng của bài toán. -Lần lượt với i từ 2 đến N, so sánh số hạng ai với giá trị Max, nếu ai > Max thì +GV: sau bước xác định yêu cầu bài Max nhận giá trị mới là ai. toán và phương pháp giải, công việc còn lại chúng ta phải làm gì để tìm ra kết *Thuật toán: luận từ giả thiết của bài toán? a. Moâ taû theo caùch lieät keâ: +HS: Trả lời (Giải bài toán). (Nêu ra tuần tự các thao tác cần tiến +GV: Nhaän xeùt vaø giaûi thích: “Giaûi baøi haønh). toán”là trong Toán học, còn trong Tin học gọi là “Thuật toán”. Bước 1: Nhập N và dãy a1, a2, . . . , aN; Từ đó, GV hướng dẫn HS cách Bước 2: Max  a1 ; i  2; chuyển từ ý tưởng của bài toán này sang Bước 3: Nếu i > N thì đưa ra kết quả và mô tả thuật toán bằng cách liệt kê. kết thúc; ngược lại thì sang Bước 4; + HS: Lắng nghe và hiểu được các bước Bước 4: mô tả thuật toán. 4.1: Neáu ai > Max thì Max  ai ;. Lop10.com. Trang 6.

<span class='text_page_counter'>(7)</span> GA: Tin hoïc 10. Tieát 10, 11, 12, 13, 14. GV: Đàng Ngọc Huynh. 4.2: i  i + 1 rồi quay lại Bước 3.. +GV: Ngoài cách liệt kê các thao tác b. Biểu diễn bằng sơ đồ khối: như trên, ta có thể dùng sơ đồ khối để mô Trong sơ đồ khối ta qui ước: tả thuật toán. -Hình oâ van : theå hieän thao taùc +GV: Ghi các qui ước trong sơ đồ lên nhập, xuất dữ liệu; baûng.. Lop10.com. Trang 7.

<span class='text_page_counter'>(8)</span> GA: Tin hoïc 10. GV: Đàng Ngọc Huynh. Tieát 10, 11, 12, 13, 14. (Đặc biệt yêu cầu HS học thuộc tại lớp -Hình thoi các biểu tượng thể hiện các thao tác trong sánh; -Hình chữ nhật sơ đồ khối).. : theå hieän thao taùc so : theå hieän pheùp tính toán; : qui định trình tự thực hieän caùc thao taùc.. -Caùc muõi teân +GV: Lấy lại VD: Bài toán “Tìm giá trị lớn nhất của dãy số nguyên”. VD: Bài toán “Tìm giá trị lớn nhất của dãy số nguyên” ở trên được mô tả bằng +GV: Hướng dẫn HS chuyển từng bước sơ đồ khối như sau: NhËp N vµ d·y a ,..., a trong mô tả thuật toán theo cách liệt kê sang cách mô tả thuật toán bằng sơ đồ khối tương ứng. Max  a , i  2 1. N. 1. §óng. i>N. §­a ra Max råi kÕt thóc. Sai. Sai. aii > Max. §óng Max  a i. +HS: Phân biệt được điểm giống và khác nhau giữa 2 cách mô tả này. Thuộc lòng tại lớp ý nghĩa các biểu tượng trong sơ đồ khối.. ii+1. *Ghi chuù: -Mũi tên  hiểu là gán giá trị của biểu thức bên phải mũi tên cho biến ở bên trái mũi teân; -VD: i  i + 1: Đặt cho biến I giá trị mới bằng giá trị trước đó tăng thêm 1 đơn vị.. 3. Tính chất của thuật toán:. Lop10.com. Trang 8.

<span class='text_page_counter'>(9)</span> GA: Tin hoïc 10. Tieát 10, 11, 12, 13, 14. GV: Đàng Ngọc Huynh. +GV: Thông qua Khái niệm thuật toán -Tính dừng: và VD trên, nêu tính chất của thuật toán Thuật toán phải kết thúc sau 1 số hữu và giải thích và đưa ra VD từng tính chất. hạn lần thực hiện thao tác. -Tính xaùc ñònh: +HS: Chuù yù theo doõi vaø ghi cheùp. Sau khi thực hiện 1 thao tác thì hoặc lá thuật toán kết thúc hoặc là có đúng 1 thao tác xác định để được thực hiện tiếp theo. -Tính đúng đắn: Sau khi thuật toán kết thúc, ta nhận đượ Output cần tìm. VD: Với thuật toán tìm Max đã xét: -TÝnh dõng: V× gi¸ trÞ cña i mçi lÇn t¨ng lªn 1 nªn sau N lần thì i > N, khi đó kết quả phép so sánh ở bước 3 xác định việc đưa ra giá trị Max råi kÕt thóc. -Tính xác định: Thứ tự thực hiện các bước của thuật toán được mặc định là tuần tự nên sau bước 1 là bước 2, sau bước 2 là bước 3. Kết quả các phép so sánh trong bước 3 và bước 4 đều xác định duy nhất bước tiếp theo cÇn thùc hiÖn. -Tính đúng đắn: V× thuËt to¸n so s¸nh Max víi tõng sè h¹ng cña d·y sè vµ thùc hiÖn Max  ai nÕu ai > Max nªn sau khi so s¸nh hÕt N sè h¹ng cña d·y th× Max lµ gi¸ trÞ lín nhÊt.. + GV: Đưa ra bài toán giải phương. Lop10.com. Trang 9.

<span class='text_page_counter'>(10)</span> GA: Tin hoïc 10. GV: Đàng Ngọc Huynh. Tieát 10, 11, 12, 13, 14. trình baäc nhaát vaø yeâu caàu HS trình baøy VD : Tìm nghiệm phương trình bậc nhất lời giải theo cách thông thường. tổng quaùt : ax + b = 0. +Từ đó, GV hướng dẫn HS cách chuyển từ lời giải thông thường này sang 2 cách liệt kê và dùng sơ đồ khối (Đặc biệt yêu cầu HS học thuộc tại lớp các biểu tượng thể hiện các thao tác trong sơ đồ khối).. a. Baèng caùch lieät keâ: -Bước 1 : Nhập a, b. -Bước 2 : Nếu a ≠ 0 thì thực hiện bước 3, nếu khoâng thì quay lại bước 1. -Bước 3 : Gaùn cho x giaù trị -b/a. -Bước 4 : Đưa ra kết quả x vaø kết thuùc. b.Bằng sơ đồ khối:. + HS: Lắng nghe và hiểu được 2 cách mô tả thuật toán. Phân biệt được điểm giống và khác nhau giữa 2 cách mô tả này. Thuộc lòng tại lớp ý nghĩa các biểu tượng trong sơ đồ khối.. Nhaäp a, b. a <> 0. Sai. Đúng x  -b/a. +GV: Giải thích để học sinh có được cảm nhận ban đầu về chương trình và ngôn ngữ lập trình.. Ñöa ra x roài keát thuùc. +HS: Có được khái niệm ban đầu về * Löu yù: ngôn ngữ lập trình và chương trình. Ta cần diễn tả thuật toán bằng một ngôn ngữ sao cho máy tính có thể hiểu và thực hiện được, ngôn ngữ đó gọi là ngôn ngữ lập trình. Kết quả diễn tả thuật toán như vậy gọi là một chương trình.. Lop10.com. Trang 10.

<span class='text_page_counter'>(11)</span> GA: Tin hoïc 10. Tieát 10, 11, 12, 13, 14. Hoạt động 5 : -Nội dung: Xét các ví dụ về thuật toán -Mục tiêu : Giúp HS vận dụng những kiến thức có được trong hoạt động 4 vào một số bài toán cụ thể -Caùch tieán haønh : +GV: Hướng dẫn các bước thực hiện bài toán trong VD.. GV: Đàng Ngọc Huynh. III. CÁC VÍ DỤ VỀ THUẬT TOÁN: VD 1: KiÓm tra tÝnh nguyªn tè cña mét sè nguyên dương. *Xác định bài toán - Input: N là một số nguyên dương; -Output: "N lµ sè nguyªn tè" hoÆc "N kh«ng lµ sè nguyªn tè". *ý tưởng: Ta nhớ lại định nghĩa: Một số nguyên dương N là số nguyên tố nếu nó có đúng hai ước số khác nhau là 1 và chính nó. +HS: Theo doừi sửù hửụựng daón cuỷa giaựo Từ định nghĩa đó, ta suy ra: vieân. -NÕu N = 1 th× N kh«ng lµ sè nguyªn tè; -NÕu 1 < N < 4 th× N lµ sè nguyªn tè; -NÕu N 4 vµ kh«ng cã ­íc sè trong ph¹m vi từ 2 đến phần nguyên căn bậc hai của N thì N lµ sè nguyªn tè. Từ đó ta có thuật toán như sau: *ThuËt to¸n a) ThuËt to¸n diÔn t¶ b»ng c¸ch liÖt kª Bửụực1: Nhập số nguyên dương N; Bước2: NÕu N = 1 th× th«ng b¸o N kh«ng nguyªn tè råi kÕt thóc; Bước3: NÕu N < 4 th× th«ng b¸o N lµ nguyªn tè råi kÕt thóc;. Bước4: i ← 2; Ghi chó: Bước5: NÕu i > [ N ]* th× th«ng b¸o N lµ -Biến i nhận giá trị nguyên thay đổi trong phạm vi từ 2 đến  N  + 1 và dùng nguyên tố rồi kết thúc; để kiểm tra N có chia hết cho i hay Bửụực6: Nếu N chia hết cho i thì thông báo N kh«ng nguyªn tè råi kÕt thóc; kh«ng. -[x] kí hiệu phần nguyên của x, là số Bửụực7: i ← i + 1 rồi quay lại bước 5. nguyªn kh«ng lín h¬n x vµ gÇn x nhÊt.. Lop10.com. Trang 11.

<span class='text_page_counter'>(12)</span> GA: Tin hoïc 10. GV: Đàng Ngọc Huynh. Tieát 10, 11, 12, 13, 14. b) Sơ đồ khối: Kiểm tra tính nguyên tố NhËp N. §óng. N=1 Sai §óng N<4 Sai. i2. i>  N   . §óng. Th«ng b¸o N lµ sè nguyªn tè råi kÕt thóc. Sai. ii+1. Sai. §óng. Th«ng b¸o N kh«ng lµ sè nguyªn tè råi kÕt thóc. i N/i Chia hÕt kh«ng?. N chia hÕt cho i. Dưới đây là ví dụ mô phỏng các bước thực KiÓm tra tÝnh nguyªn tè. Víi N = 29 (  29   5 ) Víi N = 45 (  45   6 ) 2 3 4 5 6 2 3 i 29/2 29/3 29/4 29/5 45/2 45/3 N/i Chia hÕt Kh«ng Chia hÕt Kh«ng Kh«ng Kh«ng Kh«ng kh«ng? a) 29 lµ sè nguyªn tè b) 45 kh«ng lµ sè nguyªn tè. Lop10.com. Trang 12.

<span class='text_page_counter'>(13)</span> GA: Tin hoïc 10. GV: Đàng Ngọc Huynh. Tieát 10, 11, 12, 13, 14. +GV: Trong cuộc sống, ta thường gặp những việc liên quan đến sắp xếp chaỳng haùn nhử: Danh sách häc sinh của lớp 10C được xếp theo thứ tự từ A đến Z (thứ tự ABC); XÕp lo¹i häc lùc häc sinh trong líp;... Nãi mét c¸ch tæng qu¸t, cho mét d·y đối tượng, cần sắp xếp lại vị trí các đối tượng theo một tiêu chí nào đó. VD: Cho 10 chiÕc cäc cã chiÒu cao kh¸c VÝ dô 2. Bµi to¸n s¾p xÕp nhau (hình a), cÇn xÕp l¹i sao cho cäc thÊp ë Cho d·y A gåm N sè nguyªn a1, a2,..., aN. CÇn s¾p xếp các số hạng để dãy A trở thành dãy không trước, cọc cao ở sau (hỡnh b). giảm (tức là số hạng trước không lớn hơn số hạng sau).. a) D÷ liÖu gèc. b) Sau khi s¾p xÕp. Thuật toán Sắp xếp bằng tráo đổi (Exchange Sort). *Xác định bài toán - Input: D·y A gåm N sè nguyªn a1, a2,..., aN. - Output: D·y A ®­îc s¾p xÕp l¹i thµnh d·y kh«ng gi¶m. *YÙ tưởng: Với mỗi cặp số hạng đứng liền kề trong dãy, +GV Giụựi thieọu sụ qua PP Saộp xeỏp: Saộp xeỏp nếu số trước lớn hơn số sau ta đổi chỗ chúng cho ủửụùc chia laứm 2 loaùi ủoự laứ: SX trong vaứ SX nhau. Việc đó được lặp lại, cho đến khi không có sự đổi chỗ nào xảy ra nữa. ngoài. *ThuËt to¸n *Saép xeáp TRONG: a) C¸ch liÖt kª: → +Phöông phaùp Choïn (Selection Sort); Bước 1. Nhập N, các số hạng a1, a2,..., aN; + PP Đổi chỗ (Exchange Sort); Bước 2. M ← N; + PP Cheøn (Insertion Sort ). Bước 3. Nếu M < 2 thì đưa ra dãy A đã *Sắp xếp NGOAØI: ®­îc s¾p xÕp råi kÕt thóc; → PP Trộn tự nhiên (Natural Merge Bước 4. M ← M - 1, i ← 0; Sort). Trong phaïm vi SGK chuùng ta chæ hoïc thuaät Bước 5. i ← i + 1; toán sắp xếp bằng PP Đổi chỗ hay còn gọi là Bước 6. Nếu i > M thì quay lại bước 3; tráo đổi (Exchange Sort). Bước 7. Nếu a > a thì tráo đổi a và a VD: Víi A lµ d·y gåm N sè nguyªn ( N = 10): 6, 1, 5, 3, 7, 8, 10, 7, 12, 4, Sau khi s¾p xÕp ta cã d·y: 1, 3, 4, 5, 6, 7, 7, 8, 10, 12.. +GV: Hướng dẫn các bước thực hiện bài toán trong VD.. +HS: Theo dõi sự hướng dẫn của giáo vieân.. Lop10.com. i. i+1. i. i+1. cho nhau; Bước 8. Quay lại bước 5.. Trang 13.

<span class='text_page_counter'>(14)</span> GA: Tin hoïc 10. GV: Đàng Ngọc Huynh. Tieát 10, 11, 12, 13, 14. +GV: Ta thấy rằng, sau mỗi lần đổi chỗ, giá trị lín nhÊt cña d·y A sÏ ®­îc chuyÓn dÇn vÒ cuèi dãy và sau lượt thứ nhất thì giá trị lớn nhất xếp đúng vị trí là ở cuối dãy. Tương tự, sau lượt thứ hai, giá trị lớn thứ hai được xếp đúng ở vị trí sát cuối,... Có thể hình dung, sau mỗi lượt có ít nhất một số hạng đã xếp đúng vị trí và không còn tham gia vào quá trình đổi chỗ nữa, giống như các bọt nước từ đáy hồ nổi dần và khi đã lên mặt nước rồi thì tan biến. Có thể vì thế mà sắp xếp bằng tráo đổi còn có tên gọi là sắp xếp nổi bọt (Bubble Sort).. Ghi chó: - Qua nhËn xÐt trªn, ta thÊy qu¸ tr×nh so s¸nh và đổi chỗ sau mỗi lượt chỉ thực hiện với dãy đã bỏ bớt số hạng cuối dãy. Để thực hiện điều đó trong thuËt to¸n sö dông biÕn nguyªn M cã gi¸ trÞ khởi tạo là N, sau mỗi lượt M giảm một đơn vị cho đến khi M < 2. - Trong thuËt to¸n trªn, i lµ biÕn chØ sè c¸c số hạng của dãy có giá trị nguyên thay đổi lần lượt từ 0 đến M + 1. b) Sơ đồ khối: NhËp N vµ a1, a2,..., aN MN M<2?. §óng. §­a ra A råi kÕt thóc. Sai M  M – 1; i  0 ii+1 §óng. i>M? Sai. Tráo đổi ai và ai+1. §óng. ai > ai+1 ? Sai. Dưới đây là ví dụ mô phỏng các bước thực hiện của Thuật toán Sắp xếp bằng tráo đổi (Exchange Sort). D·y A 6 1 5 3 7 8 10 7 12 Lượt 1 1 5 3 6 7 8 7 10 4 Lượt 2 1 3 5 6 7 7 8 4 10 Lượt 3 1 3 5 6 7 7 4 8 Lượt 4 1 3 5 6 7 4 7 Lượt 5 1 3 5 6 4 7 Lượt 6 1 3 5 4 6 Lượt 7 1 3 4 5 Lượt 8 1 3 4 Lượt 9 1 3 Lượt 10 1. Lop10.com. 4 12. Trang 14.

<span class='text_page_counter'>(15)</span> GA: Tin hoïc 10. GV: Đàng Ngọc Huynh. Tieát 10, 11, 12, 13, 14. -GV: Tìm kiếm là việc thường làm của mỗi người, ch¼ng h¹n t×m cuèn s¸ch gi¸o khoa Tin häc 10 trên giá sách để chuẩn bị cho giờ học ngày hôm sau, cần tìm một HS trong danh sách một lớp… Nói một cách tổng quát là cần tìm một đối tượng cụ thể nào đó trong tập các đối tượng cho trước. -GV: Sè nguyªn k ®­îc gäi lµ kho¸ t×m kiÕm (gäi t¾t lµ kho¸). VD: cho d·y A gåm c¸c sè: 5, 7, 1, 4, 2, 9, 8, 11, 25, 51. +Víi kho¸ k = 2, trong d·y trªn cã sè h¹ng a5 cã gi¸ trÞ b»ng k. VËy chØ sè cÇn t×m lµ i = 5. +Víi kho¸ k = 6 th× kh«ng cã sè h¹ng nµo cña d·y A cã gi¸ trÞ b»ng k.. -GV: Hướng dẫn các bước thực hiện bài toán và mô tả thuật toán bằng liệt kê. -HS: Chú ý theo dõi sự hướng dẫn của giáo vieân.. VÝ dô 3. Bµi to¸n t×m kiÕm: Cho dãy A gồm N số nguyên, đôi một khác nhau: a1, a2,..., aN vµ mét sè nguyªn k. CÇn biÕt cã hay kh«ng chØ sè i ( 1  i  N ) mµ ai = k. NÕu cã hãy cho biết chỉ số đó. A.ThuËt to¸n T×m kiÕm tuÇn tù (Sequential Search) *Xác định bài toán - Input: Dãy A gồm N số nguyên đôi một 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 A cã gi¸ trÞ b»ng k. *YÙ tưởng: Lần lượt từ số hạng thứ nhất, ta so sánh giá trị số hạng đang xét với khoá cho đến khi hoÆc gÆp mét sè h¹ng b»ng kho¸ (Tìm thaáy) hoặc dãy đã được xét hết và không có giá trị nµo b»ng kho¸ (Khoâng tìm thaáy). *ThuËt to¸n a) C¸ch liÖt kª Bước 1. Nhập N, các số hạng a1, a2,..., aN và kho¸ k; Bước 2. i ← 1; Bước 3. Nếu ai = k thì thông báo chỉ số i, rồi. kÕt thóc; Bước 4. i ← i + 1; Bước 5. Nếu i > N thì thông báo dãy A không. cã sè h¹ng nµo cã gi¸ trÞ b»ng k, råi kÕt thóc; Bước 6. Quay lại bước 3.. Ghi chó: Trong thuËt to¸n trªn, i lµ biÕn chØ sè c¸c sè h¹ng cña d·y vµ nhËn gi¸ trÞ nguyªn lÇn -GV: Goùi 1HS leõn baỷng moõ taỷ thuaọt toaựn baống lượt từ 1 đến N + 1. sơ đồ khối. -GV cùng Lớp nhận xét và sửa sai (nếu có).. Lop10.com. Trang 15.

<span class='text_page_counter'>(16)</span> GA: Tin hoïc 10. GV: Đàng Ngọc Huynh. Tieát 10, 11, 12, 13, 14. b) Sơ đồ khối NhËp N vµ a1, a2,..., aN; k. i. 1. §óng ai = k. §­a ra i råi kÕt thóc. Sai. i. i+1. Sai i>N. §óng. Th«ng b¸o d·y A kh«ng cã sè h¹ng cã gi¸ trÞ b»ng k råi kÕt thóc. Dưới đây là VD mô phỏng các bước thực hiện của ThuËt to¸n T×m kiÕm tuÇn tù (Sequential Search) k = 2 vµ N = 10 A 5 7 1 4 2 9 8 11 25 51 i 1 2 3 4 5 - - - - Víi i = 5 th× a5 = 2.. Lop10.com. k = 6 vµ N = 10 A 5 7 1 4 2 9 8 11 25 51 i 1 2 3 4 5 6 7 8 9 10 11 Với mọi i từ 1 đến 10 không có ai có gi¸ trÞ b»ng 6.. Trang 16.

<span class='text_page_counter'>(17)</span> GA: Tin hoïc 10. GV: Đàng Ngọc Huynh. Tieát 10, 11, 12, 13, 14. GV: Bài toán tìm kiếm ngoài thuật toán tìm kieám nhò phaân, ta coù theå duøng thuaät toán tìm kiếm nhị phân để thực hiện việc tìm kiếm, nhưng với điều kiện dãy A phải được sắp xếp theo thứ tự tăng (hoặc giaûm) VD: Cho daõy A goàm N = 6 nhö sau: i. 1. 2. 3. 4. 5. 6. ai. 2. 4. 5. 7. 8. 9. vaø moät soá nguyeân k = 7 -GV: Để thu hẹp lại phạm vi tìm kiếm, ta chia daõy A thaønh 2 phaàn coù theå hôn keùm nhau đúng 1 số hạng, số hạng nằm giữa 2 phaàn naøy ta goïi laø: aGiua . Muoán bieát aGiua cuï theå laø a? thì ta ñi tìm chæ soá Giua baèng chæ soá i (1 ≤ i ≤ N) naøo ? Ta tìm chæ soá Giua baøng caùch:  Dau  Cuoi  1  N  Giua =   =  2  2  1  6  =  = 3,5 => Giua = 3  2  => aGiua = a3 = 5. Cuoái cuøng ta so saùnh aGiua(aGiua = a3 = 5) vụựi khoaự k(k = 7). Khi đó, chỉ xảy ra một trong ba trường hợp sau: aGiua = k aGiua > k aGiua < k => aGiua = a3 = 5 < khoá k = 7. Do đó ta tiếp tục việc tìm kiếm trên dãy mới (nửa daõy beân phaûi). Ghi chó: Tuú thuéc aGiua > k hoÆc aGiua < k mµ chØ số đầu hoặc chỉ số cuối của dãy ở bước tìm kiếm tiếp theo sẽ thay đổi. Để thực hiện điều đó, trong thuật toán chỉ sử dụng các biến nguyên tương ứng Dau và Cuoi có giá trÞ khëi t¹o Dau = 1 vµ Cuoi = N.. B.ThuËt to¸n T×m kiÕm nhÞ ph©n (Binary Search) * Xác định bài toán - Input: D·y A lµ d·y t¨ng gåm N sè nguyªn kh¸c nhau a1, a2,..., aN vµ mét 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 A cã gi¸ trÞ b»ng k. *YÙ tưởng: Sử dụng tính chất dãy A là dãy tăng, ta tìm c¸ch thu hÑp nhanh ph¹m vi t×m kiÕm sau mçi lÇn so sánh khoá với số hạng được chọn. Để làm điều đó, ta chọn số hạng aGiua ở "giữa dãy" để so sánh với k, trong đó  N  1 Giua =  .  2  Khi đó, chỉ xảy ra một trong ba trường hợp sau: -NÕu aGiua = k th× Giua lµ chØ sè cÇn t×m. ViÖc t×m kiÕm kÕt thóc. -Nếu aGiua > k thì do dãy A là dãy đã được sắp xếp nên viÖc t×m kiÕm tiÕp theo chØ xÐt trªn d·y a1, a2,..., aGiua–1 (ph¹m vi t×m kiÕm míi b»ng kho¶ng mét nöa ph¹m vi t×m kiếm trước đó). -NÕu aGiua < k th× thùc hiÖn t×m kiÕm trªn d·y aGiua+1, aGiua+2,..., aN. Quá trình trên sẽ được lặp lại một số lần cho đến khi hoặc đã tìm thấy khoá k trong dãy A hoặc phạm vi tìm kiÕm b»ng rçng. *ThuËt to¸n a) C¸ch liÖt kª Bước 1. Nhập N, các số hạng a1, a2,..., aN và khoá k; Bước 2. Dau ← 1, Cuoi ← N;.  Dau  Cuoi   ; 2 . Bước 3. Giua ← . 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ì đặt 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ó. sè h¹ng cã gi¸ trÞ b»ng k, råi kÕt thóc; Bước 8. Quay lại bước 3.. Lop10.com. Trang 17.

<span class='text_page_counter'>(18)</span> GA: Tin hoïc 10. GV: Đàng Ngọc Huynh. Tieát 10, 11, 12, 13, 14. b) Sơ đồ khối: (Binary Search) NhËp N vµ a1, a2,..., aN; k.  1; Cuoi  N Giua. . [(Dau + Cuoi)/2]. aGiua = k. §óng. §­a ra Giua råi kÕt thóc. Sai. §óng. aGiua > k. Cuoi.  Giua – 1. Sai Dau. Sai.  Giua + 1. Dau > Cuoi §óng Th«ng b¸o d·y A kh«ng cã sè h¹ng cã gi¸ trÞ b»ng k råi kÕt thóc. Dưới đây là ví dụ mô phỏng các bước thực hiện thuật toán (Binary Search) . k = 21, N =10 i 1 2 3 4 5 6 7 8 9 10 A 2 4 5 6 9 21 22 30 31 33 Dau 1 6 6 Cuoi 10 10 7 Giua 5 8 6 aGiua 9 30 21 Lượt 0 1 2 ở lượt thứ hai thì aGiua = k. Vậy chỉ số cÇn t×m lµ i = Giua = 6.. Lop10.com. k = 25, N =10 i 1 2 3 4 5 6 7 8 9 10 A 2 4 5 6 9 21 22 30 31 33 Dau 1 6 6 7 8 Cuoi 10 10 7 7 7 Giua 5 8 6 7 aGiua 9 30 21 22 Lượt 0 1 2 3 4 Tại lượt thứ tư Dau > Cuoi nên kết luận trong d·y A kh«ng cã sè h¹ng nµo cã gi¸ trÞ lµ 25 c¶.. Trang 18.

<span class='text_page_counter'>(19)</span> GA: Tin hoïc 10. GV: Đàng Ngọc Huynh. Tieát 10, 11, 12, 13, 14. 4.Tổng kết nội dung, đánh giá cuối bài: -Toùm taét baøi, nhaán maïnh caùc ñieåm chính. -Yêu cầu một số HS nhắc lại các thuật ngữ chính trong bài : Bài toán, Thuật toán, Sơ đồ khối, Input, Output. -Baøi taäp: Cho daõy soá goàm N soá sau (N=5):. 8. 11. 7. 20. 4. Tìm giaù trò NHOÛ NHAÁT cuûa daõy soá treân? Hướng dẫn: -Goïi Min laø giaù trò nhoû nhaát caàn tìm. -Gán Min bằng giá trị phần tử đầu tiên của dãy. -Lần lượt so sánh Min với các phần tử tiếp theo trong dãy. Tại mỗi vị trí so sánh, nếu Min lớn hơn giá trị phần tử cần so sánh trong dãy thì lấy giá trị của phần tử đó gán lại cho Min. -Khi so sánh đến phần tử cuối cùng trong dãy thì Min sẽ mang giá trị nhỏ nhất của dãy.. a.Lieät keâ:. b. Sơ đồ khối:. -Bước 1 : Nhập N và dãy a1,…, aN;. Nhaäp N vaø daõy a1,…, aN. -Bước 2 : Đặt Min ← a1, i ← 2;. Min ← a1 , i ← 2. -Bước 3 : Nếu i >N thì Đưa ra Min rồi kết thúc, nếu không thì chuyển đến bước 4; -Bước 4 : 4.1. Neáu Min > ai thì ñaët Min ← ai ;. i >N. Đúng. Sai Sai. Ñöa ra Min roài keát thuùc. Min > ai Đúng. Min ← ai. 4.2. Tăng i một đơn vị rồi quay về bước 3. i ← i+1. 5.Dặn dò, kế hoạch học tập tiết sau: -Daën HS tham khaûo theâm VD trong SGK -Baøi taäp veà nhaø: Baøi 1, 3, 4, 5, 6 trang 44 -Yêu cầu HS đọc trước bài mới “Ngôn ngữ lập trình”.. IV. NHỮNG VẤN ĐỀ CẦN RÚT KINH NGHIỆM:. Lop10.com. Trang 19.

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