Bài giảng Một số khái niệm cơ bản về tin học

nữa Trả lời: *Cách liệt kê: Bước 1: Nhập N và các số hạng a1, a2,...,an Bước 2: m=n Bước 3: Nếu m<2 ( tức dãy chỉ có 1 số hạng ) thì đưa ra kết quả Bước 4: Giảm giá trị m một đơn vị (mß m -1), iß0 Bước 5: ißi +1 Bước 6: Nếu i>m ( đã duyệt qua lượt thứ 1) thì quay lại bước 3 Bước7: Nếu ai>ai+1 thì hoán đổi ai cho ai+1 ( GV đưa ra mô hình để minh hoạ cho trường hợp này) Bước 8: quay lại bước 5. Một HS lên bảng vẽ sơ đồ khối của bài toán HS vẽ sơ đồ khối Gọi học sinh lên chạy thử thuật toán bằng tay với dãy gồm các số sau: 8 10 2 1 5 4 Giáo viên nhận xét kết quả Cho HS vẽ sơ đồ khối vào vở 4.Hoạt động củng cố:(1-3’): Nhắc lại thuật toán sắp xếp bằng trao đổi bằng 2 cách liệt kê và sơ đồ khối. 5.Hướng dẫn học sinh về nhà:(2-3’) Học các nội dung: Thuật toán sắp xếp bằng trao đổi. Bài tập:6/SGK, 1.33, 1.38, 1.42/Sách bài tập Chuẩn bị bài mới: Thuật toán tìm kiếm tuần tự và thuật toán tìm kiếm nhị phân Ngày soạn: TIẾT 13: BÀI TOÁN VÀ THUẬT TOÁN (TIẾT 5) I.MỤC TIÊU: Qua bài học, học sinh cần nắm được: 1.Về kiến thức: -Biết khái niệm bài toán và thuật toán, các đặc trưng chính của thuật toán. -Hiểu cách biễu diễn thuật toán bằng sơ đồ khối và ngôn ngữ liệt kê. -Hiểu một số thuật toán thông dụng. 2.Về kỹ năng:Xây dưng được thuật toán giải một số bài toán đơn giản bằng sơ đồ khối hoặc ngôn ngữ liệt kê. 3.Về tư duy, thái độ: -Có ý thức xây dựng bài học -Biết xây dựng thuật toán tối ưu: ít tốn thời gian và bộ nhớ. II.CHUẨN BỊ CỦA GIÁO VIÊN VÀ HỌC SINH: 1.Chuẩn bị của giáo viên: - Đồ dùng dạy học: Máy tính điện tử -Giáo án, giáo án điện tử 2.Chuẩn bị của học sinh:Những khái niệm và kiến thức đã học. III.PHƯƠNG PHÁP DẠY HỌC: Giải quyết vấn đề IV.TIẾN HÀNH BÀI DẠY: 1. Ổn định lớp:(2’) Vắng: Trể: 2.Kiểm tra bài củ: (3 - 6’): 1.Trình bày thuật toán sắp xếp bằng trao đổi theo phương pháp liệt kê từng bước? 2. Trình bày thuật toán sắp xếp bằng tráo đổi theo phương pháp dung sơ đồ khối? 3.Dạy bài mới:(30 - 37’) Hoạt động của giáo viên Hoạt động của học sinh 3.Ví dụ 3: Bài toán tìm kiếm Cho dãy A gồm N số nguyên khác nhau a1, a2,...,an và một số nguyên K. Cần biết có hay không chỉ số i (1<=I <=N) mà ai = k. Nếu có hãy cho biết chỉ số đó. Câu hỏi: Xác định dữ liệu vào và ra của bài toán. i)Trường hợp 1: Dãy A chưa được sắp xếp a)Xác định bài toán: Input: Dãy A gồm N số nguyên khác nhau a1, a2, ...., an và số nguyên K. Output: Chỉ số I mà ai = K hopặc thông báo không có số hạng nào của dãy A có giá trị bằng K Câu hỏi: Để tìm kiếm 1 quyển sách nào đó ở trong thư viện ta phải làm thế nào? b) Ý tưởng: -Lần lượt kiểm tra từ số hạng thứ nhất. -So sánh giá trị số hạng đang xét với khoá k. có hai trường hợp xảy ra: +Số hạng đang xét có giá trị bằng khoá à thông báo vị trí mà số k đang đứng và kết thúc. +Số hạng đang xét không trung với khoá à tiếp tục kiểm tra số hạng tiếp thao cho đến cuối dãy. Nếu cho đến cuối dãy không có số hạng nào trùng với khoá thì kết luận không có số hạng nào bằng khoá. GV: Gọi Hs lên bảng vã sơ đồ khối của bài toán. c)Thuật toán tìm kiếm tuần tự: *Cách liệt kê: Bước 1: Nhập N, các số hạng a1, a2, ...., an và khoá K Bước 2:iß1 Bước 3: Nếu ai = k thì thông báo chỉ số I rồi kết thúc. Bước 4: Iß i+1 Bước 5: Nếu i>N thì thông báo dãy A không có số hạng nào có giá trị bằng k, rồi kết thúc Bước 6: Quay lại bước 3 *Sơ đồ khối: Câu hỏi: Khi dãy đã được sắp xếp thì thuật toán trên có nhược điểm gì? GV: Khi dãy đã được sắp xếp thì ta tìm kiếm như thé nào? ii)Trường hợp 2: Dãy A đã được sắp xếp( chiều tăng dần) a)Xác định bài toán: Input: Dãy A là dãy tăng gồm N số nguyên khác nhau a1,a2,..., an và số nguyên k Output: Chỉ số I mà ai = k hoặc thông báo không có số hạng nào của dãy A có giá trị bằng k. b) Ý tưởng: Sử dụng tính chất dãy A là dãy tăng -Tìm cách thu hẹp dần phạm vi tìm kiếm sau mỗi lần so sánh với số hạng được chọn. Để làm được điều đó, ta chọn số hạng agiữa ở giữa dãy để so sánh với K. Trong đó: Giữa = [(n+1)/2]. Khi đó chỉ xảy ra 3 trường hợp. -Nếu agiữa = k thì giữa là chỉ số cần tìm. -Nếu agiữa > k à việc tìm kiếm đươc lặp lại tương tự trên đoạn a1, a2,...., agiữa -1 -Nếu agiữa < k à việc tìm kiếm được lặp lại tương tự trên đoạn agiữa + 1, ...., an Quá trình trên sẽ được lặp lại cho đến khi hoặc đã tìm thấy khoá k hoặc phạm vi tìm kiếm bằng rỗng. GV: Giải thích kỹ các thành phần trong thuật toán bằng một dãy số cụ thể. GV: Gọi một học sinh lên vẽ sơ đồ khối? c)Thuật toán tìm kiếm nhị phân: Sai Không có số hạng k Đúng Cuối ß Giữa -1 1 Đầu > Cuối Đúng Đầu ß Giữa + 1 Sai agiữa > k *Cách liệt kê: Bước 1: Nhập n, các số hạng a1, a2, ...., an và khoá k. Bước 2: Đầu ß 1, Cuối ß n Bước 3: Giữa ß [(Đầu + cuối )/2] Bước 4: Nếu agiữa = k thì thông báo chỉ số giữa, rồi kết thúc. Bước 5: Nếu agiữa > k thì đặt cuối = giữa - 1 à bước 7 Bước 6: Đầu ß Giữa + 1 Bước 7: Nếu Đầu > Cuối thì thông báo dãy A không có số hạng nào có giá trị bằng k rồi kết thúc. Bước 8: Quay lại bước 3 *Sơ đồ khối: Trả lời: Input: Dãy A gồm N số nguyên khác nhau a1, a2, ...., an và số nguyên K. Output: Chỉ số I mà ai = K hopặc thông báo không có số hạng nào của dãy A có giá trị bằng K : Trả lời: HS trả lời. GV khái quát lại và đi đến ý tưởng của bài toán tìm kiếm theo kiểu tuần tự *Sơ đồ khối Nhập N, dãy a1,a2,..an và k Iß1 Đưa ra i kết thúc Đúng Ai =k Sai Iß I + 1 Sai I>N Đúng Thống báo dãy A không có số hạng có giá trị K Trả lời: Thuật toán không tối ưu do không tiết kiệm được thời gian tìm kiếm Trả lời: HS trả lời. GV đưa ra nhạn xét để hướng dẫn HS hình thành thuât toán tìm kiếm nhị phân. Giả sử ta có: A: 1 5 6 9 15 17 18 19 20 K= 8 Kiểu tra lần 1: giữa = [(1+ 9)/2 ]= 5 a5 = 15 > k =8 àCuối = 5 - 1 = 4 Kiểm tra lần 2: Giữa = [(1+4)/2] = 2 A2 = 5<k = 8 à Đầu = 2 + 1 = 3 Kiểm tra lần 3: Giữa = [(3 + 4)/2]=3 A3 = 6 <k = 8 à Đầu = 3 + 1 = 4 Kiểm tra lần 4: Giữa = [(4+4)/2] = 4 A4 = 9>k=8 à Cuối = 4 - 1 = 3 Đầu = 4 > Cuối = 3: Kết thúc: Thông báo không tìm thấy K HS vẽ sơ đồ khối. *Sơ đồ khối Nhập N, dãy a1,a2,..an và k Đầuß1, Cuối = N Giữa = [(Đầu + Cuối )/2] Đúng Sai agiữa = k Đúng Đưa ra giữa rồi kết thúc 4.Hoạt động củng cố:(1-3’) Nhắc lại thuật toán tìm kiếm bằng 2 phương pháp: tuần tự và nhị phân 5.Hướng dẫn học sinh về nhà:(2-3’) Học các nội dung: Thuật toán tìm kiếm tuần tự và tìm kiếm nhị phân Bài tập:7/SGK,1.34,1.351.40,1.42,1.43 à1.48/SBT Chuẩn bị bài mới: Làm các bài tập GV đã nêu Ngày soạn: TIẾT 14: BÀI TẬP I.MỤC TIÊU: Qua bài học, học sinh cần nắm được: 1.Về kiến thức: Rèn luyện khả năng xác định yêu cầu của một bài toán trong tin học (Input, Output). - Rèn luyện khả năng phân tích bài toán, xây dựng ý tưởng và giải thuật để giải quyết bài toán. -Rèn luyện khả năng chuyển bài toán về mặt toán học thành thuật toán giải quyết bài toán đó trong Tin học (Thuật toán có tính khả thi). -Giúp HS mô tả thuật toán bằng sơ đồ khối để dễ dàng kiểm soát bài toán -Giúp HS nắm vững hơn nữa các thuật toán cơ bản trong việc giải quyết các bài toán sắp xếp và tìm kiếm. - Nắm được các yêu cầu khi xây dựng một thuật toán (các tính chất cần thiết của một thuật toán). -HS có sự chuẩn bị trước về ý tưởng giải thuật. -HS trình bày được thuật toán giải quyết các bài toán đơn giản. 2.Về kỹ năng:Xây dưng được thuật toán giải một số bài toán đơn giản bằng sơ đồ khối hoặc ngôn ngữ liệt kê. 3.Về tư duy, thái độ: -Có ý thức xây dựng bài học -Biết xây dựng thuật toán tối ưu: ít tốn thời gian và bộ nhớ. II.CHUẨN BỊ CỦA GIÁO VIÊN VÀ HỌC SINH: 1.Chuẩn bị của giáo viên: - Đồ dùng dạy học: Máy tính điện tử -Giáo án, giáo án điện tử 2.Chuẩn bị của học sinh:Những khái niệm và kiến thức đã học về thuật toán III.PHƯƠNG PHÁP DẠY HỌC: Giải quyết vấn đề IV.TIẾN HÀNH BÀI DẠY: 1. Ổn định lớp:(2’) Vắng: Trể: 2.Kiểm tra bài củ: (3 - 6’): 1.Nêu khái niệm bài toán và thuật toán? 2.Xác định Input, Output và thuật toán cho bài toán: “Cho ba cạnh a, b, c của tam giác ABC. Tính chu vi P và diện tích S của tam giác đó” 3.Dạy bài mới:(30 - 37’) Hoạt động của giáo viên Hoạt động của học sinh Bài 1: Tìm nghiệm của phương trình bậc 2 tổng quát: ax2 + bx + c = 0 Câu hỏi: Em hãy nêu ý tưởng giải quyết bài toán về mặt toán học. Bài giải: - Input: a, b, c - Output: kết luận nghiệm x *Thuật toán: a)Cách liệt kê B1: Nhập a, b, c B2: Nếu a = 0: B21: Nếu b ¹ 0: x ¬ -c/b. Đến B7 B22: Nếu c ¹ 0: KL VN. Đến B7 B23: KL VSN. Đến B7 B3: D ¬ b2 – 4ac B4: Nếu D < 0: KL VN. Đến B7 B5: Nếu D = 0: x ¬ - b/2a. Đến B7 B6: x1,2 ¬ (- b ± ÖD)/2a. B7: Thuật toán dừng. GV:Định hướng cho HS các trường hợp đặc biệt và cách xác lập các bước giải. GV:Nhận xét bài toán: Nêu tính dừng, tính đúng đắn, tính xác định của bài toán. b)Sơ đồ khối: Bài 2: Cho N và dãy số a1,..., aN, Hãy tìm giá trị nhỏ nhất(Min) của dãy đó Câu hỏi:Nêu sự giống nhau, khác nhau giữa bài toán này và bài toán thí dụ trang 33 SGK Bài giải: a)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ị nhỏ nhất Min của dãy b)Thuật toán: *Cách liệt kê B1: Nhập N và dãy a1,..., aN; B2: Min ¬ a1, i ¬ 2; B3: Nếu i > N thì ghi ra màn hình giá trị min rồi kết thúc B4: B 4.1: Nếu ai < Min thì Min¬ai; B4.2: i ¬ i + 1rồi quay lại bước 3 *Sơ đồ khối: §óng §óng Sai NhËp N vµ d·y a1,..., aN Min ¬ ai ai < Min? i > N ? Min ¬ a1, i ¬ 2 §­a ra Min råi kÕt thóc i ¬ i + 1 Sai Bài 3: Cho N và dãy a1,..., an. Hãy cho biết có bao nhiêu số hạng trong dãy có giá trị bằng không? Trả lời: Input? (a, b, c) Output? (kết luận nghiệm) *Ý tưởng giải quyết bài toán? -Tính Delta -Xét Delta. Có 3 trường hợp +Nếu Delta>0 thì phương trình có 2 nghiệm phân biệt. +Nếu Delta=0 thì phương trình có nghiệm kép +Nếu Delta <0 thì phưưong trình vô nghiệm. Nhận xét sự khác nhau giữa bài tập 1 và thí dụ 2, trang 32 SGK HS nhận xét (a ¹ 0 hoặc a = 0) + T/h a = 0: bx + c = 0 b ¹ 0: x = - c/b b = 0: c = 0: VSN c ¹ 0: VN + T/h a ¹ 0: lập D = b2-4ac D < 0: VN D = 0: x = - b/2a D > 0: x1, x2 HS:Xây dựng thuật toán dựa trên ý tưởng đã đưa ra. Lưu ý: bao nhiêu bước giải? thuật toán dừng lúc nào? HS lên bảng vẽ sơ đồ khối Trả lời: HS trả lời · 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ị nhỏ nhất Min của dãy Câu hỏi: Em hãy nêu ý tưởng để giải quyết bài toán này? Trả lời: Ý tưởng: - Khởi tạo giá trị Min=a1. - Lần lượt với I từ 2 đến N, So sánh giá trị số hạng ai với gí trị Min, Nếu ai<Min thì Min nhận giá trị mới là ai. - Yêu cầu HS xây dựng SĐK. Nhận xét bài toán: Nêu tính dừng, tính đúng đắn, tính xác định của bài toán. Yêu cầu HS lên bảng vẽ SĐK dựa trên giải thuật đã có HD giải và định hướng các bước để HS có thể tự xây dựng thuật toán chi tiết. - Input? - Output? 4.Hoạt động củng cố:(1-3’):Phát phiếu trắc nghiệm khách quan Chọn câu trả lời đúng nhất: Câu 1: Input của bài toán là: Các thông tin đã có Các thông tin chưa biết Các thông tin cần tìm từ Output Các thông tin cần nghiên cứu thêm Câu 2: Một thuật toán là: Việc chỉ ra tường minh một cách tìm Input từ Output Việc chỉ ra tường minh một cách tìm Output từ Input Một dãy hữu hạn các thao tác được sắp xếp theo trình tự xác định sao cho sau khi thực hiện ta nhận được Output cần tìm từ Input. Một dãy hữu hạn các thao tác được sắp xếp theo trình tự xác định sao cho sau khi thực hiện ta nhận được Input cần tìm từ Output. Câu 3: Có bao nhiêu cách diễn tả giải thuật để giải quyết 1 bài toán trong tin học? 1 cách 2 cách 3 cách 4 cách Câu 4: Các khối nào sau đây dùng để diễn tả thuật toán dưới dạng sơ đồ khối? Hình tròn, Hình vuông, Hình Thoi, Mũi tên Hình Ô van, Hình Thoi, Hình chữ nhật, Mũi tên Hình Ô van, Hình Thang, Hình chữ nhật, Mũi tên Hình Chữ nhật, Hình vuông, Hình Thoi, Mũi tên 5.Hướng dẫn học sinh về nhà:(2-3’) Học các nội dung: Các nội dung đã học từ bài số 2 đến nay Bài tập: 2,6,7/SGK Chuẩn bị bài mới: Học các nội dung đã nêu, xem lại các bài tập đã sữa để chuẩn bị kiểm tra 1 tiết. Ngày soạn: TIẾT 15:NGÔN NGỮ LẬP TRÌNH I.MỤC TIÊU: Qua bài học, học sinh cần nắm được: 1.Về kiến thức: Biêt được khái niệm NN máy, hợp ngữ và ngôn ngữ lập trình bậc cao. 2.Về kỹ năng: Biết được một số loại NNLT bậc cao, ưu và nhược điểm của từng loại NNLT 3.Về tư duy, thái độ: -Có ý thức xây dựng bài họ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: - Đồ dùng dạy học: Máy tính điện tử -Giáo án, giáo án điện tử 2.Chuẩn bị của học sinh:Những khái niệm và kiến thức đã học từ trước đến nay. III.PHƯƠNG PHÁP DẠY HỌC: Giải quyết vấn đề, nêu các câu hỏi gợi mở để HS trả lời. IV.TIẾN HÀNH BÀI DẠY: 1. Ổn định lớp:(2’) Vắng: Trể: 2.Kiểm tra bài củ: (3 - 6’) 1.Nêu khái niệm bài toán và thuật toán? 2.Nêu các cách diễn tả thuật toán? 3.Nêu một bìa toán, xác định dữ liệu vào, ra và viết thuật toán? 3.Dạy bài mới:(30 - 37’) Hoạt động của giáo viên Hoạt động của học sinh Câu hỏi: NNLT là gì? Ngôn ngữ để viết chương trình được gọi là Ngôn ngữ lập trình. Các NNLT là phương tiện giao tiếp giữa người và máy tính. Câu hỏi: Khi viết chương trình bằng NN máy, ta gặp phải những khó khăn gì? I.NGÔN NGỮ MÁY: -Là NN duy nhất để viết chương trình mà máy tính có thể trực tiếp hiểu và thực hiện được. -Mỗi loại máy tính có NN máy riêng -Có thể khai thác triệt để các đặc điểm phần cứng của máy tính khi viết chương trình bằng NN máy. -Mỗi chương trình được viết trên NN khác muốn thực hiện được trên máy tính đều phải được dịch ra NN máy. -Các lệnh viết bằng NN máy là dãy các ký tự 0, 1 hoặc biến thể của chúng theo hệ cơ số 16. Câu hỏi: Chương trình dịch có chức năng gì? Câu hỏi: hợp ngữ khắc phục được những nhược điểm nào cảu NN máy? II.HỢP NGỮ:Bao gồm tên các câu lệnh và quy tắc viết các câu lệnh để máy tính hiểu được. Tên các câu lệnh bao gồm 2 phần: -Phần đầu: Tên mã lệnh, chỉ phép toán cần thực hiện. -Phần sau: Phần địa chỉ, chứa toán hạng của phép toán đó. Ví dụ: Input a (nạp giá trị cho a từ bàn phím) Load a (Đọc giá trị a vào thanh ghi tổng) Print e (Hiển thị giá trị e ra màn hình) Add d (Cộng giá trị của A với giá trị d) Mult e (Nhân giá trị của A với e) Move e (Ghi giá trị tưd A vào thanh ghi e) Câu hỏi: Em có nhận xét gì về chương trình viết trên hợp ngữ? Câu hỏi: Hãy nêu một vài ví dụ về NNLT bậc cao mà em biết? III.NGÔN NGỮ LẬP TRÌNH BẬC CAO: -Các câu lệnh trong NNLT bậc cao gần với NN tự nhiên. -Có tính độc lập cao, ít phụ thuộc vào loại máy cụ thể. -Tuỳ theo lĩnh vực ứng dụng mà các NNLT bậc cao cung cấp các phương tiện trợ giúp để giải các bài toán KH, KT hay quản lý. Trả lời: là phương tiện giao tiếp giữa người và máy tính. Trả lời: -Mỗi loại máy tính có NN máy riêng -Ta phải nhớ rất máy móc các dòng số không thể hiện tường minh ý nghĩa cảu câu lệnh. Trả lời: -Duyệt chương trình nguồn để phát hiện các lỗi sai cú pháp -Dịch chương trình viết trên NN khác ra NN máy. Trả lời: -Các câu lệnh gần với NN tự nhiên và có quy tắc viết cụ thể. Ví dụ: Viết chương trình tính giá trị của: e = (a+b) * (c+d) Input a Input b Input c Input d Load a Add b Move e Load c Add d Mult e Move e Print e Halt A: B: C: D: E: END. Trả lời: Chương trình quá dài dòng và phức tạp Trả lời: NNLT Pascal: Giải các bài toán KH - KT NNLT Foxpro: Giải các bài toán quản lý.... 4.Hoạt động củng cố:(1-3’) Nhắc lại những ưu điểm và nhược điểm của các loại NNLT 5.Hướng dẫn học sinh về nhà:(2-3’) Học các nội dung: Khái niệm NNLT, NN máy, Hợp ngữ, NNLT bậc cao Bài tập:1,2,3/SGK Chuẩn bị bài mới: Nêu các bước để gải một bài toán thông thường. Ngày soạn: TIẾT 16: GIẢI BÀI TOÁN TRÊN MÁY TÍNH I.MỤC TIÊU: Qua bài học, học sinh cần nắm được: 1.Về kiến thức: Biết các bước cơ bản khi tiến hành giải bài toán trên máy tính: Xác định bài toán, xây dựng thuật toán, lựa chọn CTDL, viết chương trình, hiệu chỉnh, đưa ra kết quả và hướng dẫn sử dụng. 2.Về kỹ năng: Ghi nhớ các bước trên có thể được tiến hành nhiều lần 3.Về tư duy, thái độ: -Có ý thức xây dựng bài họ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: - Đồ dùng dạy học: Máy tính điện tử -Giáo án, giáo án điện tử 2.Chuẩn bị của học sinh:kiến thức về MTĐT, thuật toán và NNLT III.PHƯƠNG PHÁP DẠY HỌC: Giải quyết vấn đề, nêu các câu hỏi gợi mở để HS trả lời. IV.TIẾN HÀNH BÀI DẠY: 1. Ổn định lớp:(2’) Vắng: Trể: 2.Kiểm tra bài củ: (3 - 6’) 1.Ngôn ngữ lạp trình là gì? Chương trình dịch có chức năng gì? 2.Nêu các ưu và nhược điểm của các loại NNLT? 3.Dạy bài mới:(30 - 37’) Hoạt động của giáo viên Hoạt động của học sinh I.XÁC ĐỊNH BÀI TOÁN: Ví dụ: Xét bài toán tìm nghiệm của phương trình ax + b = 0. Qua các bươc giải bài toán trên máy tính. Bước 1: Xác đinh bài toán Câu hỏi: Em hãy nêu dữ liệu vào và ra của bài toán. Câu hỏi: Qua bước này, chúng ta cần nắm rõ điều gì? -Việc xác định bài toán chính là xác định rõ 2 thành phần Input và Output. -Các thông tin này cần được nghiên cứu một cách cẩn thận để có thể lựa chọn câu trúc dữ liệu, thuật toán và NNLT thích hợp. II.LỰA CHỌN VÀ XÂY DỰNG THUẬT TOÁN: Bước 2: Lựa chọn và xây dựng thuật toán. Câu hỏi: Em hãy diển tả thuật toán của bài toán trên bằng phương pháp liệt kê? Câu hỏi: Khi lựa chọn thuật toán, cần căn cứ vào những điều nào? 1.Lựa chọn thuật toán: Cần căn cứ vào những tiêu chí sau: -Phải thoả mãn tất cảc 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. -Phải lựa chọn một thuật toán tối ưu: Thuật toán ít tốn kém về tài nguyên của máy tính nhất ( bộ nhớ, bộ xử lý, thời gian...).Trong đó thời gian là quan trọng nhất vì thời gian là tài nguyên không tái tạo lại được. -Cần thiết kế hoặc lựa chọn thuật toán sao cho việc viết chương trình cho thuật toán đó ít phức tạp -Cần căn cứ vào lượng tài nguyên mà thuật toán đòi hỏicũng như lượng tài nguyên thật tế cho phép. 2.Diễn tả thuật toán: Có hai cách -Liệt kê -Dùng sơ đồ khối. Bước 3: Viết chương trình Với máy tính điện tử, GV dung NNLT Pascal để thể hiện thuật toán trên. Không cần giả thích các câu lệnh cho HS biết. Chỉ cần giới thiệu đây là chương trình của bài toán trân khi tiến hành bước 3. Khi viết chương trình nên có một vài lỗi để sau đó giới thiệu cho HS biết bước thứ 4 III.VIẾT CHƯƠNG TRÌNH: -Là một quá trình tổng hợp giữa việc lựa chọn cấu trúc dữ liệu và NNLT để diễn tả đúng thuật toán. -Khi viết chương trình ta cần lựa chọn một NNLT bậc cao, hợp ngữ, NN máy hoặc một phần mềm chuyên dụng thích hợp cho thuật toán đã lựa chọn. -Viết chương trình bằng NNLT nào, ta cần phải tuân thủ theo đúng quy định ngữ pháp cảu NNLT đó. Bước 4: hiệu chỉnh Chạy chương trình với a, b là các bộ Input tiêu biểu. Với a= 5, b=6 Với a=0, b=0 Với a=0, b=4 Cho HS thấy kết quả khi chậy chương trình với các bộ dữ liệu như trên. IV.HIỆU CHỈNH: Câu hỏi: Nêu các công việc của hiệu chỉnh? -Thử chương trình bằng cách thực hiện nó với các bộ Input tiêu biểu -Các bộ Input này được gọi là các TEST. -Nếu có sai sót ta phải thử chương trình rồi thử lại. -Trong quá trình hiệu chỉnh ta có thể thay đổi NNLT hoặc thuật toán. -Tuỳ theo độ tiện dụng của NNLt và chương trình dịch mà ta có được sự trợ giúp khác nhau để phát hiện và sữa các sai sot. -Máy tính chỉ phát hiện những lỗi sai cú pháp(Lỗi do người lập trình viết sai). V.VIẾT TÀI LIỆU: Câu hỏi: Viết tài liệu là thực hiện những công việc gì? -Mô tả chi tiết toàn bộ bài toán, thuật toán, chương trình, kết quả thí nghiệm, hướng dẫn sử dụng. -Tài liệu này rất có ích cho người sử dụng chương trình và đề xuất những khả năng hoàn thiện thêm. Trả lời: Input: a,b Output: Nghiệm của phương trình Trả lời: Qua bước này ta cần nắm rõ: +a,b là các số bất kỳ, kiểu dữ liệu của a, b là số thực. +Nghiệm của phương trình có thể là: Vô nghiệm, vô số nghiệm hoặc một nghiệm x (với x là kiểu số thực) Trả lời: Bước 1: Nhập a b là 2 số thực Bước 2: Nếu a0 thì x = -b/a --> Bước 4 Bước 3: -Nếu b0 thì thông báo phương trình vô nghiệm -Nếu b=0 thì thông báo phương trình vô số nghiệm. Bước 4: In x ra màn hình. GV: gọi một HS lên bảng vẽ sơ đồ khối. HS: Vẽ sơ đồ khối HS trả lời: HS quan sát chương trình trên máy tính và nhận xét HS quan sát chương trình trên máy tính và nhận xét Trả lời: -Thử chương trình bằng cách thực hiện nó với các bộ Input tiêu biểu -Các bộ Input này được gọi là các TEST. -Nếu có sai sót ta phải thử chương trình rồi thử lại. -Trong quá trình hiệu chỉnh ta có thể thay đổi NNLT hoặc thuật toán. -Tuỳ theo độ tiện dụng của NNLt và chương trình dịch mà ta có được sự trợ giúp khác nhau để phát hiện và sữa các sai sot. -Máy tính chỉ phát hiện những lỗi sai cú pháp(Lỗi do người lập trình viết sai). Trả lời: -Mô tả chi tiết toàn bộ bài toán, thuật toán, chương trình, kết quả thí nghiệm, hướng dẫn sử dụng. -Tài liệu này rất có ích cho người sử dụng chương trình và đề xuất những khả năng hoàn thiện thêm. -Viết thêm một tài liệu hướng dẫn sử dụng, thuật toán, kết quả thử nghiệm.... 4.Hoạt động củng cố:(1-3’) Nhắc lại các bước giải bài toán trên máy tính 5.Hướng dẫn học sinh về nhà:(2-3’) Học các nội dung: Xác định bài toán, các tiêu chuẩn lựa chọn thuật toán, viết chương trình, hiệu chỉnh, viết tài liệu Bài tập: 1.53,1.54,1.55,1.56,1.57,1.58/SBT Chuẩn bị bài mới: Thế nào goị là một phần mềm máy tính? Có bao nhiêu loại phần mềm máy tính. Ngày soạn: TIẾT 17: BÀI TẬP I.MỤC TIÊU: Qua bài học, học sinh cần nắm được: 1.Về kiến thức: Củng cố kiến thức cho HS sau khi học lý thuyết chương I, đặt biệt là các kiến thức liên quan đến bài Bài toán và thuật toán. 2.Về kỹ năng: Học sinh vận dụng các kiến thức đã học để giải các bài toán liên quan đến bài Bài toán và thuật toán. 3.Về tư duy, thái độ: Có hành vi và thái độ đúng đắn về những vấn đề đạo đức liên quan đến việc sử dụng máy tính. II.CHUẨN BỊ CỦA GIÁO VIÊN VÀ HỌC SINH: 1.Chuẩn bị của giáo viên: - Đồ dùng dạy học: Máy tính điện tử -Giáo án, giáo án điện tử 2.Chuẩn bị của học sinh: Các kiến thức đã học trong chương I đặt biệt là bài: Bài toán và thuật toán. III.PHƯƠNG PHÁP DẠY HỌC: Giải quyết vấn đề, nêu các câu hỏi gợi mở để HS trả lời. IV.TIẾN HÀNH BÀI DẠY: 1. Ổn định lớp:(2’) Vắng: Trể: 2.Kiểm tra bài củ: (3 - 6’) 1. Nêu ảnh hưởng của Tin học đối với sự phát triển xã hội? 2. Như thế nào được gọi là một XH Tin học hoá? Em sẽ làm gì khi sống trong XH Tin học hoá? 3.Dạy bài mới:(30 - 37’) Hoạt động của giáo viên Hoạt động của học sinh` Câu hỏi:Hãy thực hiện các bước giải bài toán trên? GV: Gọi từng em HS lên thực hiện các bước giả bài toán Bài 1:Viết thuật toán cho bài toán rút gọn phân số? HD -Input: Phân số (Trong đó có tử số (a), mẫu số (b) là hai số nguyên) -Output: Phân số sau khi đã rút gọn. Bước 1: Nhập tử số a và mẫu số b Bước 2: Nếu a= b thì UCLN = a; Bước 3: Nếu a> b thì a = a - b rồi quay lại bước 2. Bước 4: b = b - a rồi quay lại bước 2. Bước 5: a = a/UCLN Bước 6: b = b/UCLN Bước 7: Đưa ra a, b rồi kết thúc. Câu hỏi: Theo em. Những bộ Input nào là tiêu biểu cho bài toán này? Bài 2: Viết thuật toán tính tổng: S = 1 + 1/2 + 1/3 +... + 1/n với n là số nguyên dương. HD: Câu hỏi: en hãy xác định dữ liệu vào và ra của bài toán? -Input: n là số nguyên dương -Output: Tổng S Câu hỏi: Em hãy viết thuật toán cho bài toán trên? Bước 1: Nhập n là số nguyên dương Bước 2: i = 1, S = 0 Bước 3: Nếu i>n thì đưa ra S rồi kết thúc Bước 4: S = S + 1/i I = i + 1 Bước 5: quay lại bước 3. Bước 1: Xác định bài toán -Input: Phân số (tử số là a, nẫu số là b là hai số nguyên) -Output: Phân số sau khi đã rút gọn. Bước 2: Thuật toán *Chú ý:có thể tham khảo thuật toán tìm UCLN của hai số M và N trong SGK Cách 1: Liệt kê Bước 1: Nhập tử số a và mẫu số b Bước 2: Nếu a= b thì UCLN = a; Bước 3: Nếu a> b thì a = a - b rồi quay lại bước 2. Bước 4: b = b - a rồi quay lại bước 2. Bước 5: a = a/UCLN Bước 6: b = b/UCLN Bước 7: Đưa ra a, b rồi kết thúc. Cách 2: Sơ đồ khối. HS tự vẽ sơ đồ khối. Bước 3: Viết chương trình Với máy tính điện tử, GV viết chương trình này trong NNLT Turbo Pascal để HS hình dung. Bước 4: Hiệu chỉnh Trả lời: HS trả lời, GV chạy chương trình TP và thử các bộ Input tiêu biểu để xem kết quả. Bước 5: Viết tài liệu. HS xem đây như một BT về nhà viết. Trả lời: -Input: n là số nguyên dương -Output: Tổng S Trả lời: GV gọi HS lên bảng viết. Bước 1: Nhập n là số nguyên dương Bước 2: i = 1, S = 0 Bước 3: Nếu i>n thì đưa ra S rồi kết thúc Bước 4: S = S + 1/i I = i + 1 Bước 5: quay lại bước 3. Với MTĐT giáo viên lập trình sãnmột chương trình trong TP và cho HS tiến hành hiệu chỉnh. 4.Hoạt động củng cố:(1-3’) Nhắc lại các kiến thức hS đã học trong các bài ở chương I 5.Hướng dẫn học sinh về nhà:(2-3’) Học các nội dung: Bài toán và thuật toán Bài tập: Viết thuật toán tính tích P = 1. 1/2 . 1/3....1/n với n là số nguyên Ngày soạn: TIẾT 18: KIỂM TRA 1 TIẾT I.MỤC TIÊU: Qua bài kiểm tra, giáo viên và học sinh có thể: 1.Về kiến thức: -Kiểm tra đánh giá kiến thức sau khi hoc các bài trong chương I từ bài 1 đến bài 4. 2.Về kỹ năng:Biết cách làm