CD3 BAI TOAN THUAT TOAN TIN 10Bạ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 (303.32 KB, 11 trang ) Ngày soạn: 9/2018 dụng linh hoạt trong lớp những bài toán dạng này. 3. Năng lực hướng tới: - - Năng lực chung: năng lực giải quyết vấn đề, năng lực sáng tạo, năng lực hợp tác, năng lực sử dụng ngôn ngữ, năng lực tự học, năng lực tính toán và năng lực sử dụng CNTT-TT. - Năng lực chuyên biệt, chuyên môn: Năng lực khoa học máy tính cơ bản; Sử dụng máy tính để học tập II. Đồ dùng dạy học 1. Chuẩn bị của giáo viên: SGK, SGV, phấn, máy chiếu 2. Chuẩn bị của học sinh: SGK, vở ghi III. Hoạt động dạy - học 1. Ổn định tổ chức: Ổn định nề nếp, kiểm tra sĩ số 2. Kiểm tra bài cũ: Một máy tính chưa có phần mềm có thể hoạt động được không? Vì sao? Em có biết thiết bị nào vừa là thiết bị vào vừa là thiết bị ra không? Em hãy trình bày khái niệm bài toán? Khi giải bài toán bằng máy tính thì cần quan tâm đến những yếu tố nào? Cho ví dụ? Hãy mô tả thuật toán tìm giá trị nhỏ nhất của 1 dãy số nguyên theo phương pháp liệt kê? Hãy mô tả thuật toán tìm giá trị nhỏ nhất của 1 dãy số nguyên theo pp sơ đồ khối? Hãy nêu các cách biểu diễn thuật toán? Các tính chất của thuật toán? Hãy mô tả thuật toán tìm UCLN của 2 số nguyên dương theo phương pháp liệt kê? Hãy mô tả thuật toán tìm UCLN của 2 số nguyên dương theo phương pháp sơ đồ khối? 3. Nội dung: Hoạt động của Giáo viên và Học sinh Nội dung Hoạt động 1: Giới thiệu khái niệm bài toán GV: Bài toán là gì, thuật toán là gì, thuật toán 1. Khái niệm bài toán trong tin học: dùng để làm gì, để biết được những điều trên Ví dụ 1a: Bài toán Giải PT: chúng ta cùng nghiên cứu bài hôm nay: Bài ax + b = 0 (với a0) (*) toán và thuật toán. Ta nói đây là một bài toán. 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 thông tin đã có phải đưa ra một kết quả nào đó. Vậy bài toán trong tin học có gì khác? HS: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. GV: Đưa ra 2 ví dụ GV: Từ ví dụ 1a, ví dụ 1b em hãy cho biết bài toán là gì? Và cũng từ các ví dụ trên ta thấy bài toán được cấu tạo bởi các thành phần nào? HS:Trả lời câu hỏi. GV: Vậy, khi cho một bài toán thì điều đầu tiên là chúng ta phải xác định được Input và Output của bài toán. Việc xác định Input và Ouput được gọi chung là xác định bài toán. HS: Chú ý lắng nghe, ghi chép. GV: Đưa ra ví dụ 2, 3, 4, 5 . Yêu cầu HS đứng tại chỗ xác định các thành phần của mỗi bài toán. GV: Dẫn dắt để các em tự tìm được Input và Output. HS: Đứng tại chỗ trả lời Bài toán này các thành phần: + Input: các gía trị a, b. + Output: tìm giá trị x thoả mãn (*) Ví dụ 1b: Bài toán: cho số nguyên dương N và dãy A: a1, a2,....,aN. Tìm giá trị lớn nhất của dãy A + Input: Số nguyên dương N và dãy A. + Output: Max(a1, a2,....,aN) Khái niệm: bài toán là việc nào đó ta muốn máy tính thực hiện Bài toán được cấu tạo bởi hai thành phần cơ bản: + Input (giả thiết): Các thông tin đã có; + Output (kết luận): Các thông tin cần tìm từ Input. Ví dụ 2. Bài toán tìm ước chung lớn nhất của hai số nguyên dương + Input: Hai số nguyên dương M và N; + Output: Ước chung lớn nhất của M và N. Ví dụ 3. Bài toán tìm nghiệm của phương trình bậc hai + Input: Các số thực a, b, c (a 0); + Output: Số thực x thoả mãn: ax2 + bx + c = 0. ở đây, Output có thể là một hoặc hai số thực hoặc câu trả lời không có số thực nào như vậy. Ví dụ 4. Bài toán tính diện tích hình chữ nhật + Input: Chiều dài, chiều rộng. + Output: Diện tích. Ví dụ 5. Bài toán xếp loại học tập của một lớp + Input: Bảng điểm của học sinh trong lớp; + Output: Bảng xếp loại học lực. Hoạt động 2: Giới thiệu khái niệm thuật toán GV: Nhưng muốn máy tính đưa ra 2. Khái niệm thuật toán. được output từ input đã cho thì cần Khái niệm thuật toán: Thuật toán để giải một bài toán là một dãy phải có chương trình, mà muốn viết hữu hạn các thao tác được sắp xếp theo một trình tự xác định sao cho được chương trình cần phải có sau khi thực hiện dãy thao tác ấy, từ Input của bài toán, ta nhận được thuật toán. Vậy thuật toán là gì ? Output cần tìm. HS: Trả lời câu hỏi Tác dụng của thuật toán: dùng để giải 1 bài toán. GV: Kết luận. Ví dụ 1: Bài toán Giải PT: ax + b = 0 (*) Xây dựng thuật toán để giải bài toán trên. GV: Đưa ra ví dụ tìm ngiệm của * Bài toán này các thành phần: phương trình dạng ax + b = 0 - Input: các gía trị a, b. GV: nêu các bước để giải bài toán - Output: tìm giá trị x thoả mãn (*) HS:quan sát, lắng nghe. * Ý tưởng: GV: xác định dữ liệu của bài toán? - Nếu a = 0 thì PT vô định. HS: Đứng tại chỗ xác định input và - Nếu a 0 thì PT có nghiệm: x = - b/a output. * Thuật toán: Bước 1: Nhập các giá trị a, b. Bước 2: Nếu a = 0 thì đưa ra thông báo PT vô nghiệm rồi kết thúc. Bước 3: Nếu a 0 thì đưa ra nghiệm x rồi kết thúc. GV: Em hãy trình bày các tính chất Các tính chất của thuật toán. của thuật toán? - Tính dừng: Thuật toán phải kết thúc sau một số hữu hạn lần thực HS:trả lời. hiện các thao tác; - Tính xác định: Sau khi thực hiện một thao tác thì hoặc là thuật toán kết thúc hoặc là có đúng một 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 phải nhận được Output cần tìm. Hoạt động 3: Hướng dẫn học sinh giải bài toán Tìm GTLN của 1 dãy số nguyên GV: học sinh xác định Input và Output Ví dụ 2. Tìm giá trị lớn nhất của một dãy số nguyên HS: Đứng tại chỗ trả lời Xác định bài toán: - Input: Số nguyên dương N và dãy N số nguyên a1,..., aN. GV: em cho biết ý tưởng bài toán Tìm giá - Output: Giá trị lớn nhất Max của dãy số. trị lớn nhất của một dãy số nguyên Ý tưởng: HS: Đứng tại chỗ trả lời - Khởi tạo giá trị Max = a1. - Lần lượt với i từ 2 đến N, so sánh giá trị số hạng ai với giá trị Max, nếu ai > Max thì Max nhận giá trị mới là ai. GV: Ta có thể mô tả thuật toán bằng 2 cách: Thuật toán: có 2 cách Cách 1: Cách liệt kê liệt kê và dùng sơ đồ khối. GV: Dưới đây là ví dụ mô phỏng các bước Thuật toán. Thuật toán giải bài toán này có thể được mô thực hiện thuật toán trên với N = 7 và dãy A: tả theo cách liệt kê như sau: Bước 1. Nhập N và dãy a1,..., aN; 5, 1, 4, 7, 6, 3, 15 Bước 2. Max a1, i 2; 5 1 4 7 6 3 15 Dãy A Bước 3. Nếu i > N thì đưa ra giá trị Max rồi kết thúc; 2 3 4 5 6 7 i Bước 4. 5 5 5 7 7 7 15 Max 4.1. Nếu ai > Max thì Max ai; HS: quan sát, lắng nghe. 4.2. i i + 1 rồi quay lại bước 3; GV: Cách viết thuật toán theo từng bước Cách 2: Sử dụng sơ đồ khối như trên gọi là cách liệt kê. Còn cách làm * Quy định: khác đó là dùng sơ đồ khối. Hình thoi thể hiện thao tác so sánh; HS: theo dõi trên bảng phụ. GV: Em hãy nhìn vào thuật toán dưới dạng Hình chữ nhật thể hiện các phép tính toán; sơ đồ khối và hãy cho biết thuật toán được diễn tả dưới dạng sơ đồ khối với các quy Các mũi tên quy định trình tự thực hiện các thao định thế nào? tác; HS: Trả lời câu hỏi. Hình ellip thể hiện thao tác nhập, xuất dữ liệu. GV: dựa vào sơ đồ khối cho HS làm bài tập VD. HS: làm bài tập theo yêu cầu của GV Nhập N và dãy a1,..., aN Max Dãy A i Min 11 6 20 2 8 7 3 2 3 4 5 6 7 i>N? Đ Đưa ra Max rồi kết thúc Sai S ai ai > Max? Đúng Max ai i i+1 * Bài tập vận dụng: Cho dãy số gồm N số sau (N =7): 11 6 20 2 8 7 3 Tìm giá trị NHỎ NHẤT của dãy số trên ? Hoạt động 4: Hướng dẫn học sinh giải bài toán Tìm UCLN của 2 số nguyên GV: Đưa ra ví dụ UCLN của 2 số M, N. Xác 3. Một số ví dụ: định input và output của bài toán. Ví dụ 1. Thuật toán tìm ước chung lớn nhất của 2 số M, N HS: Đứng tại chỗ xác định Input và Output. Xác định bài toán GV: em cho biết ý tưởng bài toán Tìm - Input: Hai số nguyên dương M, N UCLN của 2 số nguyên - Output: UCLN của M và N HS: trả lời câu hỏi. GV: Ghi thuật toán lên bảng. Thuật toán: có 2 cách HS: Ghi chép Cách 1: Cách liệt kê GV: Lấy VD cụ thể với 2 số (12,8) và giải thích thuật toán qua từng bước: B1: Nhập M =12, N =8 M > N B3: M =12 8 = 4, N = 8 N > M B4: M = 4, N = 8 4 = 4 M = N UCLN (M, N) = 4 HS: quan sát, lắng nghe. GV: Cách viết thuật toán theo từng bước gọi là cách Liệt kê, còn có cách làm khác đó là dùng sơ đồ khối. GV: Lấy lại VD tìm UCLN của 2 số M, N GV: Vẽ sơ đồ thuật toán lên bảng. Chỉ cho HS: thấy các bước thực hiện của thuật toán được mô tả trong sơ đồ khối. HS: Ghi lại sơ đồ thuật toán và hình dung ra các bước giải của thuật toán - B1: Nhập M,N - B2: Nếu M = N thì UCLN = M - B3: Nếu M > N thì thay M = M N, quay lại B2 - B4: Thay N = N M rồi quay lại B2 - B5: Gán UCLN là M. Kết thúc. Cách 2: Sử dụng sơ đồ khối Nhập M, N M=N M = M N Đ S Đ kết thúc M>N S N BT vận dụng: Tìm UCLN của 2 số 21 và 14 Hoạt động 5: Giới thiệu cho học sinh về bài toán sắp xếp. GV: Trong cuộc sống chúng ta thường gặp những việc liên 3. Một số ví dụ: (tt) quan đến sắp xếp như: xếp những học sinh theo thứ tự từ Ví dụ 2: Bài toán sắp xếp. thấp đến cao, xếp loại học sinh theo điểm trung bình của Bài toán: Cho dãy A gồm N số nguyên a1, học sinh từ cao xuống thấp. Một cách tổng quát cho một a2, .., aN. Cần sắp xếp các số hạng để dãy A trở dãy đối tượng cần sắp xếp theo một tiêu chí nào đó. Chẳng thành dãy không giảm (tức là số hạng trước hạn như cho 10 chiếc cọc khác nhau (hình 22a) cần xếp lại không lớn hơn số hạng sau). cọc từ thấp đến cao (hình 22b). Dưới đây ta chỉ xét bài Ví dụ: toán sắp xếp dạng đơn giản. Các em ghi bài toán. Dãy 7 4 9 5 7 sau khi sắp xếp được dãy: HS: ghi bài. 4 5 7 7 9 GV: Để sắp xếp dãy này có nhiều thuật toán sắp xếp. Sau đây chúng ta nghiên cứu thuật toán sắp xếp bằng tráo đổi. HS: quan sát, lắng nghe. Hoạt động 6: Hướng dẫn học sinh tìm hiểu thuật toán sắp xếp bằng tráo đổi GV: Yêu cầu học sinh xác định bài toán. * Xác định bài toán. Ví dụ: Cho dãy số nguyên sau: - Input: Dãy A gồm N số nguyên a1, a2,..., aN 6 1 5 3 7 - Output: Dãy A được sắp xếp lại thành dãy không giảm. GV: Theo em dãy số này nếu xếp tăng dần thì * ý tưởng bài toán sẽ như thế nào? - Với mỗi cặp số hạng đứng liền kề trong dãy, nếu số đứng trước lớn hơn số sau, ta đổi chỗ chúng cho nhau. Việc đó HS: đưa ra dãy đã sắp xếp tăng dần. được lặp lại, cho đến khi không có sự đổi chỗ nào nữa xảy 1 3 5 6 7 ra. HS: đưa ra ý tưởng, thảo luận nhiều ý tưởng khác nhau. GV: giải thích cho học sinh từng bước của * Thuật toán: thuật toán. a) Cách liệt kê: HS: trao đổi, thảo luận. B1: Nhập vào số nguyên dương N và dãy số a1, a2, ..., aN HS: phát biểu từng bước liệt kê sơ đồ khối. B2: MN; B3: Nếu M<2 thì sang B9 B4: M M - 1; i1 GV: Dùng bảng phụ HS: Quan sát, vẽ vào vở HS: lần lượt vẽ các bước sơ đồ khối theo các bước. B5: Nếu ai > ai+1 thì tráo đổi ai và ai+1 cho nhau B6: i i+1 B7: Nếu i > M thì quay lại B3 B8: Quay lại B5 B9: Đưa ra dãy số đã được sắp xếp, kết thúc. b) Dùng sơ đồ khối: Nhập N và a1, a2,..., aN MN M<2? đúng đưa ra A rồi kết thúc Sai M M 1; i 0 ii+1 đúng Tráo đổi ai và ai+1đúng i>M? Sai ai > ai+1 ? Sai GV: Thực hiện lần lượt việc mô phỏng thuật Mô phỏng việc thực hiện thuật toán với: N = 5 và dãy A: 6, 1, 5, 3, 7 toán cho HS quan sát. Tuy nhiên vẫn phải làm cho tới khi dãy chỉ còn Với dãy số 6 1 5 3 7 1 phần tử. Lần 1: 6 1 5 3 7 Như vậy ta được dãy số sắp xếp tăng dần. (đổi chỗ a1 và a2) 1 6 5 3 7 Dãy A 6 1 5 3 7 (đổi chỗ a2 và a3) 1 5 6 3 7 1 6 5 3 7 1 5 3 6 7 Lượt 1 1 5 6 3 7 1 5 3 6 7 Lần 2: 1 5 3 6 7 Lượt 2 1 3 5 6 (đổi chỗ a2 và a3) 1 3 5 6 7 Lượt 3 1 3 5 Lượt 4 1 3 Khi đó dãy đã sắp xếp xong. Lượt 5 1 3 5 6 7 * Bài tập vận dụng: HS: theo dõi, nhận xét và ghi chép vào vở. a. Sắp xếp dãy tăng dần: 4 5 15 23 6 12 b. Sắp xếp dãy giảm dần: 7 9 5 15 1 6 Hoạt động 7: Giới thiệu cho học sinh về bài toán tìm kiếm Đặt vấn đề: Tìm kiếm là một việc thường xảy 3. Một số ví dụ: (tt) ra trong cuộc sống. Ví dụ 3: Bài toán tìm kiếm Cho dãy A gồm N số nguyên khác nhau: a 1, a2, , aN và GV: Cho dãy A gồm: 5, 7, 1, 4, 2, 9, 8, 11, 25, một số nguyên k. Cần biết có hay không chỉ số i ( 1 i 51. Tìm i với ai = 2 ? N) mà ai = k. Nếu có hãy cho biết chỉ số đó. HS: i = 5 a) Thuật toán tìm kiếm tuần tự (sequential search) GV: Tổ chức các nhóm thảo luận Xác định bài toán HS: Các nhóm thảo luận, đưa ra ý kiến Input: Dãy A gồm N số nguyên khác nhau a 1, a2, , GV. Hãy xác định bài toán? aN và số nguyên k; HS. + Input: N, a1, a2, , aN, k - Output: Chỉ số i mà ai = k hoặc thông báo không có số + Output: i hoặc thông báo không có i GV hướng dẫn HS tìm thuật toán giải bài toán. hạng nào của dãy A có giá trị bằng k. Ý tưởng: - Tìm kiếm tuần tự là lần lượt từ số hạng thứ nhất, ta so GV: Cho các nhóm trình bày ý tưởng. sánh giá trị số hạng đang xét với khoá cho đến khi hoặc HS: thực hiện hoạt động nhóm theo y/c của GV 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á. Hoạt động 8: Hướng dẫn học sinh tìm hiểu thuật toán tìm kiếm GV hướng dẫn HS trình bày thuật toán tìm b) Thuật toán: kiếm bằng cách liệt kê. * Cách liệt kê: HS: Các nhóm thảo luận và đưa ra thuật toán. - B1: Nhập N, các số hạng a1, a2, , aN và khoá k; GV: i là biến chỉ số và nhận giá trị nguyên lần - B2: i � 1; - B3: Nếu ai = k thì thông báo chỉ số i, kết thúc; lượt từ 1 đến N+1. - B4: i � i + 1; - B5: 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. - B6: Quay lại bước 3. GV: Dùng bảng phụ * Sơ đồ khối: HS: Quan sát, vẽ vào vở HS: lần lượt vẽ các bước sơ đồ khối theo các bước. GV: Thực hiện lần lượt việc mô phỏng thuật c) Mô phỏng việc thực hiện thuật toán với: N = 10, k = 2 và dãy A: 5 7 1 4 2 9 8 11 25 51 toán cho HS quan sát. k = 2 và N = 10 HS: theo dõi, nhận xét và ghi chép vào vở. A 5 7 1 4 2 9 8 11 25 51 i 1 2 3 4 5 - - - - Vậy i = 5 thì a5 = 2. 4. Củng cố - dặn dò: * Qua bài học yêu cầu học sinh cần nắm được: - Bài toán là việc mà bạn muốn máy tính thực hiện. - Muốn giải một bài toán trước tiên phải xác định được Input và Output. + Input: các thông tin đã cho trước. + Output: thông tin cần tìm từ Input đã cho. - Xác định được Input & Output của các bài toán tìm giá trị lớn nhất của 1 dãy số nguyên, bài toán sắp xếp theo pp tráo đổi, bài toán tìm kiếm theo pp tuần tự bằng 2 dạng: liệt kê và sơ đồ khối. - Nhắc lại các thuật toán cơ bản: tìm UCLN của 2 số nguyên - Việc xác định bài toán và đưa thuật toán bài toán sắp xếp, bài toán tìm kiếm. * Dặn dò: Học bài cũ. - Làm bài tập trong SBT ----------------------------------------------- BÀI TẬP I. Mục đích bài học 1. Kiến thức: - Biết khái niệm thuật toán, các đặc trưng chính của thuật toán. - Hiểu cách biểu diễn thuật toán bằng sơ đồ khối và ngôn ngữ liệt kê. - Hiểu một số thuật toán thông dụng. 2. Kĩ năng: - Xây dựng được thuật toán giải 1 số bài toán đơn giản theo cách liệt kê và sơ đồ khối. 3. Năng lực hướng tới: - Năng lực chung: năng lực giải quyết vấn đề, năng lực sáng tạo, năng lực hợp tác, năng lực sử dụng ngôn ngữ, năng lực tự học và năng lực sử dụng CNTT-TT. - Năng lực chuyên biệt, chuyên môn: Năng lực khoa học máy tính cơ bản; Sử dụng máy tính để học tập. II. Đồ dùng dạy học 1. Chuẩn bị của giáo viên: SGK, SGV, phấn, máy chiếu 2. Chuẩn bị của học sinh: SGK, vở ghi III. Hoạt động dạy - học 1. Ổn định tổ chức: Ổn định nề nếp, kiểm tra sĩ số 2. Kiểm tra bài cũ: Câu 1: Hãy nêu các cách biểu diễn thuật toán? Các tính chất của thuật toán? Câu 2: Hãy mô tả thuật toán Bài toán sắp xếp theo phương pháp liệt kê? Câu 3: Hãy mô tả thuật toán Bài toán sắp xếp theo phương pháp sơ đồ khối? 3. Nội dung: Hoạt động của Giáo viên và Học sinh Nội dung Hoạt động 1: Luyện tập cách xác định bài toán GV: Cho các nhóm thảo luận, gọi 1 HS bất kì trong nhóm trả Bài 1: Hãy xác định các bài toán sau: lời. a) Tính chu vi hình chữ nhật khi cho biết HS trả lời chiều dài và chiều rộng của hình chữ nhật a) Input: chiều dài, chiều rộng đó. Output: chu vi b) Tìm giá trị lớn nhất của 2 số a, b. b) Input: a, b c) Tìm và đưa ra nghiệm của phương Output: GTLN của a và b. trình bậc 2 tổng quát: ax2 + bx + c = 0 c) Input: 3 số thực a, b, c (a0). (a0) Output: Kết luận nghiệm của phương trình ax2 + bx + c = 0. Hoạt động 2: Mô tả thuật toán giải các bài toán bằng cách liệt kê hoặc bằng sơ đồ khối GV: Cho các nhóm thực hiện lần lượt các bước Bài 2: Cho N và dãy số a1, a2, , aN. Hãy tìm thuật toán để tìm thuật toán. cho biết có bao nhiêu số hạng trong dãy có giá trị bằng GV: Gọi 1 HS bất kì trong nhóm trả lời. 0. HS: trả lời a) Xác định bài toán? GV. Xác định bài toán? Input: N, a1, a2, , aN HS. Input: N, a1, a2, , aN Output: số Dem cho biết số lượng số 0 có trong dãy số Output: số Dem cho biết số lượng số 0 có trên. trong dãy số trên. b) Ý tưởng thuật toán? GV. Nêu ý tưởng thuật toán? Ban đầu Dem = 0 HS: Ban đầu Dem = 0 Lần lượt duyệt qua dãy số, nếu gặp số hạng nào bằng 0 Lần lượt duyệt qua dãy số, nếu gặp số hạng nào thì tăng giá trị Dem lên 1. bằng 0 thì tăng giá trị Dem lên 1. Hoạt động 3: Biểu diễn thuật toán bằng phương pháp liệt kê sơ đồ khối GV: Hướng dẫn HS liệt kê các bước của thuật c) Thuật toán: toán và vẽ sơ đồ khối. * Liệt kê: HS: HS: theo dõi, nhận xét và ghi chép vào vở. B1: Nhập N, a1, a2, , aN B2: i 0; Dem 0 B3: i i + 1 B4: Nếu i > N thì thông báo giá trị Dem, rồi kết thúc. B5: Nếu ai = 0 thì Dem Dem + 1. B6: Quay lại B3. * Sơ đồ khối: GV: Thực hiện lần lượt việc mô phỏng thuật d) Mô phỏng việc thực hiện thuật toán: a) N = 10, dãy A: 1, 2, 0, 4, 5, 0, 7, 8, 9, 0 Dem = 3 toán cho HS quan sát. b) N = 10, dãy A: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 Dem = 0 HS: theo dõi, nhận xét và ghi chép vào vở. 4. Củng cố - dặn dò: * Qua bài học yêu cầu học sinh cần nắm được: - Nắm được các cách giải bài toán bằng liệt kê và sơ đồ khối của các bài toán đã học. * Dặn dò: Học bài cũ. - Về nhà các em xem lại phần lý thuyết và bài tập từ bài 1 đến 4. * Bảng mô tả các mức yêu cầu cần đạt cho mỗi loại câu hỏi/bài tập trong chủ đề. Nội dung Loại câu hỏi/bài tập 1. Khái niệm bài toán Câu hỏi /bài tập định tính 2. Khái niệm thuật toán Câu hỏi /bài tập định tính 3. Các cách biểu Câu hỏi /bài diễn tập định tính thuật toán Câu hỏi /bài tập định tính Nhận biết Thông hiểu BÀI TOÁN VÀ THUẬT TOÁN Biết bài toán trong Tìm Input và Tin học Output của một Biết Input và Output số bài toán. của bài toán. ND1.ĐT.TH1 ND1.ĐT.NB1 ND1.ĐT.TH2 ND1.ĐT.NB2 Biết khái niệm thuật Ý nghĩa của thuật toán, các đặc trưng toán tối ưu. của thuật toán. Một thuật toán có ND2.ĐT.NB1 thể giải được ND2.ĐT.NB2 nhiều bài toán. ND2.ĐT.TH1 ND2.ĐT.TH2 Có 2 cách trình bày Qui định sử dụng thuật toán: liệt kê & các hình trong vẽ sơ đồ khối. sơ đồ khối. ND3.ĐT.NB1 ND3.ĐT.TH1 ND3.ĐT.NB2 ND3.ĐT.TH2 Xác định được giá trị Max khởi tạo. ND4.ĐT.TH1 4. Một số ví dụ Câu hỏi /bài tập định lượng Vận dung thấp Vận dụng cao Đọc hiểu thuật toán từ đó phát biểu bài toán. ND4.ĐT.VDC1 ND4.ĐT.VDC2 Vận dụng 1 số Vận dụng 1 số thuật toán cho thuật toán sẵn để đưa ra các thông dụng để kết quả. mô phỏng ví dụ ND4.ĐT.VDT1 minh hoạ. ND4.ĐT.VDT2 ND4.ĐL.VDC ND4.ĐT.VDT3 1 ND4.ĐT.VDT4 * BỘ NỘI DUNG CÂU HỎI : ND1.ĐT.NB1 Hãy chọn phương án đúng. Trong phạm vi Tin học bài toán là: A. Công việc mà ta cần tính toán. B. Thuật toán có thể giải các bài toán. C. Một việc nào đó mà ta muốn máy tính cần thực hiện. D. Một yêu cầu mà máy tính thực hiện. ND1.ĐT.NB2 Việc xác định bài toán là đi xác định các thành phần nào? A. Input B. Output C. Input và Output D. Không có thành phần nào ND1.ĐT.TH1 Hãy xác định Input của bài toán Tìm nghiệm của phương trình bậc hai ax2 + bx + c = 0 (a#0) A. Các số thực a, b, c (a#0) B. Các số thực a, b, c C. Các số a, b, c (a#0) D. Các số a, b, c ND1.ĐT.TH2 Hãy xác định Output của bài toán Tính chu vi hình tròn với bán kính cho trước: A. Tính chu vi của hình tròn B. Bán kính của hình tròn C. Chu vi của hình tròn D. Chu vi và bán kính hình tròn ND2.ĐT.NB1 Một thuật toán là: A. Việc chỉ ra tường minh một cách tìm Input từ Output B. Việc chỉ ra tường minh một cách tìm Output từ Input C. Một dãy hữu hạn các thao tác được sắp xếp theo trình tự xác định sao cho sau khi thực hiện ta nhận được Output cần tìm từ Input. D. Một dãy hữu hạn các thao tác được sắp xếp theo trình tự xác định sao cho sau khi thực hiện ta nhận được Input cần tìm từ Output. ND2.ĐT.NB2 (1) là một dãy hữu hạn các (2) được sắp xếp theo mộ trật tự xác định sao cho khi thực hiện dãy các thao tác ấy, từ (3) của bài toán, ta nhận được (4) cần tìm. Lần lượt điền các cụm từ còn thiếu là? A. Input OutPut - thuật toán thao tác B. Thuật toán thao tác Input OutPut C. Thuật toán thao ác Output Input D. Thao tác - Thuật toán Input OutPut ND2.ĐT.TH1 Một thuật toán để giải một bài toán được xem là tối ưu nếu chương trình tương ứng được sử dụng các ít lượng tài nguyên sau: A. Số lượng thao tác cơ bản cần dùng B. Thời gian thực hiện C. Số lượng ô nhớ D. Cả 3 tài nguyên trên ND2.ĐT.TH2 Hãy chọn phát biểu đúng ? A. Mỗi bài toán chỉ có một thuật toán để giải. B. Mỗi thuật toán chỉ giải được một bài toán. C. Mỗi thuật toán có thể giải được nhiều bài toán. D. Mỗi bài toán chỉ giải một thuật toán. ND3.ĐT.NB1 Có bao nhiêu cách trình bày một thuật toán? A. 2 cách B. 3 cách C. 4 cách D. 1 cách ND3.ĐT.NB2 Hãy chọn phương án ghép đúng : Trong tin học sơ đồ khối là: A. Ngôn ngữ lập trình bậc cao B. Sơ đồ mô tả thuật toán C. Sơ đồ về cấu trúc máy tính D. Sơ đồ thiết kế vi điện tử ND3.ĐT.TH1 Hình nào sau dây không dùng biểu diễn thuật toán? A. B. C. D. ND3.ĐT.TH2 Trong cách diễn tả bằng sơ đồ khối hình thoi - hình chữ nhật dùng để thể hiện lần lượt thao tác: A. so sánh và tính toán B. xuất/nhập dữ liệu và so sánh C. tính toán và xuất nhập dữ liệu D. a, b, c đều sai ND4.ĐT.TH1 Cho dãy số A: 4 9 7 1 5 3 Giá trị Max được khởi tạo lần đầu là bao nhiêu: A. 9 B. 4 C. 1 D. 3 ND4.ĐL.VDT1 Cho thuật toán sau: B1: Nhập 2 số nguyên a, b B2: Nếu a>b thì a a b , ngược lại b b a B3: a a . b B4: Thông báo giá trị a, b, rồi kết thúc. Với các bộ dữ liệu vào như sau, hãy cho biết kết quả của thuật toán (dữ liệu ra) a) a = 6 , b = 2 a = , b = b) a= 3 , b = 3 a = , b = c) a = 5, b = 7 a = , b = ND4.ĐL.VDT2 Trong thuật toán tìm kiếm tuần tự với N=5; K=9 và dãy A như sau: 1 4 2 9 8 Khi thuật toán kết thúc thì i nhận giá trị là bao nhiêu? A. 6 B. 5 C. 4 D. 3 ND4.ĐL.VDT3 Cho dãy A gồm các số sau: 5 , 51 , 12 , 14 , 7. Dựa vào thuật toán sắp xếp bằng tráo đổi để được 1 dãy tăng, hãy cho biết dãy thu được sau 1 lần duyệt dãy A trên: A. 5 , 12, 7 , 14 , 51 B. 5 , 12 , 51 , 7 , 14 C. 5 , 12, 14 , 7 , 51 D. 5 , 7 , 12 , 14 , 51 ND4.ĐL.VDT4 Trong thuật toán tìm giá trị lớn nhất của dãy số nguyên. Với N=8 và dãy A như sau: 3 7 4 8 19 15 9 12 Khi thuật toán kết thúc thì Max và i nhận giá trị là bao nhiêu? A. Max=19 tại i=1 B. Max=19 tại i=5 C. Max=19 tại i=6 D. Max=19 tại i=4 ND4.ĐT.VDC1 Cho dãy n số nguyên a1, a2, ..., an. Có thuật toán tính số M được mô tả bằng cách liệt kê như sau: Bước 1: Nhập n và dãy a1, a2, ..., an Bước 2. M 0; i 1; Bước 3. Nếu i > n thì đưa ra M rồi kết thúc, ngược lại sang bước 4. Bước 4. M M+ ai rồi quay lại bước 3. Hãy cho biết thuật toán này tính gì? A. Tìm tổng của n số đã cho; B. Tìm giá trị lớn nhất của dãy; C. Tìm giá trị nhỏ nhất của dãy; D. sắp xếp thành dãy tăng dần. ND4.ĐL.VDC1 Xây dựng các bước mô phỏng cho trường hợp cụ thể của thuật toán Tìm giá trị lớn nhất cho một dãy số nguyên dựa vào sơ đồ sau trên? Mô phỏng với N = 8 A 3 7 4 8 19 15 9 12 i Max Kết luận: . ND4.ĐL.VDC2 Xây dựng các bước mô phỏng cho trường hợp cụ thể của thuật toán Bài toán sắp xếp tăng dần dựa vào sơ đồ khối sau đây? Với dãy số: 4 5 15 23 6 12 * RÚT KINH NGHIỆM |
