Tư duy thuật toán, Phần 1: Vòng lặp là nút 'lặp lại' của code

Đây là bài 1 trong series 13 phần đi theo thứ tự: vòng lặp → điều kiện → biến → tổng hợp điều kiện → logic đường đi → vòng lặp lồng nhau → hoán vị → Big O → đệ quy → điều hướng mê cung → depth-first search → graph → bảng. Mỗi bài xây trên bài trước; đến cuối series bạn sẽ có đủ nền tảng để tự viết thuật toán DFS giải mê cung từ đầu. Bắt đầu từ đây.

Vòng lặp thực sự làm gì

Máy tính chỉ thực thi một lệnh tại một thời điểm, theo thứ tự. Vòng lặp là cấu trúc nói rằng: "trước khi đi tiếp, quay lại làm khối lệnh này lần nữa — và lần nữa — cho đến khi một điều kiện nào đó báo dừng." Mọi thứ khác về vòng lặp chỉ là chi tiết đắp thêm lên ý tưởng duy nhất đó.

Ba dạng vòng lặp

Đếm trước (for) — bạn biết trước số lần lặp:

for (int i = 0; i < 5; i++)
{
    Console.WriteLine($"Lần {i}");
}

i là biến lặp, i < 5 là điều kiện được kiểm tra trước mỗi lần lặp, và i++ chạy sau mỗi lần lặp. Cả ba nằm chung trong phần khai báo for nên logic lặp lại ở một chỗ duy nhất thay vì rải rác khắp hàm.

Theo điều kiện (while) — bạn không biết số lần lặp, chỉ biết điều kiện dừng:

int remaining = LoadQueue().Count;
while (remaining > 0)
{
    remaining = ProcessNext();
}

Dùng while khi số lần lặp phụ thuộc vào trạng thái lúc chạy — một hàng đợi đang vơi dần, một thuật toán tìm kiếm đang hội tụ, một socket phát dữ liệu cho đến khi đóng.

Theo tập hợp (foreach) — bạn có một dãy phần tử và muốn duyệt qua từng phần tử, không quan tâm chỉ số:

foreach (var order in orders)
{
    Ship(order);
}

foreach chính là for nhưng phần đánh chỉ số và kiểm tra biên đã được làm sẵn. Hãy dùng nó trước; chỉ quay về for khi bạn thực sự cần chỉ số hoặc cần bỏ qua/nhảy bước không tuần tự.

Lỗi mà vòng lặp nổi tiếng gây ra

Lỗi off-by-one đến từ việc điều kiện bạn viết không khớp với phạm vi bạn thực sự muốn:

for (int i = 0; i <= items.Length; i++) // lỗi: phải là <
{
    Console.WriteLine(items[i]); // ném lỗi ở lần lặp cuối
}

items.Length là một số lượng hợp lệ, không phải một chỉ số hợp lệ — chỉ số chạy từ 0 đến Length - 1. Cách sửa trở thành phản xạ một khi bạn hiểu rõ nó: dùng < chặt khi đếm tới một độ dài, dùng <= khi đếm tới một giá trị lớn nhất bao gồm cả điểm cuối mà bạn thực sự muốn chạm tới.

Vì sao series thuật toán bắt đầu từ đây

Mọi kỹ thuật sau này trong series đều là một vòng lặp khoác áo khác. Tìm kiếm là vòng lặp dừng sớm. Đệ quy (bài 9) là vòng lặp mà việc "quay lại lặp" diễn ra qua call stack thay vì phần khai báo for. Depth-first search (bài 11) là vòng lặp qua các đỉnh kề của một graph, được thực hiện bằng đệ quy. Hãy làm quen với "lặp lại cho đến khi điều kiện đúng" ngay bây giờ, phần còn lại của series chủ yếu nói về việc bạn đang lặp trên cái gì, chứ không phải cách lặp mới.

Tiếp theo: Điều kiện — cách một vòng lặp quyết định hành xử khác đi ngay giữa lúc đang lặp.