Giáo án Tin học 10 - Tiết 11 - 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 11) 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 thuật toán - Cách diễn giải bài toán theo 2 cách - 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 Trong sơ đồ khối, người ta dùng một số khối, đường có mũi tên với: Hình thoi thể hiện thao tác so sánh; Hình chữ nhật thể hiện các phép tính toán; Các mũi tên quy định trình tự thực hiện các thao tác; Hình ô van thể hiện thao tác nhập, xuất dữ liệu. - Dưới đây là ví dụ mô phỏng các bước thực hiện thuật toán trên với N = 11 và dãy A: 5, 1, 4, 7, 6, 3, 15, 8, 4, 9, 12. GV: Ngoài cách liệt kê ra dãy các thao tác như trên, thuật toán còn có thể được diễn tả GV: Với bài toán ở ví dụ trên, thuật toán có thể được diễn tả bằng sơ đồ khối như hình 21bằng sơ đồ khối.  Dãy A 5 1 4 7 6 3 15 8 4 9 12 i 2 3 4 5 6 7 8 9 10 11 12 Max 5 5 5 7 7 7 15 15 15 15 15 Các thao tác trong thuật toán phải được mô tả đủ chi tiết để đối tượng thực hiện thuật toán có thể thực hiện được. Ví dụ. Trong thuật toán giải phương trình bậc hai Với ba hệ số a, b, c cần tính đại lượng D = b2 – 4ac. Qua định nghĩa, ta thấy thuật toán có các tính chất chính sau: Tính dừng: Thuật toán phải kết thúc sau một số hữu hạn lần thực hiện các thao tác; Tính xác định: Sau khi thực hiện một thao tác thì hoặc là thuật toán kết thúc hoặc là có đúng một thao tác xác định để được thực hiện tiếp theo; Tính đúng đắn: Sau khi thuật toán kết thúc, ta phải nhận được Output cần tìm. GV: Tuỳ thuộc đối tượng thực hiện mà việc tính D có thể được mô tả chi tiết khác nhau, chẳng hạn: - Với người đã biết công thức tính D thì chỉ cần mô tả một bước là: Tính D; - Với người chưa biết công thức tính D thì cần phải mô tả chi tiết hơn, chẳng hạn: Dù học sinh không hề biết khái niệm D là gì nhưng thực hiện theo các bước nêu trên thì vẫn nhận được giá trị D cần tính. Ví dụ. Với thuật toán tìm Max đã xét: Tính dừng: Vì giá trị của i mỗi lần tăng lên 1 nên sau N lần thì i > N, khi đó kết quả phép so sánh ở bước 3 xác định việc đưa ra giá trị Max rồi kết thúc. Tính xác định: Thứ tự thực hiện các bước của thuật toán được mặc định là tuần tự nên sau bước 1 là bước 2, sau bước 2 là bước 3. Kết quả các phép so sánh trong bước 3 và bước 4 đều xác định duy nhất bước tiếp theo cần thực hiện. Tính đúng đắn: Vì thuật toán so sánh Max với từng số hạng của dãy số và thực hiện Max ơ ai nếu ai > Max nên sau khi so sánh hết N số hạng của dãy thì Max là giá trị lớn nhất. 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.