Giáo án môn Tin học 10 - Bài 6: Giải bài toán trên máy tính

Hội giảng chào mừng ngày nhà giáo việt namBài 6Giải bài toán trên máy tínhGiáo viên: Nguyễn Huyền Trang Trung tâm GDTX Ba ĐìnhGiải bài toán trên máy tínhXác định bài toánLựa chọn hoặcthiết kế thuật toánViết chương trìnhHiệu chỉnhViết tài liệu Xác định: Input, Output và quan hệ giữa chúng Ví dụ: Trong bài toán tin học, khi đề cập tới số tuổi N của một người ta phải chọn N là loại số nguyên dương, có thể chỉ rõ phạm vi giá trị của N từ 0 tới 150 Mục đích: để lựa chọn một cách thích hợp	 Thuật toán Cách thể hiện các đại lượng đã cho, các đại lượng phát sinh trong quá trình giải bài toán Ngôn ngữ lập trình1. Xác định bài toán2. Lựa chọn hoặc thiết kế thuật toánMột thuật toán chỉ giải được một bài toán nhất định, nhưng có thể có nhiều thuật toán khác nhau cùng giải một bài toánThuật toán tìm kiếm tuần tự Thuật toán tìm kiếm nhị phânBài toán tìm kiếmQuan trọng nhất(Yếu tố thời gian còn phụ thuộc: ngôn ngữ lập trình, hệ thống, cấu hình máy ) Thời gian thực hiện nhanh (Số lượng các phép toán ít) Tốn ít bộ nhớ Dễ hiểu Trình bày dễ nhìn2. Lựa chọn hoặc thiết kế thuật toána) Tiêu chuẩn lựa chọn thuật toánVí dụ: Tìm ước chung lớn nhất (ƯCLN) của hai số nguyên dương M và N2. Lựa chọn hoặc thiết kế thuật toánb) Diễn tả thuật toána) Tiêu chuẩn lựa chọn thuật toán Cách liệt kê Sơ đồ khối Xác định bài toán Input: Cho 2 số nguyên dương M và N Output: ƯCLN (M , N) ý tưởng: Sử dụng những điều đã biết sau: Nếu M = N thì giá trị chung đó là ƯCLN của M và N Nếu M N thì ƯCLN (M , N) = UCLN ( M – N , N)Ví dụ: Tìm ƯCLN (M , N) Thuật toán Cách liệt kêBước 1. Nhập M, NBước 2. Nếu M = N thì lấy giá trị chung này làm ƯCLN rồi chuyển đến bước 5Bước 3. Nếu M > N thì M  M – N rồi quay lại bước 2Bước 4. Nếu M N ? SaiM  M – NĐúngN  N – MSai Thuật toán Cách liệt kêVí dụ mô phỏng việc thực hiện thuật toánTìm ƯCLN (M , N)M = 10N = 25M = 10N = 15N  N – MLần 1M = 10N = 5N  N – MLần 2N  N – MLần 3M = 5N = 5Kết quảƯCLN (10 , 25) = 5Ví dụ mô phỏng việc thực hiện thuật toánTìm ƯCLN (M , N)N = 7M = 2Lần 1N N - MN = 5M = 2Lần 2N N - MN = 3M = 2Lần 3N N - MN = 1M = 2Lần 4M M - NN = 1M = 1Kết quảƯCLN (7 , 2) = 1Ví dụ mô phỏng việc thực hiện thuật toánTìm ƯCLN (M , N)N = 7M = 2Lần 1N N - MN = 5M = 2Lần 2N N - MN = 3M = 2Lần 3N N - MN = 1M = 2Lần 4M M - NN = 1M = 1Kết quảƯCLN (7 , 2) = 13. Viết chương trình Là chọn cách tổ chức dữ liệu và sử dụng ngôn ngữ lập trình để diễn đạt đúng thuật toán. Chú ý: Khi viết chương trình trong ngôn ngữ nào thì phảituân thủ đúng quy định ngữ pháp của ngôn ngữ đó. Chương trình dịch chỉ có thể phát hiện và thông báo các lỗi về mặt ngữ nghĩa4. Hiệu chỉnha) Mục đích: Kiểm tra chương trình để phát hiện và sửa lỗib) Nội dung: + Thử chương trình bằng cách thực hiện nó với một số bộ Input tiêu biểu (phụ thuộc vào đặc trưng của bài toán) và bằng cách nào đố ta đã biết trước Output. (Các bộ Input và Output tương ứng này được gọi là các Test) + Nếu có sai sót, ta sửa chương trình rồi thử lại + Nếu kết quả hiệu chỉnh cho thấy ngôn ngữ lập trình hoặc thuật toán không phù hợp ta phải quay lại lựa chọn hay thiết kế thuật toán4. Hiệu chỉnha) Mục đíchb) Nội dung c) Ví dụ Giải PT bậc hai ax2 + bx + c = 0 > 0: a = 1, b = - 5, c = 6 (Chương trình dưa ra 2 nghiệm phân biệt = 0: a = 1, b = - 4, c = 4 (chương trình đưa ra 1 nghiệm) < 0: a = 1, b = 4, c = 8 (chương trình thông báo PT vô nghiệm)Hãy thảo luận tìm ra các Test tiêu biểu để kiểm tra chương trình : Giải phương trình ax + b = 04. Hiệu chỉnha) Mục đíchb) Nội dung c) Ví dụ 5. Viết Tài liệu Nội dung: Mô tả chi tiết toàn bộ bài toán, thuật toán, thiết kế chương trình, kết quả thử nghiệm và hướng dẫn sử dụng Mục đích: + Hỗ trợ người sử dụng chương trình + Đề xuất những khả năng hoàn thiện thêmDặn dò, Hướng dẫn về nhà Ghi nhớ: Các bước giải bài toán trên máy tính Tiêu chuẩn lựa chọn thuật toán Nội dung và mục đích của bước hiệu chỉnh Làm bài tập 3 (SGK/51)Hướng dẫn: vận dụng thuật toán giải phương trình bậc hai đã biết