Mục lục bài họcĐang ở d02-b4
Nested Loops and String Traversal
Nested loops
When a loop appears inside another loop, the inner loop runs to completion on every single pass of the outer loop. If the outer loop makes m passes and the inner loop makes n passes each time, the innermost statement runs m * n times. The count is a product, not a sum.
When the inner bound depends on the outer variable, the total is a sum rather than a product. For for (int i = 0; i < n; i++) for (int j = i; j < n; j++) the inner loop runs n, then n-1, then n-2 passes, so the total is n(n+1)/2.
Traversing a String
Strings are traversed by index. The two methods used constantly are s.length() and s.substring(i, i + 1), which returns the one-character string at index i. Comparison uses .equals(...), never ==.
To examine a pair of neighbouring characters, use s.substring(i, i + 2). The loop bound must then be i < s.length() - 1, because the last starting position for a two-character window is s.length() - 2. Every window of width w shortens the usable range by w - 1.
Vòng lặp lồng nhau
Vòng trong chạy trọn vẹn ở mỗi lượt của vòng ngoài. Vòng ngoài m lượt, vòng trong n lượt mỗi lần thì câu lệnh trong cùng chạy m * n lần. Đây là phép nhân, không phải phép cộng — nhầm chỗ này là hỏng cả câu đếm lẫn câu phân tích thời gian chạy.
Khi cận của vòng trong phụ thuộc vào biến vòng ngoài thì tổng không còn là tích. Với for (int i = 0; i < n; i++) for (int j = i; j < n; j++), vòng trong chạy lần lượt n, n−1, n−2, … lượt, nên tổng là n(n+1)/2. Cách chắc chắn nhất là viết ra vài dòng đầu rồi cộng, đừng đoán công thức.
Duyệt chuỗi
Chuỗi được duyệt theo chỉ số. Hai phương thức dùng liên tục: s.length() và s.substring(i, i + 1) lấy ra chuỗi một ký tự ở vị trí i. So sánh nội dung luôn dùng .equals(...), không dùng ==.
Muốn xét một cặp ký tự cạnh nhau thì dùng s.substring(i, i + 2), và cận vòng lặp phải hạ xuống i < s.length() - 1, vì vị trí bắt đầu cuối cùng của cửa sổ rộng 2 là s.length() - 2. Quy tắc chung: cửa sổ rộng w làm ngắn dải chỉ số đi w − 1.
j khởi đầu từ i chứ không từ 0. Cộng theo dòng: 5 + 4 + 3 + 2 + 1 = 15, đúng bằng n(n+1)/2 với n = 5. Hai lỗi cùng nằm trên hình: đếm cả 25 ô là quên cận trong phụ thuộc vòng ngoài; đếm 10 ô là dùng j = i + 1 — tức bỏ mất đường chéo, đúng một ô mỗi dòng.Chuỗi word có ít nhất hai ký tự. Đoạn mã dưới đây đếm số lần chuỗi con "an" xuất hiện. Cho biết kết quả với word = "banana", rồi giải thích vì sao cận vòng lặp là word.length() - 1.
int count = 0;
for (int i = 0; i < word.length() - 1; i++) {
if (word.substring(i, i + 2).equals("an")) {
count++;
}
}Liệt kê từng cửa sổ. Chuỗi "banana" dài 6, nên i chạy từ 0 tới 4:
| i | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| cửa sổ | ba | an | na | an | na |
Hai cửa sổ khớp "an", tại i = 1 và i = 3. Kết quả count bằng 2.
Vì sao cận là length() - 1. Cửa sổ rộng 2 nên vị trí bắt đầu cuối cùng phải là 4, tức length() - 2. Điều kiện i < length() - 1 cho đúng giá trị lớn nhất là 4. Viết i < word.length() thì lượt i = 5 gọi substring(5, 7) và ném ngoại lệ.
Chú ý cửa sổ chồng nhau. Vòng lặp này đếm cả các lần xuất hiện chồng lấn, vì i tăng 1 mỗi lượt. Muốn đếm không chồng lấn thì phải nhảy i += 2 khi khớp — hai bài toán khác nhau, đề luôn nói rõ mình hỏi cái nào.
i < s.length() khi đổi từ cửa sổ một ký tự sang cửa sổ hai ký tự. Vòng lặp chạy đúng cho tới lượt cuối rồi mới nổ, nên bài thử với chuỗi ngắn có khi vẫn qua. Cách chặn: mỗi lần viết substring(i, i + w), hạ ngay cận xuống i < s.length() - w + 1 trong cùng một thao tác — sửa cửa sổ mà chưa sửa cận thì đừng chuyển sang dòng khác.w thì cận trên hạ xuống s.length() - w. So sánh chuỗi luôn bằng .equals.Đọc xong rồi — làm thử ngay
Bài tập của chương Unit 2 — Selection and Iteration gồm 14 câu trắc nghiệm và 8 đề tự luận. Đáp án hiện ngay khi chọn, miễn phí.