选择与迭代

Algorithms 算法 are built from three control structures 控制结构: sequence 顺序 (steps in order), selection 选择 (choosing a path), and iteration 迭代 (repeating steps). This topic covers selection and iteration – the tools that let a program make decisions and loop.

A boolean expression 布尔表达式 evaluates to true or false, using relational operators 关系运算符: == (equal), != (not equal), <, >, <=, >=. Note == compares primitive values 基本类型值 but object references 对象引用 for objects, so use .equals for Strings.

Worked example. With int a = 7, b = 3; and String s = "cat";:

A common mistake is = for ==: if (a = 7) does not compile, because = assigns and gives an int, not a boolean.

An if statement 条件语句 runs a block 代码块 only when its condition 条件 is true; an optional else gives an alternative:

if (score >= 60) {
    System.out.println("Pass");
} else {
    System.out.println("Fail");
}

Common mistakes.

• A semicolon after the condition ends the if: in if (x > 0); { count++; } the block runs every time.
• Without braces only one statement belongs to the if. Below, "Done" prints whatever t is, despite the indentation:

if (t > 30)
    System.out.println("Hot");
    System.out.println("Done");

Placing an if inside another, or chaining with else if, tests several cases in order. Only the first matching branch 分支 runs:

if (g >= 90) grade = 'A';
else if (g >= 80) grade = 'B';
else grade = 'C';

Worked example. The order of the tests matters. This version never gives an 'A':

if (g >= 80) grade = 'B';
else if (g >= 90) grade = 'A';   // never reached for g >= 90
else grade = 'C';

For g = 95 the first test is already true, so 'B' is chosen and the rest is skipped. With ranges, test the narrowest case first (highest mark first), as in the correct version above. If the chain used separate if statements without else, every true test would run and the last one would win.

Logical operators 逻辑运算符 combine conditions: && (and – both true), || (or – at least one true), ! (not – reverse). Java uses short-circuit evaluation 短路求值: && stops if the left side is false, and || stops if the left side is true – useful to guard against 防止 errors, e.g. if (n != 0 && total / n > 5).

Worked example. Evaluate !(x > y) || x < 5 && y == 6 for x = 4, y = 6. The order is !, then &&, then ||:

1. x > y is 4 > 6, false, so !(x > y) is true.
2. x < 5 && y == 6 is true && true, true.
3. true || true is true. In fact, step 2 is never run: || already has true on its left and short-circuits.

Short-circuiting changes what runs. In if (s != null && s.length() > 0) the null check must come first; the other order throws a NullPointerException when s is null.

De Morgan's laws 德摩根定律 rewrite negations: !(a && b) equals !a || !b, and !(a || b) equals !a && !b. Two boolean expressions are equivalent 等价 if they give the same result for every input – a truth table 真值表 proves it. Simplifying conditions this way is a common exam task.

Worked example. Write !(age >= 13 && age <= 19) without the !.

1. De Morgan: !(age >= 13) || !(age <= 19) (the && becomes ||).
2. Negate each comparison: !(age >= 13) is age < 13; !(age <= 19) is age > 19.
3. Result: age < 13 || age > 19, every age outside the teens.

Check one value of each kind: age = 15 gives false in both; age = 25 gives true in both. A common error is to negate >= as <=: the opposite of >= is <.

A while loop 当型循环 repeats while its condition stays true, testing before each pass. You must change something inside so the loop eventually stops, or it becomes an infinite loop 无限循环:

int i = 0;
while (i < 5) {
    System.out.println(i);
    i++;
}

Worked example. Trace a loop that adds the digits of n = 472:

int n = 472, sum = 0;
while (n > 0) {
    sum += n % 10;   // last digit
    n /= 10;         // drop it
}

After pass 3 the test n > 0 is false, so the loop stops with sum = 13. If n started at 0, the body would run zero times: a while loop tests before the first pass.

A for loop packs initialization 初始化, condition, and update 更新 into one line – best when you know the count:

for (int i = 0; i < n; i++) {
    // runs n times, i = 0..n-1
}

A for and an equivalent while do the same work; be able to convert between them.

Worked example. How many times does this run, and what does it print?

for (int k = 10; k > 0; k -= 3)
    System.out.print(k + " ");

k takes the values 10, 7, 4, 1; the next value, $-2$, fails k > 0. So it runs 4 times and prints 10 7 4 1. The equivalent while moves the three parts apart:

int k = 10;
while (k > 0) {
    System.out.print(k + " ");
    k -= 3;
}

A loop for (int i = a; i < b; i++) runs $b - a$ times; with <= it runs $b - a + 1$ times. A variable declared in the for header, such as k, cannot be used after the loop.

Combine loops and conditions to solve real problems – count, sum, find a maximum, or test a property:

int max = arr[0];
for (int k = 1; k < arr.length; k++) {
    if (arr[k] > max) max = arr[k];
}

Two integer patterns the exam tests directly use % and /. For a nonnegative integer 整数 n, read its digits 数字位 one at a time by taking n % 10 (the last digit) and then n = n / 10 (drop it). For nonzero d, n % d == 0 tests divisibility 整除性: n is evenly divisible by d. Combine them with a counter 计数器 to find the frequency 频率 with which some criterion 条件标准 is met.

Worked example. Count the numbers from 1 to 20 that are divisible by 3 but not by 2.

int count = 0;
for (int i = 1; i <= 20; i++) {
    if (i % 3 == 0 && i % 2 != 0) {
        count++;
    }
}

The multiples of 3 are 3, 6, 9, 12, 15, 18; the odd ones are 3, 9, 15, so count is 3. The counter starts at 0 before the loop; resetting it inside the loop is a common error.

Standard patterns like a running total 累加和, a counter, or a flag 标志 (a boolean that records whether something happened) recur throughout the course.

Loop through a string by index 索引 to process each character 字符:

for (int i = 0; i < s.length(); i++) {
    char c = s.charAt(i);
    // count vowels, reverse, check for a substring, ...
}

Typical tasks: count occurrences 出现次数, build a reversed or filtered copy, or test whether one string contains another.

Worked example. Count how many times "ana" occurs in "banana", overlaps included.

String s = "banana", t = "ana";
int count = 0;
for (int i = 0; i <= s.length() - t.length(); i++) {
    if (s.substring(i, i + t.length()).equals(t)) {
        count++;
    }
}

i runs from 0 to $6 - 3 = 3$, checking "ban", "ana", "nan", "ana": count is 2. With i < s.length() instead, substring(4, 7) is past the end and throws a StringIndexOutOfBoundsException.

A nested loop 嵌套循环 puts one loop inside another; the inner loop 内层循环 completes fully for each pass of the outer loop 外层循环. If the outer runs $n$ times and the inner $m$ times, the body runs $n\times m$ times – the basis for processing grids 网格 and comparing all pairs.

Worked example. What does this print?

for (int r = 1; r <= 3; r++) {
    for (int c = 1; c <= r; c++) {
        System.out.print(c);
    }
    System.out.println();
}

The println is inside the outer loop but outside the inner one, so it ends each row.

Run-time analysis 运行时间分析 counts how many basic steps an algorithm takes as the input size $n$ grows. Count the executions of the innermost statement: with constant work per iteration, visiting each of $n$ items once is linear 线性 ($n$ steps); two full nested loops of $n$ iterations each are quadratic 平方级 ($n^2$). This informal counting lets you compare two algorithms' efficiency 效率.

Exam skill: for a nested loop, be able to state how many times the inner statement runs in terms of the loop bounds – a frequent multiple-choice question.

Worked example. How many stars does this print?

for (int i = 0; i < 4; i++)
    for (int j = 0; j < i; j++)
        System.out.print("*");

The inner loop runs i times for each outer i: 0 + 1 + 2 + 3 = 6 stars. When the inner bound is the outer variable, the total is the triangular sum $0+1+\dots+(n-1)=\dfrac{n(n-1)}{2}$ – here $\dfrac{4\times3}{2}=6$ – not the full $n^2=16$ of a rectangular nested loop.

• Get boundary conditions 边界条件 right: use < vs <= deliberately, and watch the first and last iteration of every loop (off-by-one 差一错误 is the classic bug 缺陷).
• Build compound conditions with &&, ||, ! and remember short-circuit evaluation (put the null check first).
• Trace nested loops by counting how many times the inner body runs in total.
• Choose the right structure — if/else if for ranges, a loop for repetition — and avoid an infinite loop by updating the loop variable 循环变量.
• Apply De Morgan's laws when you simplify or negate a boolean condition.