tailieunhanh - Bài giảng Tin học đại cương (Phần 2): Chương 2 - TS. Nguyễn Kim Hiếu

Bài giảng "Tin học đại cương (Phần 2) - Chương 2: Thuật toán" cung cấp cho người học các kiến thức: Định nghĩa thuật toán, biểu diễn thuật toán, một số thuật toán thông dụng, thuật toán đệ quy, thuật giải heuristic. . | Nội dung chương này IT1110 Tin học đại cương Phần II Giải quyết bài toán Chương 2 Thuật toán . Định nghĩa thuật toán . Biểu diễn thuật toán . Một số thuật toán thông dụng . Thuật toán đệ quy . Thuật giải heuristic 2 1 . Định nghĩa thuật toán Ví dụ 1: Thuật toán tìm phần tử lớn nhất của một dãy hữu hạn các số nguyên Là một khái niệm cơ sở của toán học và tin học. Bao gồm một dãy hữu hạn các lệnh/chỉ thị rõ ràng và có thể thi hành được để hướng dẫn thực hiện một hành động nhằm đạt được mục tiêu đề ra. Thuật toán là sự thể hiện của một phương pháp để giải quyết một vấn đề. Các bước: 3 1. Đặt giá trị lớn nhất tạm thời là số nguyên đầu tiên. 2. So sánh số nguyên kế tiếp trong dãy với giá trị lớn nhất tạm thời, nếu số nguyên này lớn hơn giá trị lớn nhất tạm thời thì đặt giá trị lớn nhất tạm thời bằng số nguyên này. 3. Lặp lại bước 2 nếu còn số nguyên trong dãy chưa được xét. 4. Dừng nếu không còn số nguyên nào trong dãy chưa được xét. Giá trị lớn nhất tạm thời lúc này chính là giá trị lớn nhất trong dãy số. 4 Các đặc trưng của thuật toán Ví dụ 2: Thuật toán giải phương trình bậc hai: ax2 + bx + c = 0 (a 0) 1. Nhập 3 hệ số a, b, c 2. Tính giá trị Δ = b2 - 4*a*c 3. Xét dấu Δ. Nếu Δ>0 thì thực hiện các thao tác sau đây: . Tính các nghiệm theo các công thức: x1 = (-b-sqrt(Δ))/(2*a) x2 = (-b+sqrt(Δ))/(2*a) . Xuất kết quả: phương trình có hai nghiệm x 1 và x2. 4. Nếu Δ là 0 thì xuất kết quả: phương trình có nghiệm kép là -b/(2*a) 5. Nếu Δ0 x1 = (-b-sqrt(Δ))/(2*a) x2 = (-b+sqrt(Δ))/(2*a) Mã giả Δ = b2 - 4ac đúng 9 đúng Các cấu trúc thường gặp: Cấu trúc chọn: Cấu trúc lặp i i+1 Tiện lợi, đơn giản, vẫn dễ hiểu. while (điều kiện) do (hành động) end while repeat (hành động) until (điều kiện) for (biến)=(giá trị đầu) to (giá trị cuối) do (hành động) end for for (biến)=(giá trị cuối) downto (giá trị đầu) do (hành động) end .