Thuật toán - hay còn gọi là giải thuật - là khái niệm quan trọng nhất trong Tin học. Nó là nền tảng cho mọi khía cạnh của Tin học. Khái niệm về thuật toán đã tồn tại từ thời cổ đại, sớm nhất ở đế chế Babylonia với thuật toán chia vào năm 2500 TCN. Khái niệm về thuật toán có thể phát biểu như sau:
Thuật toán là một dãy hữu hạn các bước, mỗi bước mô tả chính xác các phép toán hoặc hành động cần thực hiện để giải quyết một vấn đề.
Với sự phát triển chóng mặt của khoa học máy tính, các thuật toán cũng ngày càng phát triển về số lượng cũng như chất lượng. Trong phạm vi của lập trình thi đấu, chúng ta sẽ tập trung nghiên cứu chuyên sâu về các thuật toán từ dễ đến khó, phục vụ cho các kỳ thi về thuật toán như HSG Tin học, Tin học trẻ hay các kỳ thi thuật toán online. Toàn bộ các cài đặt sẽ được viết ở ngôn ngữ C++ vì như đã nói ở các chuyên đề lập trình cơ bản, C++ là một ngôn ngữ rất mạnh trong lập trình thi đấu.
2. Các đặc trưng của thuật toán
Mỗi thuật toán luôn luôn có đủ 55 đặc trưng sau:
- Có đầu vào [Input]: Thuật toán nhận dữ liệu vào từ một tập nào đó.
- Có đầu ra [Output]: Từ dữ liệu đầu vào, thuật toán sẽ tính toán và đưa ra kết quả tương ứng với đầu vào đó.
- Tính chính xác: Các bước của thuật toán được mô tả chính xác.
- Tính hữu hạn: Thuật toán cần phải đưa ra được output sau một số hữu hạn các bước với mọi input.
- Tính đơn trị: Các kết quả trung gian của từng bước thực hiện thuật toán được xác định một cách đơn trị và chỉ phụ thuộc và input và kết quả của các bước trước.
- Tính tổng quát: Thuật toán có thể áp dụng để giải mọi bài toán có cùng dạng với bài toán đã giải.
Chẳng hạn, dưới đây là thuật toán tìm số ước của một số nguyên dương NN được viết trong một hàm int count_divisors[int N]
int count_divisors[int N]
{
int divisors = 0;
for [int i = 1; i n; // [2]
int s1 = 0; // [3]
for [int i = 1; i