2012 PPCT 13
Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (102.21 KB, 3 trang )
<span class='text_page_counter'>(1)</span>Gi¸o ¸n chi tiÕt líp 10 Bµi 4: BµI TO¸N Vµ THUËT TO¸N TiÕt theo PPCT: 13. Ngêi so¹n: GV Ph¹m Anh Tïng. Ngµy so¹n: 28 th¸ng 09 n¨m 2012. TuÇn häc thø: 07 I. Mục đích, yêu cầu: 1. Mục đích: - HS hiÓu râ kh¸i niÖm thuËt to¸n lµ c¸ch gi¶i bµi to¸n mµ vÒ nguyªn t¾c cã thÓ giao cho m¸y thùc hiÖn; - HS cần hiểu và thực hiện đợc một số thuật toán đơn giản trong SGK. 2. Yªu cÇu: Gi¸o viªn: - Gi¸o ¸n, tranh ¶nh. - S¸ch gi¸o khoa. Häc sinh: - §äc tríc s¸ch gi¸o khoa ë nhµ. - S¸ch gi¸o khoa vµ vë ghi chÐp bµi. ThiÕt bÞ d¹y häc: - M¸y chiÕu ®a n¨ng, b¶ng ®en, s¸ch gi¸o khoa, m¸y tÝnh ®iÖn tö, … II. TiÕn tr×nh lªn líp: A. ổn định lớp: - SÜ sè: …… - Sè häc sinh cã mÆt: ….. B. KiÓm tra bµi cò: Câu hỏi: Em hãy xác định bài toán Sắp xếp dãy gồm N số nguyên a1, ..., aN thành dãy kh«ng gi¶m? Đáp án: Xác định bài toán là chúng ta xác định thông tin nhập vào và thông tin thu đợc sau khi xử lý bài toán. Do vậy bớc xác định thông tin bài toán của bài Sắp xếp dãy gồm N số nguyªn a1, ..., aN thµnh d·y kh«ng gi¶m lµ: + Input: - NhËp vµo sè nguyªn N bÊt k×. - Nhập lần lợt giá trị các phần tử đó + Output: Thông báo dãy số đã đợc sắp xếp theo trình tự là dẫy không giảm. C. Néi dung bµi häc: Hoạt động dạy – HọC - GV: Cho HS xác định bài toán.. - HS: Nªu ý tëng. - GV nhËn xÐt. - GV: Gợi ý để HS nêu đợc thuật toán. - HS: Nªu thuËt to¸n. - GV: ChØ dÉn cho HS tõ d¹ng 1 chuyÓn sang d¹ng 2. Dạng 2: Sơ đồ khối. NhËp N vµ a1, a2,..., aN. MN M<2? Sai. §óng. §a ra A råi kÕt thóc. NéI DUNG 3. Mét sè vÝ dô vÒ thuËt to¸n(tiÕp) Bµi to¸n:. S¾p xÕp d·y gåm N sè nguyªn a1, ..., aN thµnh d·y kh«ng gi¶m? + 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. + ý tëng: Với mỗi cặp số hạng đứng liền kề trong dãy, nếu số trớc lớn hơn số sau ta đổi chỗ chúng cho nhau. Việc đó đợc lặp lại, cho đến khi không có sự đổi chỗ nào xảy ra nữa. Thuật toán Sắp xếp bằng tráo đổi (Exchange Sort). + ThuËt to¸n: D¹ng 1: LiÖt kª Bíc 1: NhËp N, c¸c sè h¹ng a1, a2,..., aN; Bíc 2: M N; Bớc 3: Nếu M < 2 thì đa ra dãy A đã đợc sắp.
<span class='text_page_counter'>(2)</span> ii+1 §óng i > M ? – HäC Hoạt động d¹y Sai Tráo đổi ai và ai+1. §óng. ai > ai+1 ?. Sai. NéI DUNG xÕp råi kÕt thóc; Bíc 4: M M – 1, i 0; Bíc 5: i i + 1; Bíc 6: NÕu i >M th× quay l¹i bíc 3; Bớc 7: Nếu ai > ai+1 thì tráo đổi ai và ai+1 cho nhau; Bíc 8: Quay l¹i bíc 5. 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. - 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.. Díi ®©y lµ vÝ dô m« pháng c¸c bíc thùc hiÖn cña thuËt to¸n trªn. D·y A 6 1 5 3 7 8 10 7 12 4 Lît 1 5 3 6 7 8 7 10 4 12 1 Lît 1 3 5 6 7 7 8 4 10 2 Lît 1 3 5 6 7 7 4 8 3 Lît 1 3 5 6 7 4 7 4 Lît 1 3 5 6 4 7 5 Lît 1 3 5 4 6 6 Lît 1 3 4 5 7 Lît 1 3 4 8 Lît 1 3 9 Lît 10 1 VÝ dô 3. Bµi to¸n t×m kiÕm. Bài toán: 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ố đó. Số nguyên k đợc gọi là khoá tìm kiếm (gọi tắt lµ kho¸). 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.
<span class='text_page_counter'>(3)</span> Hoạt động dạy – HọC - GV: Các em hãy lấy ví dụ để minh hoạ? - HS: LÊy vÝ dô. - GV: Cho HS xác định bài toán. - HS: Tr¶ lêi yªu cÇu cña GV.. NéI DUNG kh«ng cã sè h¹ng nµo cña d·y A cã gi¸ trÞ b»ng k. + ý tởng: Tìm kiếm tuần tự đợc thực hiện mét c¸ch tù nhiªn. 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á hoặc dãy đã đợc xét hết và không có giá trÞ nµo b»ng kho¸. Trong trêng hîp thø hai d·y A kh«ng cã sè h¹ng nµo b»ng kho¸. + ThuËt to¸n:. - GV: Em h·y nªu ý tëng cña bµi to¸n? - HS: Nªu ý tëng. - GV: NhËn xÐt. - HS : Tù t×m hiÓu th«ng qua th¶o luËn nhãm. D. Cñng cè bµi häc: - Thuật toán có 3 tính chất? Lấy ví dụ để minh hoạ 3 tính chất này. - Híng dÉn häc sinh thuËt to¸n t×m min{aN} E. Bµi tËp vÒ nhµ: - GV híng dÉn HS lµm bµi tËp 3, 4, 5 SGK trang 44. - Híng dÉn HS viÕt thuËt to¸n gi¶i bµi to¸n: T×m 10 sè nguyªn d¬ng ®Çu tiªn biÕt c¸c sè nµy chia cho 2, 3, 4, 5, 6 d 1 vµ chia hÕt cho 7. VÝ dô: Sè ®Çu tiªn lµ 301. F. §óc rót kinh nghiÖm:. ………………………………………………………………………………… …………... ………………………………………………………………………………… …………... ………………………………………………………………………………… …………………………………………………………………... ………………………………………………………………………………… …………... ………………………………………………………………………………… ……………………………………………………………... ………………………………………………………………………………… …………...……………………………………………………….........
<span class='text_page_counter'>(4)</span>
