Xemtailieu Tải về Giáo án tin học 10 bài 6
Giáo án Tin Học 10 Tuần:………Tiết:...……... Ngày soạn:……………… Ngày dạy:……………….. Chương I: MỘT SỐ KHÁI NIỆM CƠ BẢN CỦA TIN HỌC BÀI 6: GIẢI BÀI TOÁN TRÊN MÁY TÍNH I. Mục tiêu: Kiến thức: - Biết cách giải một bài toán trên máy tính theo các bước cụ thể. - Làm rõ hơn các khái niệm trong bài trước: bài toán, thuật toán, lệnh, chương trình, ngôn ngữ lập trình. II. Dụng cụ dạy – học: * Giáo viên : Chuẩn bị đồ dùng dạy học: + Sử dụng bảng, tranh ảnh. + Giáo Án, SGK, Sách GV. * Học sinh : xem lài những kiến thức cũ có liên quan. III. Hoạt động dạy - học: 1. Ổn định lớp. Kiểm tra sĩ số lớp (cán bộ lớp báo cáo) (1’) 2. Kiểm tra bài cũ: (6’) 1) Trình bày ưu - khuyết điểm của ngôn ngữ máy? 2) Chương trình dịch dùng để làm gì? 3) Hãy kể tên một vài ngôn ngữ lập trình bậc cao mà em biết? 3. Nội dung bài học : TG 1’ HOẠT ĐỘNG CỦA THẦY HOẠT ĐỘNG CỦA TRÒ NỘI DUNG Chúng ta đã biết máy tính là BÀI 6: GIẢI BÀI công cụ hỗ trợ cho con người TOÁN TRÊN MÁY TÍNH rất nhiều trong đời sống xã hội. Trong tin học một việc gì đó mà con người muốn máy tính thực hiện thì được gọi là bài toán. Hãy chỉ ra những ưu điểm o Nhanh, chính xác. của việc giải bài toán bằng máy o Không cần sự tham gia trực tính so với cách giải toán thông tiếp của con người… thường khác? Vậy thì việc giải một bài o Việc giải một bài toán trên toán trên máy tính sẽ được tiến máy tính thường được tiến hành theo các bước sau: hành theo các bước nào? + B1: Xác định bài toán. + B2: Lựa chọn hoặc thiết kế thuật toán. + B3: Viết chương trình. + B4: Hiệu chỉnh. Trong bài ngày hôm nay + B5: Viết tài liệu. chúng ta sẽ giới thiệu về cách giải bài toán trên máy tính. GVGD: Nguyễn Triều Thảo 1./ Xác định bài toán: 1 5’ Giáo án Tin Học 10 * Hoạt động 1: Tìm hiểu cách xác định bài toán. Xác định hai thành phần: Trước khi giải một bài toán o Tức là xác định Input và Input và Output nào đó thì trước hết ta phải xác Output. định được các thông tin mà đề cho và các thông tin đề yêu cầu thực hiện, và ta gọi là xác định bài toán. Vậy khi xác định bài toán thì ta cần làm gì? Input, Output là gì? o Input: các thông tin đã có VD: Tìm ước số chung lớn Với mỗi bài toán ta cần xác o Output: các thông tin cần nhất của hai số nguyên dương M và N. định Input, Output để từ đó tìm từ Input. + Input: hai số nguyên lựa chọn thuật toán và ngôn ngữ dương M và N. lập trình cho phù hợp. Giữa + Output: UCLN(M,N) Input - Output có mối liên hệ với nhau VD: Tìm ước số chung lớn nhất của hai số nguyên dương M và N. Xác định bài toán? 15’ o Input: hai số nguyên dương M và N. Khi xác định được bài toán o Output: ước chung lớn nhất thì kế tiếp ta cần lựa chọn và của M và N ---> UCLN(M,N). xây dựng thuật toán cho bài toán đó. * Hoạt động 2: Lựa chon hoặc thiết kế thuật toán. Đây là bước quan trọng nhất để giải một bài toán. Tức là ta phải chọn thuật toán như thế nào để giải bài toán chính xác và nhanh chóng. Nêu VD: Theo các em thì o Không. chúng ta có thể dùng thuật toán tìm UCLN để giải bài toán tìm giá trị lớn nhất Max của hai số M, N không? Vậy thì chúng ta có thể o Không. Một thuật toán chỉ dùng thuật toán của bài toán này có thể giải được các bài toán để giải được bài toán khác cùng dạng. không? Vậy để giải một bài toán thì o Một bài toán thì có thể có có bao nhiêu thuật toán? nhiều thuật toán để giải. Nhận xét, bổ sung. Từ đó ta thấy cần phải thiết o Lắng nghe. GVGD: Nguyễn Triều Thảo 2 2./ Lựa chọn hoặc thiết kế thuật toán: a./ Lựa chọn thuật toán: Tức là ta phải lựa chọn hoặc xây dựng thuật toán như thế nào để giải bài toán chính xác và nhanh chóng. Mỗi thuật toán chỉ giải được một bài toán. Một bài toán thì có thể có nhiều thuật toán để giải. Giáo án Tin Học 10 kế hoặc chọn một thuật toán phù hợp nhất để giải một bài toán. Phù hợp nghĩa là sử dụng tài nguyên ít nhất. Tài nguyên mà người ta quan tâm khi thiết kế hoặc lựa chọn thuật toán là gì? Theo các em thì tài nguyên nào được quan tâm nhiều nhất? Xét bài toán tìm kiếm có 2 dạng là tìm kiếm tuần tự và tìm kiếm nhị phân, vậy theo các em thì thời gian thực hiện cho bài toán tìm kiếm nào ít hơn? Khi thiết kế thuật toán ngoài thời gian thực hiện, số lượng ô nhớ, . . . người ta còn quan tâm đến vấn đề gì? Tìm ước số chung lớn nhất của hai số nguyên dương M và N. Ta sẽ lựa chọn thuật toán nào để giải. C1: Tìm UCLN(M,N) chính là tìm số lớn nhất mà M và N cùng chia hết Lâu vì ta phải kiểm tra từng số nguyên xem M và N có cùng chia hết hay không? C2: So sánh M và N - Nếu M=N: + Đúng UCLN(M,N)= M (hoặc N) Kết thúc. + Sai xét nếu M>N: Đúng M= M-N Sai N= N-M Quá trình này được lặp lại cho tới khi M= N UCLN(M,N) = M (hoặc N) Kết thúc. Khi lựa chọn xong thuật toán thì ta tiến hành thiết kế thuật toán bằng một trong hai cách là: liệt kê các bước hay vẽ sơ đồ khối, người ta gọi là diễn tả thuật toán. Việc diễn tả thuật toán đã được trình bày trong §4, ta xét thêm một VD là: Tìm ước số GVGD: Nguyễn Triều Thảo o Tài nguyên là thời gian thực hiện, số lượng ô nhớ, . . . o Tài nguyên được quan tâm nhiều nhất là thời gian thực hiện vì đó là dạng tài nguyên không tái tạo được. o Ta thấy bài toán tìm kiếm nhị phân cần ít thao tác hơn vì sau mỗi sau mỗi lần duyệt thì phạm vi tìm kiếm được thu hẹp một nữa. Vì thế cần ít thời gian thực hiện hơn. o Người ta còn quan tâm đến độ phức tạp của chương trình khi lựa chọn thuật toán. b./ Diễn tả thuật toán: theo 2 cách: - Cách 1: Liệt kê các bước - Cách 2: Vẽ sơ đồ khối o So sánh hai số nguyên dương M và N. Có 3 trường hợp Xây dựng thuật xảy ra: M=N, M>N, M N thì M M – N, quay lại B2. + B4: N N – M, quay lại B2. +B5: Đưa ra UCLN rồi kết thúc. Xây dựng thuật toán bằng sơ đồ khối: (SGK-T49). * Tìm UCLN(10, 25) ? o Xem SGK-T48,49 3 Giáo án Tin Học 10 chung lớn nhất của hai số Lần duyệt M N nguyên dương M và N. Vậy để Tìm UCLN 10 25 diễn tả thuật toán ta thực hiện Lần 1 10 15 theo các bước như thế nào? Lần 2 10 5 Hướng dẫn hs xây dựng Lần 3 5 5 thuật toán bằng cách liệt kê các Vậy UCLN(10, 25) = 5 bước. o Lên bảng làm theo hướng * Tìm UCLN(17, 13)? Xây dựng thuật toán bằng dẫn. sơ đồ khối. Lần duyệt M N Xét ví dụ mô phỏng cho o Lên bảng làm. Tìm UCLN 17 13 thuật toán trên, tìm UCLN(10, o Tìm UCLN(17, 13) Lần 1 4 13 25) Lần duyệt Tìm UCLN Lần 1 Lần 2 Lần 3 N 25 15 Lần duyệt 5 Tìm UCLN 5 Lần 1 Vậy UCLN(10, 25) = 5 Lần 2 Lần 3 Lần 4 Lần 5 Tìm UCLN(17, 13), gọi HS Lần 6 Lần 7 lên bảng làm. 7’ M 10 10 10 5 Sau khi đã có được thuật toán của bài toán, việc tiếp theo là phải chuyển đổi thuật toán đó sang chương trình. * Hoạt động 3: Tìm hiểu về cách viết chương trình. Viết chương trình là lựa chọn ngôn ngữ lập trình để thể hiện lại thuật toán mà ta đã xây dựng, khi viết chương trình thì nên chọn ngôn ngữ lập trình thích hợp với thuật toán mà ta đã xây dựng, viết chương trình trên ngôn ngữ nào thì phải tuân theo cú pháp của ngôn ngữ đó. Khi viết chương trình xong để máy thực hiện được thì ta phải làm gì? Ta có thể viết chương trình bằng những ngôn ngữ bậc cao nào? Trong mỗi ngôn ngữ lập trình đều có chương trình dịch giúp phát hiện lỗi và thông báo GVGD: Nguyễn Triều Thảo M 17 4 4 4 4 3 2 1 Lần 2 4 9 Lần 3 4 5 Lần 4 4 1 NLần 5 3 1 13 Lần 6 2 1 13 Lần 7 1 1 9 Vậy UCLN(17, 13) = 1 5 1 1 3./ Viết chương trình: 1 1 Vậy UCLN(17, 13) = 1 Việc viết chương trình là tổng hợp giữa việc: - Lựa chọn cách tổ chức dữ liệu. - Sử dụng ngôn ngữ lập trình để thể hiện đúng thuật toán. Khi viết chương trình thì nên chọn ngôn ngữ lập trình thích hợp với thuật toán, viết chương trình trên ngôn ngữ nào thì phải tuân theo cú pháp của ngôn ngữ đó. o Khi viết chương trình xong thì cần phải dịch sang ngôn ngữ máy để máy thực hiện. o Có thể chọn một trong các ngôn ngữ bậc cao như: Pascal, C, C++, . . tuỳ theo thuật toán thích hợp với ngôn ngữ nào. 4 Giáo án Tin Học 10 lỗi cú pháp. Ta viết chương trình cho thuật toán tìm UCLN(M, N), o Xem chương trình. giả sử ta sử dụng ngôn ngữ Pascal để thể hiện. Program Tim_UCLN; Var M, N: integer; Begin write ('Nhap M, N = ’); readln (M,N); while M N do if M > N then M :=M-N else M < N then N :=N-M; write('Uoc chung lon nhat la: ',M); 5’ readln; End. * Hoạt động 4: Tìm hiểu về cách hiệu chỉnh. Chương trình được viết không phải lúc nào cũng đảm bảo hoàn toàn đúng, do đó cần o Các bộ Input-Output này phải thử chương trình bằng các được gọi là các Test. bộ Input đặc trưng khác nhau và bằng cách nào đó ta biết trước Output, vậy các bộ Input – Output này được gọi là gì? Vậy dựa vào chương trình tìm UCLN, các em hãy đề xuất các Test và biết trước Output. o Tìm UCLN(12 ,8) Input: Nếu test có sai sót thì ta 12 và 8 Output: 4 phải sửa lại rồi chạy thử. Quá trình đó gọi là hiệu chỉnh. Sử dụng ngôn ngữ lập trình o Xem chương trình. 3’ Pascal để viết chương trình tìm UCLN(M, N). Chạy thử chương trình cho hs xem. * Hoạt động 5: Tìm hiểu cách viết tài liệu. Khi ta viết được chương trình hoàn chỉnh thì kế đó ta phải viết tài liệu, vậy tài liệu o Tài liệu phải mô tả bài toán, gồm có những gì? thuật toán, thiết kế chương trình, Nêu VD thực tế. kết quả thử nghiệm và hướng dẫn sử dụng. o Lắng nghe. 4. Củng cố: (1’) yêu cầu học sinh nhắc lại các kiến thức: GVGD: Nguyễn Triều Thảo 5 4./ Hiệu chỉnh: Sau khi viết xong chương trình cần phải thử chương trình bằng các bộ Input đặc trưng. Trong quá trình chạy thử nếu có sai sót thì ta phải sửa lại rồi chạy thử. Quá trình đó gọi là hiệu chỉnh. 5./ Viết tài liệu: Mô tả chi tiế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. Từ tài liệu này, người sử dụng đề xuất các khả năng hoàn thiện thêm. Giáo án Tin Học 10 Các bước để giải một bài toán trên máy tính 5. Dặn dò: (1’) - Trả lời các câu hỏi 1, 2, 3 trong SGK-T51 - Chuẩn bị bài mới: BÀI 7: PHẦN MỀM MÁY TÍNH GVGD: Nguyễn Triều Thảo 6 Tải về bản full