Bài giảng Tin học căn bản (Phần 2): Chương 2 - Nguyễn Hồng Phương

Chương 2:<br /> Thuật toán<br /> Ngo Van Linh<br /> Bộ môn Hệ thống thông tin<br /> Viện Công nghệ thông tin và Truyền thông<br /> Đại học Bách Khoa Hà Nội<br /> <br /> 1<br /> <br /> Nội dung chương này<br /> <br /> <br /> <br /> <br /> <br /> <br /> 2.1.<br /> 2.2.<br /> 2.3.<br /> 2.4.<br /> 2.5.<br /> <br /> Định nghĩa thuật toán<br /> Biểu diễn thuật toán<br /> Một số thuật toán thông dụng<br /> Thuật toán đệ quy<br /> Thuật giải heuristic<br /> <br /> 2<br /> <br /> 2.1. Định nghĩa thuật toán<br /> <br /> <br /> <br /> <br /> <br /> <br /> Là một khái niệm cơ sở của toán học và tin<br /> học.<br /> Bao gồm một dãy hữu hạn các lệnh/chỉ thị<br /> rõ ràng và có thể thi hành được để hướng<br /> dẫn thực hiện một hành động nhằm đạt<br /> được mục tiêu đề ra.<br /> Thuật toán là sự thể hiện của một phương<br /> pháp để giải quyết một vấn đề.<br /> 3<br /> <br /> Ví dụ 1: Thuật toán tìm phần tử lớn nhất<br /> của một dãy hữu hạn các số nguyên<br /> <br /> <br /> Các bước:<br /> <br /> <br /> <br /> <br /> <br /> <br /> <br /> 1. Đặt giá trị lớn nhất tạm thời là số nguyên đầu tiên.<br /> 2. So sánh số nguyên kế tiếp trong dãy với giá trị lớn<br /> nhất tạm thời, nếu số nguyên này lớn hơn giá trị lớn<br /> nhất tạm thời thì đặt giá trị lớn nhất tạm thời bằng số<br /> nguyên này.<br /> 3. Lặp lại bước 2 nếu còn số nguyên trong dãy chưa<br /> được xét.<br /> 4. Dừng nếu không còn số nguyên nào trong dãy chưa<br /> được xét. Giá trị lớn nhất tạm thời lúc này chính là giá<br /> trị lớn nhất trong dãy số.<br /> 4<br /> <br /> Ví dụ 2: Thuật toán giải phương trình bậc<br /> hai: ax2 + bx + c = 0 (a0)<br /> <br /> <br /> <br /> <br /> 1. Nhập 3 hệ số a, b, c<br /> 2. Tính giá trị Δ = b2 - 4*a*c<br /> 3. Xét dấu Δ. Nếu Δ>0 thì thực hiện các thao tác<br /> sau đây:<br /> <br /> <br /> 3.1. Tính các nghiệm theo các công thức:<br /> <br /> <br /> <br /> <br /> <br /> <br /> <br /> <br /> <br /> x1 = (-b-sqrt(Δ))/(2*a)<br /> x2 = (-b+sqrt(Δ))/(2*a)<br /> <br /> 3.2. Xuất kết quả: phương trình có hai nghiệm x1 và x2.<br /> <br /> 4. Nếu Δ là 0 thì xuất kết quả: phương trình có<br /> nghiệm kép là -b/(2*a)<br /> 5. Nếu Δ