Hình 1
Kéo để xoay · giữ shift và kéo để dịch chuyển · nhấp để phân tích từng phần
Cuộn để lật trang
Computer Science A · AP Computer Science A
if, while và for
Một chương trình chạy các câu lệnh lần lượt, theo thứ tự. Hai điều làm thay đổi thứ tự đó: lựa chọn chọn câu lệnh nào chạy, và phép lặp chạy lại các câu lệnh.
Chương trình trong hình bắt đầu với n = 5. Chừng nào n chưa bằng 1, nó chia đôi n nếu chẵn, hoặc nhân ba rồi cộng 1 nếu lẻ, và đếm một bước. Hình thoi ở trên cùng là câu hỏi của vòng lặp; hình thoi bên dưới là của if. Thẻ đỏ là điểm đang thực thi, và mã bên cạnh làm sáng dòng đang chạy.
int n = 5; int steps = 0; while (n != 1) { if (n % 2 == 0) { n = n / 2; } else { n = 3 * n + 1; } steps++; } System.out.println(steps); n đi qua 5, 16, 8, 4, 2, 1. Điều kiện của vòng lặp được kiểm tra 6 lần: đúng 5 lần, rồi sai một lần, và chương trình in 5.
Chương này là Đơn vị 2 của AP Computer Science A, chiếm 25–35% điểm trắc nghiệm: biểu thức Boolean và câu lệnh if (2.1–2.6), vòng lặp while và for (2.7–2.8), các thuật toán chuẩn xây dựng từ chúng (2.9–2.10), vòng lặp trong vòng lặp (2.11), và đếm số lần một câu lệnh chạy (2.12).
ba khối xây dựng
Mọi thuật toán được xây dựng từ ba thứ: tuần tự (các bước theo thứ tự), lựa chọn (một quyết định) và lặp lại (một vòng lặp).
Lựa chọn xảy ra khi cách thuật toán tiếp diễn phụ thuộc vào một quyết định đúng hoặc sai. Lặp lại là một quá trình lặp đi lặp lại cho đến khi đạt kết quả mong muốn. Cả hai đều có trong các chỉ dẫn hằng ngày: “nếu trời mưa thì mang ô” là lựa chọn; “khuấy cho đến khi đường tan” là lặp lại.
Thuật toán có thể được viết bằng lời hoặc vẽ thành lưu đồ: một hộp cho mỗi bước, một hình thoi cho mỗi quyết định đúng hoặc sai, và một mũi tên chạy ngược lên cho phép lặp. Giờ hình viết cùng thuật toán đó bằng lời: “n có chẵn không?”, “chia đôi”, “đếm một bước”. Mã nói đúng điều đó bằng Java.
Thứ tự của các bước làm thay đổi kết quả. Hai đoạn này chứa cùng các câu lệnh:
int x = 3; x = x * 2; x = x + 1;
int x = 3; x = x + 1; x = x * 2;
Đoạn đầu để x bằng 7; đoạn thứ hai, bằng 8. Trong hình, nếu đếm một bước sau vòng lặp thay vì bên trong nó thì sẽ in 1, dù vòng lặp chạy bao lâu.
toán tử quan hệ
Biểu thức Boolean có giá trị là một trong hai giá trị, true hoặc false. Cách đơn giản nhất là so sánh hai giá trị bằng một toán tử quan hệ.
== và != kiểm tra hai giá trị giống hay khác nhau. <, >, <= và >= so sánh các số. Với kiểu nguyên thủy như int, double và boolean, == so sánh chính các giá trị. Với kiểu tham chiếu, nó so sánh các tham chiếu: hai biến có tham chiếu tới cùng một đối tượng không (2.6).
Trong hình, a giữ 7 và b nhận các giá trị 4, 7, 9. Mỗi phép so sánh tạo ra một khối, màu đỏ cho đúng:
| b = 4 | b = 7 | b = 9 | |
|---|---|---|---|
a == b | false | true | false |
a != b | true | false | true |
a < b | false | false | true |
a > b | true | false | false |
a <= b | false | true | true |
a >= b | true | true | false |
= gán; == so sánh. Kết quả Boolean có thể được lưu như mọi giá trị khác: boolean same = a == b;
lựa chọn một nhánh và hai nhánh
Câu lệnh lựa chọn thay đổi việc thực thi tuần tự các câu lệnh. Câu lệnh if chạy các đoạn mã khác nhau tuỳ theo giá trị của một biểu thức Boolean.
Lựa chọn một nhánh (một if) có một đoạn, chỉ chạy khi điều kiện đúng:
if (temp >= 30) { System.out.println("hot"); } System.out.println("done"); Khi temp bằng 34 nó in hot then done; khi bằng 22, chỉ in done. Dòng cuối nằm sau if, nên luôn chạy.
Lựa chọn hai nhánh (một if-else) có hai đoạn: thân của if khi điều kiện đúng, thân của else khi điều kiện sai. Chạy đúng một trong hai.
if (temp >= 30) { System.out.println("hot"); } else { System.out.println("mild"); } System.out.println("done"); Hình cho hai nhiệt độ đi qua nó. Ở 34, thẻ đi vào làn đúng và in hot; ở 22, vào làn sai, mild. Sau đó cả hai đều in done.
if, else if, else
Lựa chọn nhiều nhánh (if-else-if) kiểm tra một dãy điều kiện theo thứ tự. Điều kiện đúng đầu tiên chạy đoạn của nó, và không quá một đoạn được chạy.
if (score >= 90) { grade = "A"; } else if (score >= 80) { grade = "B"; } else if (score >= 70) { grade = "C"; } else { grade = "F"; } Hình thả ba điểm số xuống chuỗi này. 83 không qua score >= 90, qua score >= 80, và bị chặn lại: hạng "B". Các điều kiện bên dưới không bao giờ được kiểm tra. 95 bị chặn ở cổng đầu tiên, "A". 64 không qua cả ba, nên else ở cuối chạy: "F". Nếu không có else ở cuối, một giá trị không qua điều kiện nào sẽ không chạy đoạn nào cả.
Vì điều kiện đúng đầu tiên thắng, nên thứ tự quan trọng. Kiểm tra score >= 70 trước thì 95 nhận "C": mọi điểm từ 70 trở lên đều dừng ở cổng đầu tiên. Hãy đặt phép kiểm tra khắt khe nhất lên đầu.
một if bên trong một if
Câu lệnh if lồng nhau là các câu lệnh if, if-else hoặc if-else-if nằm bên trong một câu lệnh if, if-else hoặc if-else-if khác.
if (age >= 16) { if (hasPermit) { System.out.println("may drive"); } else { System.out.println("needs a permit"); } } System.out.println("done"); Điều kiện bên trong được đánh giá chỉ khi điều kiện bên ngoài đúng. Hình cho ba người đi qua. Tuổi 17 có giấy phép qua cả hai và in may drive. Tuổi 17 không có giấy phép qua phép kiểm tra ngoài và không qua phép kiểm tra trong: needs a permit. Tuổi 14 không qua phép kiểm tra ngoài, nên thẻ đi vòng quanh cả hộp: hasPermit thậm chí không bao giờ được xét tới, và chỉ in done.
Dấu ngoặc nhọn quyết định else thuộc về if nào. Ở đây else nằm trong dấu ngoặc nhọn ngoài, nên nó ghép với if (hasPermit): người dưới 16 tuổi hoàn toàn không nhận được thông báo nào về giấy phép.
!, && và ||
Các toán tử logic ! (not), && (and) và || (or) kết hợp các biểu thức Boolean thành một biểu thức cũng đúng hoặc sai.
!a đúng khi a sai, và sai trong trường hợp còn lại. a && b chỉ đúng khi cả hai đúng. a || b đúng khi a đúng, b đúng, hoặc cả hai. Hình xét mọi tổ hợp, từng hàng một:
| a | b | a && b | a || b | !a |
|---|---|---|---|---|
| true | true | true | true | false |
| true | false | false | true | false |
| false | true | false | true | true |
| false | false | false | false | true |
Thứ tự ưu tiên là ! trước, rồi &&, rồi ||. Vì vậy với a = false, b = true, c = false, biểu thức !a || b && c nghĩa là (!a) || (b && c): true. Nếu nhóm thành (!a || b) && c thì được false. Dấu ngoặc đơn làm thứ tự rõ ràng.
Toán tử quan hệ đứng trước toán tử logic, nên x > 0 && x < 10 so sánh trước rồi kết hợp sau: nó đúng với mọi x nằm chặt giữa 0 và 10.
vế phải có thể không bao giờ chạy
Khi toán hạng bên trái của && hoặc || đã quyết định kết quả, Java không đánh giá toán hạng bên phải. Đây là đánh giá ngắn mạch.
false && anything là sai, và true || anything là đúng, bất kể vế phải nói gì. Vì vậy vế phải bị bỏ qua. Hình đánh giá hai biểu thức, trước với x = 4, rồi với x = 0:
x != 0 && 10 / x > 2 x == 0 || 10 / x > 2
Với x = 4, cả hai vế của cả hai biểu thức đều chạy. 10 / 4 là 2 (phép chia nguyên), không lớn hơn 2, nên biểu thức đầu là false và biểu thức thứ hai cũng vậy.
Với x = 0, x != 0 là sai, nên biểu thức đầu là false ngay lập tức; và x == 0 là đúng, nên biểu thức thứ hai là true ngay lập tức. Trong cả hai, 10 / x đều không chạy, và thế cũng hay: chia một int cho không sẽ ném ra một ArithmeticException.
Điều đó biến toán hạng bên trái thành một chốt chặn. Viết ngược lại, 10 / x > 2 && x != 0 chia trước và bị lỗi khi x bằng 0.
bảng chân trị và định luật De Morgan
Hai biểu thức Boolean là tương đương nếu chúng có cùng giá trị trong mọi trường hợp. Một bảng chân trị, với một hàng cho mỗi tổ hợp đầu vào, có thể chứng minh điều đó.
Định luật De Morgan cho hai phép tương đương:
!(a && b) tương đương với !a || !b !(a || b) tương đương với !a && !b
Để đưa ! vào trong dấu ngoặc đơn, hãy phủ định từng phần và đổi && thành ||, hoặc || thành &&. Trong hình, mỗi cột của biểu thức thứ hai trượt lên biểu thức thứ nhất: các màu khớp nhau ở mọi hàng.
| a | b | !(a && b) | !a || !b | !(a || b) | !a && !b |
|---|---|---|---|---|---|
| true | true | false | false | false | false |
| true | false | true | true | false | false |
| false | true | true | true | false | false |
| false | false | true | true | true | true |
Quên đổi toán tử thì sai: !(a && b) và !a && !b khác nhau ở 2 trong 4 hàng. Một phép so sánh bị phủ định thì đảo toán tử: !(x > 5) là x <= 5. Vậy !(x >= 1 && x <= 10) tương đương với x < 1 || x > 10.
== so với equals
Hai biến khác nhau có thể giữ tham chiếu tới cùng một đối tượng. == và != trên các tham chiếu hỏi liệu chúng có tham chiếu tới cùng một đối tượng hay không, chứ không phải hai đối tượng có cùng nội dung hay không.
String s1 = new String("atlas"); String s2 = s1; String s3 = new String("atlas"); String s4 = null; s2 = s1 sao chép tham chiếu, nên s1 và s2 trỏ vào một đối tượng: s1 == s2 là true. s3 tham chiếu tới một đối tượng thứ hai có cùng các chữ cái: s1 == s3 là false.
Các lớp thường định nghĩa phương thức equals cho biết khi nào hai đối tượng được coi là bằng nhau, thường bằng cách so sánh các thuộc tính của chúng. Phương thức của Sợi dây so sánh các ký tự, nên s1.equals(s3) là true. Hãy so sánh chuỗi bằng equals, đừng bao giờ dùng ==.
Một tham chiếu có thể được so sánh với null bằng == hoặc !=, để biết nó có tham chiếu tới đối tượng nào không: s4 == null là true. (Ghi đè phương thức equals nằm ngoài phạm vi của chương trình học.)
kiểm tra, chạy, kiểm tra lại
Phép lặp là một dạng lặp lại: câu lệnh lặp chạy lại một đoạn mã không hoặc nhiều lần, chừng nào biểu thức Boolean của nó còn đúng.
Trong vòng lặp while, biểu thức Boolean được đánh giá trước mỗi lượt qua thân, kể cả lượt đầu. Khi nó đúng thì thân chạy; khi nó sai thì vòng lặp kết thúc và chương trình tiếp tục sau nó.
int sum = 0; int k = 1; while (k <= 4) { sum += k; k++; } System.out.println(sum); Bảng theo dõi ghi lại các biến mỗi lần điều kiện được kiểm tra. Hình điền nó từng hàng một:
| k | sum | k <= 4 |
|---|---|---|
| 1 | 0 | true |
| 2 | 1 | true |
| 3 | 3 | true |
| 4 | 6 | true |
| 5 | 10 | false |
Điều kiện được kiểm tra 5 lần và thân chạy 4 lần: lần kiểm tra cuối cùng là lần sai. Vòng lặp kết thúc với k = 5, và 10 được in ra.
không bao giờ, mãi mãi, thiếu một
Hầu hết lỗi vòng lặp là một trong ba loại: vòng lặp không bao giờ chạy, không bao giờ dừng, hoặc chạy thừa hay thiếu một lần.
Nếu biểu thức Boolean sai ngay lần đầu thì thân không bao giờ được thực thi. while (k < 5) với k bằng 10 kiểm tra một lần rồi đi tiếp (hàng trên cùng).
Vòng lặp vô hạn xảy ra khi biểu thức Boolean luôn có giá trị đúng. Ở hàng giữa, k đi qua 1, 3, 5, 7, 9, … và không bao giờ bằng 6, nên while (k != 6) không bao giờ trở thành sai. Một vòng lặp mà thân của nó không bao giờ thay đổi các biến trong điều kiện cũng như vậy.
Lỗi lệch một đơn vị là vòng lặp chạy thừa một lần hoặc thiếu một lần. Định in từ 1 đến 5, vòng lặp ở hàng dưới cùng in 1234: while (k < 5) dừng trước 5. k <= 5 sửa được nó.
int k = 1; while (k < 5) { System.out.print(k); k++; } Hãy kiểm tra vòng lặp ở các biên của nó: lượt đầu, lượt cuối, và lần kiểm tra kết thúc nó.
khởi tạo, biểu thức Boolean, cập nhật
Vòng lặp for đặt ba phần của một vòng lặp đếm vào phần đầu của nó: khởi tạo, biểu thức Boolean và cập nhật.
for (int i = 0; i < 3; i++) { System.out.println(i); } Phần khởi tạo chạy một lần, trước lần kiểm tra đầu tiên. Biến mà nó đặt là biến điều khiển vòng lặp. Biểu thức Boolean được đánh giá ngay sau phần khởi tạo, rồi lại được đánh giá sau mỗi lần cập nhật, cho đến khi nó sai. Trong mỗi lượt, phần cập nhật chạy sau toàn bộ thân và trước lần kiểm tra kế tiếp.
Thẻ trong hình đi qua khởi tạo → kiểm tra → thân → cập nhật → kiểm tra …. Số đếm dưới mỗi trạm: khởi tạo 1, kiểm tra 4, thân 3, cập nhật 3. Nó in 0, 1, 2, mỗi số trên một dòng riêng.
Vòng lặp for có thể được viết lại thành vòng lặp while tương đương, và ngược lại:
int i = 0; while (i < 3) { System.out.println(i); i++; } Một điểm khác: i được khai báo trong phần đầu của for chỉ tồn tại bên trong vòng lặp; khai báo trước vòng lặp while thì sau đó nó vẫn còn.
% 10, / 10 và % k
Hai thuật toán chuẩn dùng toán tử lấy phần dư: tách một số nguyên ra từng chữ số, và kiểm tra xem một số nguyên có chia hết cho số khác hay không.
Với int n dương, n % 10 là chữ số cuối của nó và n / 10 (phép chia nguyên) là n đã bỏ chữ số đó. Lặp lại cho đến khi n bằng 0:
| n | n % 10 | n / 10 |
|---|---|---|
| 3725 | 5 | 372 |
| 372 | 2 | 37 |
| 37 | 7 | 3 |
| 3 | 3 | 0 |
int n = 3725; int sum = 0; int max = 0; int odd = 0; while (n > 0) { int d = n % 10; sum += d; if (d > max) { max = d; } if (d % 2 == 1) { odd++; } n /= 10; } Hình tách các chữ số của 3725 từ bên phải, 5, 2, 7, 3, và mỗi chữ số đi qua d.
a % b == 0 đúng chính xác khi a chia hết cho b. 3725 % 5 là 0, nên 3725 chia hết cho 5; 3725 % 3 là 2, nên nó không chia hết cho 3. Cùng phép kiểm tra với 2 phân biệt chẵn với lẻ, như d % 2 == 1 làm trong vòng lặp.
tích luỹ khi vòng lặp chạy
Ba thuật toán chuẩn nữa giữ một giá trị đang chạy trong một biến được khai báo trước vòng lặp và được cập nhật bên trong vòng lặp: tổng, giá trị nhỏ nhất hoặc lớn nhất, và phép đếm.
Tổng bắt đầu từ 0 và cộng thêm từng giá trị: sum += d. Với 3725, sum kết thúc ở 17.
Trung bình là tổng chia cho số lượng giá trị. Hãy chú ý phép chia nguyên:
double avg = (double) sum / 4; int avgInt = sum / 4;
avg là 4.25; avgInt là 4, phần thập phân bị bỏ đi. Hãy ép kiểu trước khi chia, không phải sau.
Giá trị lớn nhất giữ giá trị lớn nhất cho đến lúc này và thay nó mỗi khi gặp giá trị lớn hơn: if (d > max). Ở đây max kết thúc ở 7. Hãy bắt đầu từ giá trị đầu tiên, hoặc từ một giá trị mà không giá trị thực nào có thể nhỏ hơn: 0 dùng được chỉ vì chữ số không bao giờ âm; nói chung hãy dùng Integer.MIN_VALUE. Giá trị nhỏ nhất là ảnh phản chiếu của nó, bắt đầu từ Integer.MAX_VALUE và kiểm tra <; chữ số nhỏ nhất là 2.
Phép đếm số lần một tiêu chí được thoả bắt đầu từ 0 và cộng 1 bên trong một câu lệnh if: if (d % 2 == 1) đếm các chữ số lẻ, có 3 chữ số.
đảo ngược và đếm chuỗi con
Thuật toán trên chuỗi di chuyển một chỉ số dọc theo chuỗi và lấy một chuỗi con tại mỗi vị trí: để tạo chuỗi mới, hoặc để kiểm tra hay đếm các chuỗi con có một tính chất nào đó.
Để đảo ngược một chuỗi, hãy đặt mỗi ký tự lên trước phần đã xây dựng được. substring(i, i + 1) là ký tự đơn tại chỉ số i:
String word = "drawer"; String rev = ""; for (int i = 0; i < word.length(); i++) { rev = word.substring(i, i + 1) + rev; } rev lớn dần "d", "rd", "ard", "ward", "eward", "reward". (rev = rev + word.substring(i, i + 1) sẽ sao chép nguyên từ đó.)
Để đếm các chuỗi con thoả một tiêu chí, hãy trượt một cửa sổ dọc theo chuỗi và kiểm tra từng chuỗi:
String s = "banana"; int count = 0; for (int i = 0; i < s.length() - 1; i++) { if (s.substring(i, i + 2).equals("an")) { count++; } } Cửa sổ substring(i, i + 2) xét "ba", "an", "na", "an", "na": 2 khớp, nên count là 2. Cửa sổ cuối cùng bắt đầu ở chỉ số 4, nên i phải dừng ở dưới s.length() - 1; thêm một bước nữa, substring(5, 7) vượt quá cuối chuỗi và ném ra StringIndexOutOfBoundsException.
So sánh các chuỗi con bằng equals. Để tìm xem có chuỗi con nào mang tính chất đó không, cùng vòng lặp ấy có thể dừng ở chuỗi đầu tiên tìm thấy, hoặc indexOf trả về vị trí một chuỗi con cho trước xuất hiện lần đầu, và −1 nếu không có.
một vòng lặp bên trong một vòng lặp
Phép lặp lồng nhau là một vòng lặp nằm trong thân của một vòng lặp khác. Vòng lặp trong chạy hết mọi lần lặp của nó trước khi vòng lặp ngoài chuyển sang lần lặp tiếp theo.
for (int r = 0; r < 3; r++) { for (int c = 0; c < 4; c++) { System.out.print(r * c + " "); } System.out.println(); } Với r = 0, vòng lặp trong chạy c từ 0 đến 3; rồi println kết thúc dòng, và chỉ khi đó r mới thành 1. Hình ở trên làm sáng lưới từng ô một, hàng này đến hàng khác: thân vòng lặp trong chạy 3 × 4 = 12 lần và in ra
0 0 0 0 0 1 2 3 0 2 4 6
Cận của vòng lặp trong có thể phụ thuộc vào biến của vòng lặp ngoài. Ở đây vòng lặp trong chạy r + 1 lần, nên các lượt lặp là 1, 2, 3, 4:
int count = 0; for (int r = 0; r < 4; r++) { for (int c = 0; c <= r; c++) { count++; } } count kết thúc ở 10, một hình tam giác thay vì hình chữ nhật.
đếm số lần một câu lệnh chạy
Số lần thực thi câu lệnh là số lần một câu lệnh chạy. Thường người ta tìm nó một cách không hình thức, bằng cách lần theo vài lượt lặp và lập luận về các vòng lặp.
for (int i = 0; i < n; i++) { count++; } Với i từ 0 đến n − 1, count++ chạy n lần. Phép kiểm tra i < n chạy n + 1 lần: thêm một lần nữa, để kết thúc vòng lặp.
for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { count++; } } Khi lồng nhau, mỗi lượt trong n lượt của vòng lặp ngoài chạy vòng lặp trong n lần: count++ chạy n × n lần. Với n = 6 đó là 6 so với 36; với n = 8, là 8 so với 64. Hình tăng cả hai khi n tăng lên: nhân đôi n thì một số tăng gấp đôi còn số kia tăng gấp bốn.
Hãy đếm từ cận của vòng lặp. for (int i = 1; i <= n; i++) cũng chạy n lần; i < n bắt đầu từ 1 chạy n − 1; một hình tam giác như ở trang trước chạy 1 + 2 + … + n lần. So sánh các số đếm như vậy là cách để nói vòng lặp này nhanh hơn vòng lặp kia mà không cần đồng hồ bấm giờ.