Giáo án Tin học 10 - Tiết 10 - Bài 4: Bài toán và thuật toán

bài 4: Bài toán và thuật toán (Tiết 10) Ngày soạn: 02/10/07 I- Mục đích và yêu cầu. - Khái niệm thuât toán, một số vi dụ của bài toán. VD cụ thể: Tìm giá trị lớn nhất của một dãy số nguyên. - Phương pháp : Diễn giảng, giải thích - Đồ dùng: Sơ đồ, GAĐT II- Nội dung. 1. ổn định tổ chức lớp. Lớp Sĩ số Vắng Ghi chú 10A5 42 10A6 10A7 2. Kiểm tra bài cũ. 3. Bài mới. Nội dung Hoạt động của GV và HS 1. Khái niệm bài toán Bài toán là việc nào đó ta muốn máy tính thực hiện. - Khi dùng máy tính giải bài toán, ta cần quan tâm đến hai yếu tố: - Đưa vào máy thông tin gì (Input) và cần lấy ra thông tin gì (Output). Bài toán trong tin học có tính mềm dẻo và được mở rộng. Nhằm đáp ứng nhu cầu của đời sống gắn với lao động sản xuất của con người chứ không đơn thuần là tính toán GV: Bài toán là 1 khái niệm quen thuộc đã được biết trong toán học VD: Đưa một dòng chữ ra màn hình, giải phương trình bậc hai, quản lí cán bộ của một cơ quan,... là những ví dụ về bài toán. GV: Để phát biểu một bài toán, ta cần phải trình bày rõ Input và Output của bài toán đó và mối quan hệ giữa Input và Output.  Ví dụ 1. 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ụ 2. 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. Ví dụ 3. Bài toán kiểm tra tính nguyên tố Input: Số nguyên dương N; Output: "N là số nguyên tố" hoặc "N không là số nguyên tố". Ví dụ 4. 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. 2. 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 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 ấy, từ Input của bài toán, ta nhận được Output cần tìm. VD: GPT B2( GV liệt kê và vẽ sơ đồ khối GV: ước chung lớn nhất ? HS: Là số lớn nhất mà hai số M, N chia hết. GV: Nêu cách giải PTB2 tổng quát? HS: Tính Delta? GV: Số nguyên tố là số như thế nào? HS: GV: H/s lấy một số ví dụ khác chỉ rõ Input và Output Qua các ví dụ trên, ta thấy các 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. GV: Việc cho một bài toán là mô tả rõ Input và Output cần tìm. Vấn đề là: Làm thế nào để tìm ra Output?  Ví dụ. Tìm giá trị lớn nhất của một dãy số nguyên ã Xác định bài toán - Input: Số nguyên dương N và dãy N số nguyên a1,..., aN. - Output: Giá trị lớn nhất Max của dãy số. ã ý tưởng: - 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. Hình 1 Đúng Đúng Sai Nhập N và dãy a1,..., aN Max ơ ai ai > Max? i > N ? Max ơ a1, i ơ 2 Đưa ra Max rồi kết thúc i ơ i + 1 Sai ã Thuật toán. Thuật toán giải bài toán này có thể được mô tả theo cách liệt kê như sau: Bước 1. Nhập N và dãy a1,..., aN; Bước 2. Max ơ a1, i ơ 2; Bước 3. Nếu i > N thì đưa ra giá trị Max rồi kết thúc; Bước 4. Bước 4.1. Nếu ai > Max thì Max ơ ai; Bước 4.2. i ơ i + 1 rồi quay lại bước 3; + Trong thuật toán trên, i là biến chỉ số các số hạng của dãy và có giá trị nguyên thay đổi từ 2 đến N + 1. + Mũi tên ơ trong thuật toán trên được hiểu là gán giá trị của biểu thức bên phải cho biến ở bên trái mũi tên. Ví dụ i ơ i + 1 được hiểu là đặt cho i giá trị mới bằng i + 1. 4. củng cố: - Nắm được hai cách diễn giải theo cách liệt kê và sơ đồ khối 5. Bài tập về nhà: Bài tập: 1, 2, 3, 4, 5, 6 SGK (27) III. Rút kinh nhgiệm giờ dạy.