Kết quả cần thu được trong phần xác định bài toán còn được gọi là gì

BÀI 5 TỪ BÀI TOÁN ĐẾN CHƯƠNG TRÌNH Bài toán và xác định bài toán Bài toán là khái niệm quen thuộc trong các môn học như Toán, Vật lí,... Chẳng hạn tính tổng của các số tự nhiên từ 1 đến 100, tính quãng đường ô tô đi được trong 3 giờ với tốc độ 60km/giờ là những ví dụ vể bài toán. Tuy nhiên, hằng ngày ta thường gặp và giải quyết các công việc đa dạng hơn nhiều. Ví dụ, lập bảng cửu chương, lập bảng điểm của các bạn trong lớp hoặc so sánh chiểu cao của hai bạn Long và Trang,... cũng là những ví dụ về bài toán. Như vậy, có thể hiểu: Bài toán là một công việc hay một nhiệm vụ cần phải giải quyết. Để giải quyết được một bài toán cụ thể, người ta cần xác định bài toán, tức là xác định rõ các điều kiện cho trước và kết quả cần thu được. Ví dụ 1. Xét các bài toán tính diện tích hình tam giác, tìm đường đi tránh các điểm nghẽn giao thông trong giờ cao điểm và nấu một món ăn. Đê’ tính diện tích hình tam giác: Điều kiện cho trước: Một cạnh và đường cao tương ứng với cạnh đó; Kết quả cần thu được: Diện tích hình tam giác. Đối với bài toán tìm đường đi tránh các điểm nghẽn giao thông: Điều kiện cho trước: Vị trí điểm nghẽn giao thông và các con đường có thể đi từ vị trí hiện tại tới vị trí cần tới; Kết quả cần thu được: Đường đi từ vị trí hiện tại tới vị trí cần tới mà không qua điểm nghẽn giao thông. Đối với bài toán nấu một món ăn: Điểu kiện cho trước: Các thực phẩm hiện có [trứng, mỡ, mắm, muối, rau,...]; - Kết quả cần thu được: Một món ăn. Xác định bài toán là bước đầu tiên và là bước rất quan trọng trong việc giải bài toán. Quá trình giải bài toán trên máy tính Việc dùng máy tính giải một bài toán chính là đưa cho máy tính dãy hữu hạn các thao tác đon giản mà nó có thể thực hiện được để từ các điều kiện cho trước ta nhận được kết quả cần tìm. Dãy hữu hạn các thao tác cần thực hiện để giải một bài toán được gọi là thuật toán. Máy tính không thể tự mình tìm ra lời giải của các bài toán. Cách giải của một bài toán cụ thể, tức thuật toán, là tư duy sáng tạo của con người. Tuy nhiên, việc mô tả thuật toán chưa đủ đối với máy tính mà cần diễn đạt thuật toán dưới dạng mà máy tính có thể hiểu và thực hiện được. Kết quả diễn đạt thuật toán là chương trình được viết trong một ngôn ngữ lập trình nào đó. Máy tính sẽ chạy chưong trình và cho ta lời giải của bài toán [h. 28]. Hình 28 Nói một cách khác, thuật toán là các bước để giải một bài toán, còn chương trình là thể hiện của thuật toán trong một ngôn ngữ lập trình cụ thể. Quá trình giải bài toán trên máy tính gồm các bước sau: Xác định bài toán: Từ phát biểu của bài toán, ta xác định đâu là thông tin đã cho [INPUT] và đâu là thông tin cần tìm [OUTPUT]. Mô tả thuật toán: Diễn tả cách giải bài toán bằng dãy các thao tác cần phải thực hiện. Viết chương trình: Dựa vào mô tả thuật toán ở trên, viết chương trình bằng một ngôn ngữ lập trình thích hợp. Cần phải lưu ý rằng, để giải một bài toán có thể có nhiều thuật toán khác nhau, song mỗi thuật toán chỉ dùng để giải một bài toán cụ thể. Vì vậy, khi mô tả thuật toán, người ta thường chỉ ra cả điều kiện cho trước và kết quả cần nhận được để dễ nhận biết thuật toán đó dùng để giải bài toán nào. Thuật toán và mô tả thuật toán Trong phần này chúng ta sẽ tìm hiểu sâu hơn về khái niệm thuật toán. Nhiều công việc chúng ta thường làm mà không phải suy nghĩ nhiều, tuy nhiên, nếu hệ thống lại, ta có thể thấy thực chất đó là những thuật toán. Đơn giản như việc pha trà mời khách có thể mô tả dưới dạng thuật toán như sau: INPUT: Trà, nước sôi, ấm và chén. OUTPUT: Chén trà đã pha để mời khách. Bước 1. Tráng ấm, chén bằng nước sôi. Bước 2. Cho trà vào ấm. Bước 3. Rót nước sôi vào ấm và đợi khoảng 3 đến 4 phút. Bước 4. Rót trà ra chén để mời khách. Việc liệt kê các bước như trên là một cách thường dùng để mô tả thuật toán. Nếu không có mô tả gì khác trong thuật toán, các bước của thuật toán được thực hiện một cách tuần tự theo trình tự như đã được chỉ ra. Mặc dù không được nêu rõ trong khái niệm thuật toán, song thuật toán phải được mô tả đủ cụ thể để bất kì đối tượng nào, với cùng khả năng và điểu kiện như nhau, khi thực hiện thuật toán cũng đều đạt được kết quả như nhau. Đê’ minh hoạ, chúng ta xét thêm một vài ví dụ: Bài toán “Giải phương trình bậc nhất dạng tổng quát bx + c = 0”: INPUT: Các số b và c. OUTPUT: Nghiệm của phương trình bậc nhất. Bước 1. Nếu b = 0 chuyển tới bước 3. Bước 2 Tính nghiệm của phương trình X = và chuyển tới bước 4. Bước 3. Nếu Cí 0, thông báo phương trình đã cho vô nghiệm. Ngược lại [c= 0], thông báo phương trình có vô số nghiệm. Bước 4. Kết thúc. Bài toán “Làm món trứng tráng” INPUT: Trứng, dầu ăn, muối và hành. OUTPUT: Trứng tráng. Bước 7. Đập trứng, tách vỏ và cho trứng vào bát. Bước 2. Cho một chút muối và hành tươi thái nhỏ vào bát trứng. Dùng đũa quấy mạnh để trộn đều trứng, muối, hành. Bước 3 Cho một thìa dầu ăn vào chảo, đun nóng rồi đổ trứng đã trộn vào. Đun tiếp trong khoảng 1 phút. Bước 4. Lật mặt trên của miếng trứng úp xuống dưới. Đun tiếp trong khoảng 1 phút. Bước 5. Lấy trứng ra đĩa. Rõ ràng, bất kì ai biết về các phép toán số học hay hiểu biết một chút vê' làm bếp, theo đúng trình tự và chỉ dẫn ở các bước trong các thuật toán nêu trên đều có thể tính ra nghiệm của phương trình đã cho hay tự làm cho mình món trứng tráng. Tóm lại, có thể hiểu: Thuật toán là dãy hữu hạn các thao tác cần thực hiện theo một trình tự xác định để thu được kết quả cần thiết từ những điều kiện cho trước. Một số ví dụ về thuật toán Ví dụ 2. Một hình A được ghép từ một hình chữ nhật với chiều rộng 2a, chiều dài b và một hình bán nguyệt bán kính a như hình 29 dưới đây: INPUT: Số a là y chiều rộng của hình chữ nhật và là bán kính của hình bán nguyệt, b là chiều dài của hình chữ nhật. OUTPUT: Diện tích của hình A. Thuật toán đơn giản để tính diện tích hình A có thể gồm các bước sau: Bước 7. 5,