for and while

Vòng for: lặp một số lần biết trước

Chương trình dưới đọc $n$ rồi in các số từ 1 đến $n$.

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cout << i << ' ';
    }
    cout << '\n';
}

ChạyInput5

Output1 2 3 4 5

Điều cần học nằm ở dòng for (int i = 1; i <= n; i++). Trong ngoặc có ba phần, ngăn nhau bởi hai dấu ;:

• int i = 1 là phần khởi tạo: tạo biến đếm i (loop variable) và gán cho nó giá trị 1. Phần này chạy đúng một lần, trước lượt đầu tiên.
• i <= n là điều kiện, được kiểm tra trước mỗi lượt. Đúng thì chạy thân vòng, sai thì thoát khỏi vòng lặp.
• i++ là phần cập nhật, chạy sau mỗi lượt. Lệnh i++ viết gọn cho i = i + 1.

Phần nằm trong cặp ngoặc nhọn { } là thân vòng. Mỗi lần thân chạy xong gọi là một lượt lặp (iteration).

Ta chạy tay với $n = 3$. Cột i ghi giá trị của i ngay lúc kiểm tra điều kiện.

Khi vòng dừng, i bằng 4 chứ không phải 3: vòng chỉ dừng sau khi i đã vượt qua n. Biến i khai báo trong ngoặc của for chỉ tồn tại bên trong vòng; dùng nó sau dấu } đóng vòng sẽ bị báo lỗi biên dịch.

Dòng for có đúng hai dấu ; trong ngoặc và không có dấu ; nào sau dấu ). Thiếu một dấu trong ngoặc thì trình biên dịch báo lỗi ngay; thừa một dấu sau ) lại biên dịch được nhưng chạy sai, ta sẽ thấy ở mục sau.

Ví dụBảng nhân

Đề. Cho số nguyên $n$ ($0 \le n \le 100$). In mười tích $n \times 1, n \times 2, \dots, n \times 10$, mỗi tích trên một dòng.

Lời giải. Số lượt biết trước là 10 và không phụ thuộc $n$, nên biến đếm i chạy từ 1 tới 10, mỗi lượt in n * i rồi xuống dòng. $n$ chỉ được đọc một lần, trước vòng. Tích lớn nhất là $100 \cdot 10$, vừa int.

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n;
    cin >> n;
    for (int i = 1; i <= 10; i++) {
        cout << n * i << '\n';
    }
}

ChạyInput3

Output3
6
9
12
15
18
21
24
27
30

Đếm xuống, nhảy bước và lỗi lệch một

Cả ba phần trong ngoặc for đều đổi được. Chương trình dưới in các số từ $n$ xuống 1, rồi in các số 1, 4, 7, ... không vượt quá $n$.

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n;
    cin >> n;
    for (int i = n; i >= 1; i--) {
        cout << i << ' ';
    }
    cout << '\n';
    for (int i = 1; i <= n; i += 3) {
        cout << i << ' ';
    }
    cout << '\n';
}

ChạyInput10

Output10 9 8 7 6 5 4 3 2 1
1 4 7 10

Lệnh i-- là i = i - 1, còn i += 3 là i = i + 3. Đếm xuống thì điều kiện cũng phải đổi chiều thành i >= 1; giữ nguyên i <= n thì i cứ giảm mà điều kiện vẫn đúng, vòng không dừng ở 1. Lệnh cout << i << ' ' để lại một dấu cách thừa cuối dòng; trình chấm của các bài ở đây bỏ qua nó.

Lỗi người mới gặp nhiều nhất với vòng lặp là lệch một (off-by-one): vòng chạy nhiều hơn hoặc ít hơn đúng một lượt. Có hai cách viết đáng thuộc lòng:

• Duyệt các số từ $a$ đến $b$, gồm cả hai đầu: for (int i = a; i <= b; i++). Vòng chạy $b - a + 1$ lượt.
• Làm đúng $n$ lần, đếm từ 0: for (int i = 0; i < n; i++). Vòng chạy $n$ lượt, với $i$ từ 0 tới $n - 1$.

Trộn hai cách vào nhau là gây lỗi: đếm từ 1 mà viết i < n thì mất giá trị $n$, với $n = 5$ chỉ in 1 2 3 4. Cách kiểm nhanh là thử $n = 1$ và hỏi vòng có chạy đúng một lượt không.

Lỗi thứ hai là dấu ; thừa ngay sau dấu ):

for (int i = 1; i <= 3; i++);
    cout << "x";

Dấu ; đó là một lệnh rỗng, nên thân vòng là “không làm gì” và được lặp 3 lần. Lệnh cout nằm ngoài vòng, chạy đúng một lần, nên chỉ in ra một chữ x. Trình biên dịch không đọc thụt lề: chỉ cặp { } và dấu ; quyết định lệnh nào thuộc vòng.

Ví dụIn các số chẵn

Đề. Cho số nguyên $n$ ($0 \le n \le 1000$). In các số chẵn từ 0 đến $n$ theo thứ tự tăng dần trên một dòng.

Lời giải. Các số chẵn cách nhau 2, nên bắt đầu từ 0 và nhảy bước i += 2 thay vì duyệt mọi số rồi hỏi i % 2 == 0; vòng chạy nửa số lượt. Điều kiện là i <= n để $n$ chẵn cũng được in. Với $n = 7$ vòng in 0, 2, 4, 6 rồi i lên 8, vượt 7 nên dừng. Với $n = 0$ vòng vẫn chạy một lượt và in số 0, đúng như đề.

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n;
    cin >> n;
    for (int i = 0; i <= n; i += 2) {
        cout << i << ' ';
    }
    cout << '\n';
}

ChạyInput7

Output0 2 4 6

Đọc dữ liệu và cộng dồn trong vòng lặp

Phần lớn vòng lặp trong đề thi làm một việc: đọc $n$ số, mỗi lượt xử lý một số rồi gom kết quả vào vài biến. Khuôn mẫu gồm ba bước: gán giá trị đầu cho các biến trước vòng, cập nhật chúng trong vòng, in kết quả sau vòng. Chương trình dưới tính tổng, số phần tử dương và phần tử lớn nhất của $n$ số.

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n;
    cin >> n;
    long long sum = 0;
    int pos = 0, mx = INT_MIN;
    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        sum += x;
        if (x > 0) {
            pos++;
        }
        if (x > mx) {
            mx = x;
        }
    }
    cout << sum << ' ' << pos << ' ' << mx << '\n';
}

ChạyInput5
3 -4 8 0 -1

Output6 2 8

Lệnh cin >> x nằm trong thân vòng nên mỗi lượt đọc một số, và $n$ lượt thì đọc đủ $n$ số. Biến x khai báo trong thân, mỗi lượt là một biến mới. Ba biến sum (tổng), pos (số phần tử dương), mx (lớn nhất) khai báo ngoài vòng để giữ giá trị từ lượt này sang lượt sau; đặt long long sum = 0; vào trong thân thì mỗi lượt tổng lại về 0.

Bảng dưới cho giá trị các biến sau mỗi lượt của ví dụ. INT_MIN là số int nhỏ nhất, bằng $-2147483648$.

Giá trị đầu quyết định chương trình đúng hay sai. Tổng và biến đếm bắt đầu từ 0. Tích bắt đầu từ 1, vì bắt đầu từ 0 thì tích mãi bằng 0. Số lớn nhất phải bắt đầu từ một giá trị nhỏ hơn mọi dữ liệu: đặt mx = 0 thì với dãy $-5, -2, -9$ chương trình in 0, một số không có trong dãy. Còn khai báo mà không gán (long long sum;) thì biến chứa giá trị rác, mỗi lần chạy có thể ra một kết quả khác.

Tổng của nhiều số nhỏ rất dễ vượt int: $1 + 2 + \dots + 10^5 = 5000050000$, trong khi int chỉ tới $2147483647$. Giai thừa $n! = 1 \cdot 2 \cdot \dots \cdot n$ lớn còn nhanh hơn: $12! = 479001600$ còn vừa int, $13! = 6227020800$ thì không, và long long đủ cho tới $20!$.

Ví dụĐợt mưa liên tiếp

Đề. Ghi chép $n$ ngày ($n \le 1000$), mỗi ngày là 1 (có mưa) hoặc 0 (không mưa), ngày đánh số từ 1. In độ dài đợt mưa liên tiếp dài nhất và ngày bắt đầu của nó; nhiều đợt dài bằng nhau thì chọn đợt sớm nhất; không có ngày mưa thì in 0 0.

Lời giải. Không cần lưu cả $n$ ngày. Gọi cur là số ngày mưa liên tiếp kết thúc đúng tại ngày đang đọc: ngày mưa thì cur tăng 1, ngày khô thì cur về 0. Tại ngày cuối của mỗi đợt, cur bằng đúng độ dài cả đợt, nên đợt dài nhất là giá trị lớn nhất cur từng đạt. Mỗi khi cur > best, ghi lại best = cur và ngày bắt đầu st = i - cur + 1, vì đợt gồm cur ngày kết thúc ở ngày i.

So sánh chặt > giữ lại đợt sớm hơn khi hai đợt dài bằng nhau: đợt sau chỉ bằng chứ không lớn hơn. Viết >= sẽ chọn nhầm đợt muộn. Không có ngày mưa thì cur luôn bằng 0, best và st giữ giá trị đầu 0 0, đúng quy ước của đề.

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n;
    cin >> n;
    int cur = 0, best = 0, st = 0;
    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        if (x == 1) {
            cur++;
        } else {
            cur = 0;
        }
        if (cur > best) {
            best = cur;
            st = i - cur + 1;
        }
    }
    cout << best << ' ' << st << '\n';
}

ChạyInput8
1 1 0 1 1 1 0 1

Output3 4

Vòng while: lặp khi điều kiện còn đúng

Vòng while có dạng while (điều kiện) { thân vòng }. Máy kiểm tra điều kiện trước; đúng thì chạy thân rồi quay lại kiểm tra, sai thì dừng. Nếu điều kiện sai ngay từ đầu, thân vòng chạy 0 lần. while không có chỗ riêng cho khởi tạo và cập nhật: ta tự viết khởi tạo trước vòng và cập nhật trong thân. Vậy for chỉ là cách gom ba phần ấy vào một dòng; hai đoạn dưới làm cùng một việc:

for (int i = 1; i <= n; i++) {
    cout << i << ' ';
}

int i = 1;
while (i <= n) {
    cout << i << ' ';
    i++;
}

Cách chọn: biết trước biến đếm chạy từ đâu tới đâu thì dùng for; chỉ biết điều kiện để dừng thì dùng while. Ví dụ: chia đôi số $n$ liên tục, bỏ phần dư, cho tới khi về 0; cần mấy lần chia? Số lần không đoán ngay được từ $n$, nhưng điều kiện dừng thì rõ: $n = 0$.

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n;
    cin >> n;
    int cnt = 0;
    while (n > 0) {
        n /= 2;
        cnt++;
    }
    cout << cnt << '\n';
}

ChạyInput100

Output7

n /= 2 là n = n / 2, chia nguyên nên phần dư bị bỏ: 25 / 2 là 12. Với $n = 100$, giá trị của $n$ qua các lượt là $100, 50, 25, 12, 6, 3, 1, 0$: bảy phép chia, nên in 7. Ý “chia đôi liên tục” sẽ quay lại ở chặt nhị phân (bài 05).

Mỗi lượt của while phải đưa điều kiện tiến gần tới chỗ sai. Quên dòng n /= 2 thì n không bao giờ đổi, điều kiện đúng mãi và chương trình không dừng: đó là vòng lặp vô hạn (infinite loop). Trên máy mình, bấm Ctrl+C để dừng; trên máy chấm, kết quả là “quá thời gian”. Trước khi viết while, hãy hỏi: biến nào đổi trong thân, và nó đổi theo hướng làm điều kiện sai? Dấu ; thừa sau while (n > 0) cũng gây vô hạn, vì thân vòng thành lệnh rỗng và n không đổi.

Khi đề không cho trước số lượng số, ta đọc tới hết dữ liệu. Biểu thức cin >> x vừa đọc một số vào x, vừa có giá trị đúng nếu đọc được và sai nếu hết dữ liệu, nên while (cin >> x) lặp tới khi đọc hết:

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    long long x, sum = 0;
    int cnt = 0;
    while (cin >> x) {
        sum += x;
        cnt++;
    }
    cout << cnt << ' ' << sum << '\n';
}

ChạyInput4 -2 9
5 1

Output5 17

int i = 1;
while (i <= 3)
    cout << i << ' ';
    i++;

Ví dụGấp đôi đến đích

Đề. Bắt đầu với giá trị 1, mỗi lần nhân đôi giá trị hiện tại. Cho $n$ ($1 \le n \le 10^9$), in số lần nhân đôi ít nhất để giá trị đạt hoặc vượt $n$.

Lời giải. Không biết trước số lần, chỉ biết điều kiện dừng: giá trị $x \ge n$. Vậy while (x < n) nhân đôi x và đếm. Với $n = 9$: $x$ đi $1, 2, 4, 8, 16$, bốn lần nhân. Với $n = 1$ điều kiện sai ngay từ đầu, vòng chạy 0 lượt và in 0, đúng. Lượt cuối có thể đưa $x$ lên gần $2 \cdot 10^9$, sát giới hạn int, nên khai báo x là long long.

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    long long n, x = 1;
    cin >> n;
    int cnt = 0;
    while (x < n) {
        x *= 2;
        cnt++;
    }
    cout << cnt << '\n';
}

ChạyInput9

Output4

break và continue

Đôi khi ta muốn dừng vòng lặp sớm hơn điều kiện của nó. Lệnh break thoát ngay khỏi vòng lặp chứa nó. Lệnh continue bỏ qua phần còn lại của lượt hiện tại và sang lượt kế tiếp.

Ví dụ kinh điển cho break là kiểm tra số nguyên tố: số $n \ge 2$ là số nguyên tố nếu nó không có ước nào trong khoảng từ 2 đến $n - 1$. Ta thử lần lượt từng $d$ và dừng ngay khi gặp ước đầu tiên.

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n;
    cin >> n;
    bool ok = n >= 2;
    for (int d = 2; d < n; d++) {
        if (n % d == 0) {
            ok = false;
            break;
        }
    }
    if (ok) {
        cout << "YES\n";
    } else {
        cout << "NO\n";
    }
}

ChạyInput91

OutputNO

Kiểu bool chỉ có hai giá trị true và false; biến ok ghi nhớ câu “$n$ vẫn có thể là số nguyên tố”, và nó bắt đầu là false với $n = 0$ hay $1$. Với $n = 91$, các $d = 2, 3, 4, 5, 6$ đều không chia hết, tới $d = 7$ thì 91 % 7 == 0 và break chạy: vòng dừng sau 6 lượt thay vì 89. Với số nguyên tố như 97 thì không có ước nào, vòng chạy đủ và ok giữ nguyên true. Thật ra chỉ cần thử $d$ tới $\sqrt n$, ta sẽ làm vậy ở bài 08.

Ví dụ cho continue: cộng các số từ 1 tới $n$, trừ các bội của 3.

for (int i = 1; i <= n; i++) {
    if (i % 3 == 0) {
        continue;
    }
    sum += i;
}

Trong for, continue nhảy tới phần cập nhật i++ rồi mới kiểm tra điều kiện, nên vòng vẫn tiến. Trong while, continue nhảy thẳng về phép kiểm tra: nếu lệnh cập nhật nằm sau continue thì nó bị bỏ qua và vòng có thể không bao giờ dừng.

Ví dụMốc đóng góp

Đề. Có $n$ lượt đóng góp ($n \le 1000$), lượt thứ $i$ góp $a_i$; cần ít nhất $t$. In lượt đầu tiên mà tổng đạt hoặc vượt $t$ và tổng ngay sau lượt đó; không bao giờ đạt thì in -1 0.

Lời giải. Giữ tổng chạy sum. Đọc từng lượt, cộng vào, và ngay khi sum >= t thì ghi lại lượt i, tổng sum, rồi break: các lượt sau không đổi được đáp án. Gán sẵn đáp án -1 0 trước vòng để trường hợp không đạt tự đúng. Với ví dụ, tổng đi $2, 2, 7, 11$ và dừng ở lượt 4.

break khi còn dữ liệu chưa đọc chỉ an toàn vì sau vòng chương trình không đọc gì nữa. Nếu phía sau còn phải đọc tiếp (chẳng hạn một dòng dữ liệu khác), các số chưa đọc của dãy này sẽ bị đọc nhầm vào đó; khi ấy thay break bằng một biến cờ và đọc hết dãy.

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n, t;
    cin >> n >> t;
    int sum = 0, pos = -1, at = 0;
    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        sum += x;
        if (sum >= t) {
            pos = i;
            at = sum;
            break;
        }
    }
    cout << pos << ' ' << at << '\n';
}

ChạyInput5 10
2 0 5 4 1

Output4 11

Tách chữ số bằng % và /

Một số nguyên không có sẵn “chữ số thứ $k$”, nhưng hai phép toán cho ta tách được từng chữ số. n % 10 là phần dư khi chia cho 10, chính là chữ số hàng đơn vị: 5093 % 10 bằng 3. n / 10 là thương nguyên, tức là bỏ chữ số cuối: 5093 / 10 bằng 509. Lặp hai bước này cho tới khi $n = 0$, ta lấy ra mọi chữ số từ phải sang trái.

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n;
    cin >> n;
    while (n > 0) {
        cout << n % 10 << ' ';
        n /= 10;
    }
    cout << '\n';
}

ChạyInput5093

Output3 9 0 5

Số lượt bằng số chữ số, nên với $n \le 10^9$ vòng chạy tối đa 10 lượt; chữ số 0 ở giữa vẫn tính một lượt. Vòng lặp làm thay đổi $n$, nên muốn giữ giá trị gốc thì sao chép trước, ví dụ int m = n;. Với số âm, % cho kết quả âm (-7 % 10 bằng -7), vì thế ở đây ta chỉ làm việc với $n \ge 0$.

Có một chỗ hở: khi $n = 0$, điều kiện n > 0 sai ngay từ đầu, vòng không chạy và chương trình không in chữ số nào, trong khi số 0 có một chữ số. Cách sửa gọn là vòng do ... while: nó chạy thân trước rồi mới kiểm tra điều kiện, nên thân luôn chạy ít nhất một lượt. Dấu ; sau while (n > 0) ở cuối là bắt buộc.

do {
    cout << n % 10 << ' ';
    n /= 10;
} while (n > 0);

Ví dụTổng chữ số

Đề. Cho số nguyên $n$ ($0 \le n \le 10^9$). In tổng các chữ số của $n$.

Lời giải. Chữ số cuối của $n$ là n % 10, và các chữ số còn lại chính là các chữ số của n / 10. Vậy mỗi lượt cộng n % 10 vào sum rồi thay $n$ bằng n / 10, tới khi $n = 0$. Mỗi lượt chuyển đúng một chữ số từ $n$ sang sum, nên khi $n$ về 0 thì sum là tổng mọi chữ số. Với 4027 các chữ số lấy ra là 7, 2, 0, 4, tổng 13. Khác với bài đếm chữ số, $n = 0$ ở đây không cần xét riêng: vòng không chạy và chương trình in 0, đúng với đề.

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n;
    cin >> n;
    int sum = 0;
    while (n > 0) {
        sum += n % 10;
        n /= 10;
    }
    cout << sum << '\n';
}

ChạyInput4027

Output13

Vòng lặp lồng nhau

Thân của một vòng lặp có thể chứa một vòng lặp khác. Với mỗi giá trị của vòng ngoài, vòng trong chạy trọn từ đầu tới cuối, rồi vòng ngoài mới sang giá trị kế. Chương trình dưới in tam giác $n$ dòng, dòng thứ $i$ có $i$ dấu *.

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= i; j++) {
            cout << '*';
        }
        cout << '\n';
    }
}

ChạyInput4

Output*
**
***
****

Vòng ngoài chọn dòng i, vòng trong in i dấu *, hết một dòng thì xuống dòng. Hai biến đếm nên khác tên (i và j); đặt trùng thì vòng trong che mất biến của vòng ngoài. Vị trí của lệnh xuống dòng cũng quan trọng: đặt cout << '\n' trong vòng trong thì mỗi dấu * chiếm một dòng, đặt sau cả hai vòng thì mọi dấu * dính thành một hàng.

Để đếm số lượt của vòng trong, ta cộng qua các giá trị của vòng ngoài: $1 + 2 + \dots + n = \frac{n(n+1)}{2}$, bằng 15 khi $n = 5$. Nếu vòng trong luôn chạy $m$ lượt thì tổng là $n \cdot m$. Con số này cũng là thước đo thời gian: mốc $10^7$ tới $10^8$ thao tác đơn giản mỗi giây chỉ là ước lượng thô. Hai vòng đầy đủ với $n = 1000$ chạy $10^6$ lượt, rất thoải mái. Với $n = 10^5$ chúng chạy $10^{10}$ lượt, quá xa giới hạn; khi đó cần một ý tưởng khác chứ viết nhanh hơn cũng không cứu được.

break chỉ thoát vòng trong cùng chứa nó. Muốn thoát cả hai vòng thì cần thêm một biến cờ bool, hoặc đưa hai vòng vào một hàm rồi dùng return (bài B4).

Ví dụKhung bảng

Đề. In một hình chữ nhật $h$ dòng, $w$ cột ($1 \le h, w \le 30$): ô thuộc biên in *, ô bên trong in ., không chèn dấu cách. Chỉ có một dòng hoặc một cột thì mọi ô đều thuộc biên.

Lời giải. Vòng ngoài duyệt dòng i từ 1 tới $h$, vòng trong duyệt cột j từ 1 tới $w$, và mỗi ô tự hỏi mình có nằm ở biên không: dòng đầu, dòng cuối, cột đầu hoặc cột cuối, tức i == 1 || i == h || j == 1 || j == w. Trường hợp một dòng hay một cột không cần xét riêng: khi $h = 1$ thì mọi ô đều có i == 1. Hết một dòng thì xuống dòng, đặt sau vòng trong.

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int h, w;
    cin >> h >> w;
    for (int i = 1; i <= h; i++) {
        for (int j = 1; j <= w; j++) {
            if (i == 1 || i == h || j == 1 || j == w) {
                cout << '*';
            } else {
                cout << '.';
            }
        }
        cout << '\n';
    }
}

ChạyInput3 5

Output*****
*...*
*****