Giáo án Tin - Giải bài toán trên máy tính

BÀI GIẢNG TIN HỌC 10 Giáo viên hướng dẫn: Thầy Trần Doãn Vinh Sinh viên thực hiện: Đào Ngọc Hà K56A-CNTT Bài 6 GIẢI BÀI TOÁN TRÊN MÁY TÍNH MỤC TIÊU, PHƢƠNG TIỆN KIỂM TRA BÀI CŨ NỘI DUNG BÀI GIẢNG CỦNG CỐ KIẾN THỨC BÀI TẬP VỀ NHÀ Mục tiêu, phƣơng tiện Mục tiêu: Giới thiệu cách dùng máy tính để giải bài toán. Củng cố và làm rõ hơn các khái niệm: bài toán, thuật toán, dữ liệu, lệnh, ngôn ngữ lập trình và chƣơng trình. Giúp học sinh hiểu về ứng dụng quan trọng của máy tình là giải quyết bài toán. Giúp học sinh nắm đƣợc nội dung cụ thể các bƣớc cần thực hiện khi giải một bài toán trên máy tính. Phƣơng tiện: Phƣơng pháp: kết hợp các phƣơng pháp nhƣ: thuyết trình, vấn đáp, vẽ hình minh họa,… Phƣơng tiện học tập: sách giáo khoa, máy tính, máy chiếu,… Kiểm tra bài cũ Em hiểu ngôn ngữ lập trình là gì? Em có biết những ngôn ngữ lập trình nào? Trả lời: - Ngôn ngữ để viết chƣơng trình đƣợc gọi là ngôn ngữ lập trình. - Một số ngôn ngữ lập trình: Ngôn ngữ máy, hợp ngữ, ngôn ngữ bậc cao. GIẢI BÀI TOÁN TRÊN MÁY TÍNH 1. Xác định bài toán 2. Lựa chọn hoặc thiết kế thuật toán 3. Viết chƣơng trình 4. Hiệu chỉnh 5. Viết tài liệu 1. Xác định bài toán  Mỗi bài tóan đặc tả bởi 2 thành phần: Input và Output.  Xác định bài toán là xác định rõ hai thành phần này và mối quan hệ giữa chúng.  Ví dụ: đề cập đến số nguyên dƣơng N, là điểm số của học sinh, thì pham vi giá trị của N là từ 0 đến 10, từ đó lựa chọn kiểu dữ liệu thích hợp thể hiện N. b. Diễn tả thuật toán Ví dụ: Tìm ƣớc chung lớn nhất (ƢCLN) của hai số nguyên dƣơng M và N  Xác định bài toán: - Input: Cho M, N - Output: ƢCLN(M,N)  Ý tưởng: - Nếu M=N thì gía trị chung đó là ƢCLN(M,N) - Nếu M<N thì ƢCLN(M,N)= ƢCLN(M,N-M) - Nếu M>N thì ƢCLN(M,N)= ƢCLN(M-N,N)  Thuật toán: Cách liệt kê •Bƣớc 1: Nhập M, N. •Bƣớc 2: Nếu M=N thì lấy giá trị chung làm ƢCLN rồi chuyển đến bƣớc 5. •Bƣớc 3: Nếu M>N thì M M-N rồi quay lại bƣớc 2. •Bƣớc 4: N N-M rồi quay lại bƣớc 2. •Bƣớc 5: Đƣa ra kết quả ƢCLN rồi kết thúc. 2. Lựa chọn hoặc thiết kế thuật toán a. Lựa chọn thuật toán b. Diễn tả thuật toánn a. Lựa chọn thuật toán  Mỗi bài toán có thể có nhiều thuật toán, nhƣng mỗi thuật toán chỉ giải một bài toán nào đó.  Tài nguyên lựa chọn một thuật toán tối ƣu: thời gian thực hiện, số lƣợng ô nhớ,… Tài nguyên thời gian la quan trọng nhất.  Ngoài ra còn một tiêu chí khá đƣợc quan tâm là chƣơng trình ứng với thuật toán lựa chọn là ít phức tạp nhất. Sơ đồ khối Là công cụ giúp ta diễn tả thuật toán một cách trực quan. Sơ đồ khối đƣợc tạo bởi 4 loại khối nối với nhau bằng các cung. Và chúng ta áp dụng sơ đồ khối để tìm thuật giải UCLN Khối bắt đầu Khối thao tác Khối điều kiện Khối kết thúc Cung Sơ đồ khối Nhập M,N Đưa ra M rồi kết thúc M=N? M>N? N <- N-M M <- M-N Mô tả ví dụ ƢCLN(25,10)=5 M=10 N=25 N=15 N=5 N=5 M=10 M=10 M=5 N <- N-M N <- N-M M<- M-N 3. Viết chƣơng trình  Viết chƣơng trình là tổng hợp giữa việc lựa chon 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ọn ngôn ngữ lập trình hoặc phần mềm chuyên dụng thích hợp với thuật toán.Phải tuân theo quy định ngữ pháp của ngôn ngữ đó.  Chú ý: Chƣơng trình dịch chỉ có thể thông báo và phát hiện lỗi về mặt cú pháp. 4. Hiệu chỉnh Để giải quyêt lỗi chƣa phát hiện đƣợc cần phải thử chƣơng trình bằng cách thực hiện nó với các Input tiêu biểu phụ thuộc vào đặc thù của bài toán và bằng cách nào đó ta biết trƣớc Output. Chúng đƣợc gọi là Test. Nếu có sai sót ta phải sửa lại chƣơng trình rồi thử lại. Quá trình này đƣợc gọi là hiệu chỉnh. Ví dụ: Kiểm chứng tính đúng đắn của chƣơng trình giải phƣơng trình bậc nhất: ax+b=0, có thể sử dụng bộ Input nhƣ sau: +a=0: b=0(chƣơng trình vô định),b0 (chƣơng trình vô nghiệm) +a0:b(chƣơng trình có nghiệm duy nhất). 5. Viết tài liệu Tài liệu phải mô tả 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. Chú ý các bƣớc trên có thể lặp đi lặp lại nhiều lần cho đến khi ta cho rằng chƣơng trình đã làm việc đúng đắn và hiệu quả . Củng cố kiến thức Ghi nhớ các bƣớc để giải bài toán trên máy tính: Xác định bài toán Lựa chọn hoặc thiết kế thuật toán. Viết chƣơng trình. Hiệu chỉnh. Viết tài liệu. Bài tập về nhà 1. Đọc trƣớc nội dung của bài tiếp theo. 2. Làm các bài tập sách giáo khoa. 3. Ghi nhớ các bƣớc giải một bài toán trên máy tính.