Bài 4. Bài toán và thuật toán

$4b. Trình bày Thuật toán
(Tóm tắt các cách trình bày)

Trong tin học, bài toán là một việc mà ta muốn máy tính thực hiện. Cho một bài toán là mô tả đầu vào (Input) và yêu cầu của đầu ra (Output)
Ví dụ đơn giản:
Giải phương trình ax2 + bx + c = 0. Nếu mình muốn giao cho máy tính làm thì phải nhập các hệ số a, b, c cho máy, rổi máy đưa kết quả ra ngay, ta không cần phải tự tay tính toán gì hết. Tuy nhiên ta phải “dạy” cho máy cách làm “tổng quát” để khi ta đưa a, b, c thế nào cho nó thì cũng phải ra kết quả!
Việc chỉ ra một cách tường minh lời giải của một bài toán gọi là thuật toán (Algorithm) giải bài toán đó. SGK đã nêu một định nghĩa chính thức như sau:
Thuật toán đẻ giải một bài toán là một dãy hữu hạn các tháo tác, được sắp xếp theo một trình tự xác định sao cho sau khi thực hiện dãy thao tác ấy, từ Input của bài toán, ta nhận được Output cần tìm!
Chú ý:
Chương trình có khác với thuật toán ở chỗ:
Chương trình thì nêu lên các bước giải, có thể không tường minh. Trả lời câu hỏi lần lượt làm những gì?
Thuật toán nêu bật phương pháp (mưu mẹo) qua các bước tường minh, và trả lời câu hỏi làm thế nào?
Thuật toán có thể chỉ nêu một phần của chương trình! Cùng một bài toán có thể có nhiều thuật toán khác nhau! Thuật toán tối ưu là thuật toán giúp máy tính thực hiện nhanh nhất, tốn ít bộ nhớ nhất.
Có 3 cách trình bày một thuật toán:
Diễn giải thành từng bước: Các bước được thực hiện tuần tự hoặc nhảy đến bước trước hay sau nhưng xa hơn sau khi gặp một điều kiện nào đó.
Vẽ sơ đồ khố (lưu đồ): Khoanh hình tròn hay elíp để bắt đầu hay kết thúc, hình thoi để chứa điều kiện, hình chữ nhật chứa công việc, và đoạn thẳng hay véo tơ chỉ đường đi.
Giả lập trình: Dùng các cấu trúc của ngôn ngữ lập trình bậc cao, các kí hiệu toán học và ngôn ngữ tự nhiên. Cách này gọn gàng hơn.
Nhà quản lý, nhà doanh nghiệp hay nhà khoa học, nên nắm chắc được ít nhất một trong các cách trình bày thuật toán nêu trên.
Sau đây là một ví dụ đơn giản về chương trình và so sánh 2 thuật toán khác nhau:
Ví dụ: Tính trung bình n nhiên tiên, n>1 bàn phím.
trình:
1. n bàn phím. 2. Tính s = 1+2+…+n. 3. Tính = s/n. 4. : kq.
Chú ý:
Ta có thể dùng kí hiệu mũi tên ngược để mô ta phép gán giá trị của một biểu thức cho một đại lượng có đặt tên (còn gọi là biến).

Ví dụ:
Tăng k thêm 1 đơn vị, ta có thể viết: k ( k+1.
Trong ngôn ngữ lập trình C/C++, ta viết luôn k=k+1. Trong Pascal, ta viết k:=k+1.
Sau , ta đề các trình trên, ở 2: Tính s = 1+2+..+n.
Có các thuật toán sau:
toán 1. (– ): 1. S ( 0, k ( 1. (Tức là cho S = 0 và cho k = 1). 2. S ( S+k. (là cho S = S cũ + k). 3. k ( k+1. (là k lên 1 4. k > n thì thu giá S và thúc!
Trái thì quay 2.
Cách làm trên, n-1 phép , vô cùng khi n ! Chẳng hạn n = 1 triệu, phải mất gần 1 triệu phép cộng! toán 2. (Carl_Friedrich_Gauss) Bước 1. S ( (1+n)*n/2.
!
Trên đây là thuật toán tính tổng của một dãy số có quy luật, thì mới sử dụng công thức toán học được. Chỉ trừ không giỏi toán thì mới phải làm theo thuật toán “cơ bắp”. Cho nên, việc kết hợp toán học và tin học là rất có lợi! Một người rất giỏi tin, nhưng lại không giỏi toán thì vẫn tạo ra các thuật toán để giải bài toán tin học, nhưng thường dài dòng