Bài giảng Tin học lớp 10 - Bài 4: Bài toán và thuật toán

BÀI TOÁN VÀ THUẬT TOÁNXét các yêu cầu :Giải phương trình bậc hai ax2+bx+c=0Viết một dòng chữ ra màn hình máy tính.Quản lý các cán bộ trong một cơ quanI. KHÁI NIỆM BÀI TOÁNTrong TIN HỌCTất cả các yêu cầu trên đều được xem là bài toánKhái niệm	Bài toán là việc nào đó ta muốn máy tính thực hiện.CÁC THÀNH PHẦN CƠ BẢN CỦA BÀI TOÁNINPUTCác thông tin đã cóOUTPUTCác thông tin cần tìm từ inputII. KHÁI NIỆM THUẬT TOÁNHướng dẫn các thao tác cho máy thực hiện để tìm ra lời giảiBài toánInputOutputBằng cách nào?Giải bài toánThuật toánInputOutputTHUẬT TOÁN(Thao tác 1 Thao tác 2 ... Thao tác n)BÀI TOÁNThuật toán để giải một bài toán là : Một dãy hữu hạn các thao tác. Các thao tác được sắp xếp theo một trình tự xác định. Sau khi thực hiện dãy thao tác đó, từ Input ta tìm được Output của bài toán.MÔ TẢ CÁC THAO TÁC TRONG THUẬT TOÁNCó 2 cách mô tảLiệt kêDùng sơ đồ khốiNêu ra tuần tự các thao tác cần tiến hànhDùng một số biểu tượng thể hiện các thao táca) LIỆT KÊ LIỆT KÊ : Bước 1 : Nhập a, b. Bước 2 : Nếu a = 0 thì quay lại bước 1, ngược lại thì qua bước 3. Bước 3 : Gán cho x giá trị -b/a, rồi qua bước 4. Bước 4 : Đưa ra kết quả x và kết thúc.VD : Tìm nghiệm phương trình bậc nhất tổng quát : ax + b = 0 (): Thể hiện các thao tác so sánhb) DÙNG SƠ ĐỒ KHỐITrong sơ đồ khối, người ta dùng một số biểu tượng thể hiện các thao tác như :: Thể hiện các phép tính toán: Quy định trình tự thực hiện các 	thao tác: Thể hiện các thao tác nhập, xuất 	dữ liệuNgoài ra:III. VÍ DỤ VỀ THUẬT TOÁN Kiểm tra tính nguyên tố của số nguyên dươngXác định bài toánInputOutputÝ tưởng: nhớ lại định nghĩaThuật toánLiệt kêSơ đồ khối2. Bài toán sắp xếpMOÂ PHOÛNG THUAÄT TOAÙN TRAÙO ÑOÅI (Exchange Sort)Xác định bài toánInputOutputÝ tưởngThuật toánLiệt kêSơ đồ khối3. Bài toán tìm kiếmXác định bài toánInputOutputÝ tưởngThuật toánLiệt kêSơ đồ khốiThuật toám tìm kiếm tuần tựThuật toán tìm kiếm nhị phân