Tuần 5,6 Ngày soạn: 04/09 Tiết 10,11,12 Ngày dạy: §4. BÀI TOÁN VÀ THUẬT TOÁN I. Mục tiêu 1. Kiến thức - Học sinh biết khái niệm về Bài toán và thuật toán, các tính chất của thuật toán - Học sinh chỉ ra được Input và Output của mỗi bài toán đưa ra. 2. Kỹ năng - Hiểu và nhận biết được Input và Output trong mỗi bài toán. 3. Thái độ - Chú ý nghe giảng, hăng hái phát biểu ý kiến. - Có thái độ học tập nghiêm túc. II. Chuẩn bị của giáo viên và học sinh 1. Chuẩn bị của giáo viên: SGK, Giáo án, Tài liệu tham khảo. 2. Chuẩn bị của học sinh: SGK, vở ghi III. Phương pháp: Hướng dẫn giảng giải, minh họa trực quan, nêu câu hỏi để học sinh thảo luận trả lời. Hoạt động nhóm, hoạt động cá nhân IV. Hoạt động dạy - học 1. Ổn định tổ chức 2. Kiểm tra bài cũ: 3. Nội dung bài mới Hoạt động của thầy và trò Nội dung GV: Đặt vấn đề: Để 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à thuật toán và bài toán. Đó chính là nội dung của bài học hôm nay. GV: Trong toán học "Bài toán" được 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ữ liệu đã có phải tìm ra kết quả 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 ? HS: Trả lời. GV: Trong nhà trường có phần mềm quản lý học sinh : Nếu ta yêu cầu đưa ra những học sinh có điểm trung bình từ 7 trở lên, đó là bài toán. Hay đơn gian hơn yêu cầu máy tính cho ra kết quả của một phép tính nhân, chia,... Đó cũng là bài toán. Vậy bài toán là gì ? HS: Suy nghĩ và trả lời. GV: Để giải được một bài toán thì công việc đầu tiên ta cần làm là gì ? HS: Cụng việc đầu tiên là đi xỏc định đâu là dữ kiện đó cho và đâu là cái cần tìm. 1. Bài toán * Khái niệm: Bài toán là những việc mà con người muốn máy tính thực hiện. * Các yếu tố: Khi máy tính giải bài toán cần quan tâm đến 2 yếu tố: - Input (Thông tin đưa vào máy) - Output (Thông tin muốn lấy ra từ máy) GV: Ta cần đi xác định đầu vào (Input) và đầu ra (Output) của bài toán. Input là thông tin được đưa vào máy, Output là thông tin cần lấy ra khỏi máy. nput của bài toàn là gì ? Output của bài toàn là gì ? HS: Đứng tại chỗ trả lời câu hỏi GV: Cho học sinh lấy thêm ví dụ và phân tích đâu là Input và đâu là Output. HS: Trả lời. GV: Muốn máy tính đưa ra được Output từ Input đã cho thì cần phải có chương trình, mà muốn viết chương trình thì cần phải có thuật toán. Vậy thuật toán là gì ? HS: Trả lời. GV: Giải thích thêm về các khái niệm như: Dãy hữu hạn các lệnh, sắp xếp theo một trình tự nhất định. HS: Lắng nghe và ghi nhớ. GV: Đưa ra ví dụ tìm UCLN của 2 số M và N. Xác định Input và Output của bài toán. HS: Đứng tại chỗ xác định Input và Output GV: Ghi thuật toán lên bảng GV: Lấy ví dụ 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 B2: M=12-8=4, N=8-->N>M B3: M=4, N=8-4=4 --> M=N => UCLN(M,N)=4 GV: Cách viết thuật toán theo từng bước như trên gọi là cách liệt kê, còn có cách làm khác đó là dùng Sơ đồ khối. HS: Lắng nghe. GV: Lấy lại ví dụ tìm UCLN của 2 số M,N GV: Vẽ sơ đồ thuật toán lên bảng. Chỉ cho học sinh thấy các bước của thuật toán được mô tả trong sơ đồ. 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. GV: Xoá các ghi chú Đ và S trên sơ đồ, yêu cầu 1 học sinh viết lại và giải thích vì sao ? HS: Lên bảng điền lại các ghi chú và giải thích vì sao lại điền như thế. 2. Thuật toán - Khái niệm thuật toán: Là một dãy 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 sau khi thực hiện dãy thao tác đó, từ Input của bài toán này ta nhận được Output cần tìm. - Tác dụng của thuật toán: Dùng để giải một bài toán. - Ví dụ: Thuật toán tìm UCLN của 2 số M, N. * Xác định bài toán + Input: M, N + Ontput: UCLN(M, N) * ý tượng: - Nếu M = N thì gán UCLN=M - Nếu M > N thì gán M = M - N - Nếu M < N thì gán N = N - M * Thuât toán: (Theo cách liệt kê từng bước) -B1: Nhập M, N -B2: Nếu M = N thì UCLN = M -B3: Nếu M > N thì thay M= M - N, rồi quay lại B2. -B4: Nếu M<N thì thay N = N - M rồi quay lại B2 -B5: Gán UCLN là M và kết thúc. Ngoài ra thuật toán còn được diễn tả bằng sơ đồ khối với các qui định: - Hình elip: Các thao tác nhập, xuất dữ liệu - Hình thoi: Các thao tác so sánh - Hình chữ nhật: Các phép toán - Mũi tên: Qui định trình tự các thao tác * Thuật toán được mô tả bằng sơ đồ khối: GV: Giới thiệu các tính chất của thuật toán. HS: Lắng nghe và ghi nhớ. Nhập M và N M=N ? M>N ? Đưa raUCNN là M và Kết thúc N <= N - M M <= M - N Đúng Đúng Sai Sai Các tính chất của thuật toán: + Tính dừng: + Tính xác định: + Tính đúng đắn 4. Củng cố: - Khái niệm bài toán trong tin học - Các yếu tố cần xác định trong việc giải bài toán - Thuật toán: Cách giải bài toán - Diễn tả thuật toán 5. Bài về nhà - Nêu thêm 5 ví dụ về bài toán trong tin học - Làm lại bài tập ví dụ đã chữa, lấy thêm một số ví dụ khác tương tự. - Đọc trước các mục còn lại để giờ sau học tiếp bài : Bài toán và thuật toán. Rút kinh nghiệm:
• Nội dung chính - Khái niệm về bài toán và xác định bài toán - Quá trình giải bài toán trên máy tính - Thuật toán và cách thức mô tả thuật toán 1. Xác định bài toán - Khái niệm bài toán: là 1 công việc hay 1 nhiệm vụ cần được giải quyết. - Xác định bài toán là đi xác định điều kiện cho trước và xác định kết quả cần thu được. - Ví dụ: Tính diện tích tam giác + Điều kiện cho trước: 3 cạnh của tam giác + Kết quả cần thu được: Diện tích tam giác 2. Quá trình giải bài toán trên máy tính - Máy tính hoạt động dưới sự chỉ đạo của con người, để giải quyết 1 bài toán trên máy tình là đưa cho máy tính dãy hữu hạn các thao tác đơn giản mà nó có thể thực hiện để từ các điều kiện cho trước, ta được kết quả cần tìm. - Khái niệm thuật toán: các thao tác cần thiết để giải quyết 1 bài toán.  - Quá tình giải bài toán gồm các bước: + B1: Xác định bài toán, bao gồm xác định điều kiện cho trước và xác định kêt quả cần đạt được + B2: Mô tả thuật toán, liệt kê các thao tác cần thực hiện. + B3: Viết chương trình, dùng thuật toán vừa viết ra chuyển thành chương trình để máy tính có thể hiểu và thực hiện. 3. Mô tả thuật toán - Xét ví dụ: Pha trà mời khách INPUT: Trà, nước sôi, ấm và chén. OUTPUT: Chén trà đã pha để mời khách + B1: Tráng ấm, chén bằng nước sôi + B2: Cho trà vào ấm + B3: Rót nước sôi vào ấm và đợi khoảng 3 đến 4 phút. + B4: Rót trà ra chén để mời khách. - Khái niệm thuật toán: là dãy các thao tác cần thực hiện theo 1 trình tự xác định để thu được kết quả cần thiết từ những điều kiện cho trước. - Khái niệm mô tả thuật toán: là việc liệt kê các bước thực hiện công việc( như ví dụ pha trà). Các bước của thuật toán thực hiện tuần tự từ trên xuống dưới. 4. Một số ví dụ về thuật toán Ví dụ 1: một hình A được ghép từ hình chữ nhật với chiều rộng 2a, chiều dài b và 1 hình bán nguyệt bán kính a như hình 5.2 INPUT: các số a là ½ chiều rộng của hình chữ nhật và là bán kính của hình bán nguyệt, b là chiều dài của HCN. OUTPUT: Diện tích của A Thuật Toán: B1: tính S hình chữ nhật, S1 = 2a∗b; B2: tính S hình bán nguyệt, S2 = πa2/2; B3: tính S tổng, S = S1 + S2; Ví dụ 2: Tính tổng của 100 số tự nhiên đầu tiên INPUT: Dãy 100 số tự nhiên đầu tiên: 1, 2, …, 100. OUTPUT: Giá trị tổng 1 + 2 + … + 100. Thuật toán: - B1: SUM 0; I 0. - B2: SUM SUM + I; I I + 1. - B3: nếu I ≤ 100, thì quay lại bước 2. Ngược lại, thông báo giá trị SUM và kết thúc thuật toán. Ví dụ 3: Đổi giá trị của 2 biến x và y., INPUT: Hai biến x, y có giá tri tương ứng là a và b OUTPUT: Hai biến x, y có giá trị tương ứng là b và a Thuật Toán: - B1: z := x, khi đó z có giá trị là a - B2: x := y, khi đó x có giá trị là b - B3: y := z, khi đó y có giá trị là a. Ví dụ 4: Cho hai số thực a, b. Hãy cho biết kết quả so sánh hai số đó dưới dạng ″a lớn hơn b″, ″a nhỏ hơn b″ hoặc ″a bằng b″. INPUT: hai số thực a và b OUTPUT: kết quả so sánh Thuật Toán: - B1: Nếu a >b, kết quả là ″a lớn hơn b″ và chuyển đến Bước 3 - B2: Nếu a < b, kết quả là "a nhỏ hơn b"; ngược lại, kết quả là ″a bằng b″ - B3: Kết thúc thuật toán Ví dụ 5: Tìm số lớn nhất trong dãy các số A1, A2,… An cho trước. INPUT: Dãy A các số A1, A2,.. An ( n ≥ 1) OUTPUT: Giá trị MAX = max{A1, A2,..An} Thuật Toán: - B1: MAX := A1, I := 1. - B2: Nếu Ai > MAX, gán MAX := Ai. - B3: I := i+1. - B4: Nếu I ≤ n, quay lại bước 2. - B5: Thông báo giá trị MAX và kết thúc thuật toán. Xem thêm các bài Lý thuyết và câu hỏi trắc nghiệm Tin học lớp 8 có đáp án hay khác: Xem thêm các loạt bài Để học tốt Tin học 8 hay khác:
Giới thiệu kênh Youtube VietJack
Đã có app VietJack trên điện thoại, giải bài tập SGK, SBT Soạn văn, Văn mẫu, Thi online, Bài giảng....miễn phí. Tải ngay ứng dụng trên Android và iOS.
Nhóm học tập facebook miễn phí cho teen 2k8: fb.com/groups/hoctap2k8/ Theo dõi chúng tôi miễn phí trên mạng xã hội facebook và youtube:Loạt bài Giải bài tập Tin học 8 | Soạn Tin học lớp 8 | Trả lời câu hỏi Tin học 8 của chúng tôi được biên soạn bám sát nội dung sgk Tin học lớp 8. Nếu thấy hay, hãy động viên và chia sẻ nhé! Các bình luận không phù hợp với nội quy bình luận trang web sẽ bị cấm bình luận vĩnh viễn. ly-thuyet-trac-nghiem-tin-hoc-8.jsp |
