Thuật toán được định nghĩa là tập hữu hạn các hướng dẫn, nếu tuân thủ sẽ thực hiện một nhiệm vụ cụ thể. Mọi thuật toán phải thỏa mãn các tiêu chí:
- Đầu vào (Input): 0 hoặc nhiều đầu vào, lấy từ tập đối tượng xác định.
- Đầu ra (Output): 1 hoặc nhiều đầu ra có quan hệ cụ thể với đầu vào.
- Tính xác định (Definiteness): Mỗi bước phải được định nghĩa rõ ràng; hướng dẫn rõ ràng, không mơ hồ.
- Tính hữu hạn (Finiteness): Thuật toán phải kết thúc sau số hữu hạn bước.
- Tính hiệu lực (Effectiveness): Mọi thao tác phải đủ cơ bản để thực hiện chính xác và trong thời gian hữu hạn.
Chúng ta có thể biểu diễn thuật toán nhiều cách:
- Ngôn ngữ tự nhiên: tiếng Anh, tiếng Việt, v.v.
- Sơ đồ luồng (Flow charts): Biểu diễn đồ họa, chỉ dùng cho thuật toán nhỏ, đơn giản.
- Mã giả (Pseudo code): Bỏ qua hầu hết sự mơ hồ; không phụ thuộc cú pháp ngôn ngữ lập trình cụ thể.
Ví dụ 1: Thuật toán tính giai thừa
Bước 1: Nhập số n Bước 2: Biến final = 1 Bước 3: final ← final * n Bước 4: Giảm n Bước 5: Kiểm tra n == 0 Bước 6: Nếu n == 0, nhảy đến bước 8 (thoát vòng lặp) Bước 7: Ngược lại, nhảy về bước 3 Bước 8: In kết quả final
Thuật toán Đệ quy (Recursive Algorithms)
Thuật toán đệ quy gọi chính nó, thường truyền giá trị trả về làm tham số cho lần gọi tiếp theo. Tham số là đầu vào, giá trị trả về là đầu ra.
Đệ quy là phương pháp đơn giản hóa chia bài toán thành các bài toán con cùng bản chất. Kết quả của một lần đệ quy là đầu vào cho lần đệ quy tiếp theo. Lặp lại theo kiểu tự tương tự. Thuật toán gọi chính nó với giá trị đầu vào nhỏ hơn và đạt kết quả bằng cách thực hiện thao tác trên các giá trị nhỏ hơn. Ví dụ: tính giai thừa, dãy Fibonacci.
Ví dụ: Hàm giai thừa đệ quy
int factorialA(int n) {
return n * factorialA(n-1);
}