2.9 Implementing Selection and Iteration Algorithms

Jump to topic

Unit 2 · Selection and Iteration · Topic 2.9

Implementing Selection and Iteration Algorithms

Skill 2.ASkill 3.ASkill 4.A

Big idea: A handful of loop patterns (sum, count, min/max, digits, divisibility) solve most problems. Learn them as templates.

Learning objectives

Develop code for standard and original algorithms (without data structures) and determine the result of these algorithms.

Sum, count, and average

Code

int sum = 0;
int evens = 0;
for (int n = 1; n <= 10; n++) {
  sum += n;
  if (n % 2 == 0) {
    evens++;
  }
}
double avg = (double) sum / 10;
System.out.println(sum + " " + evens + " " + avg);

Output

55 5 5.5

Minimum and maximum

Start the running max at the first value or at Integer.MIN_VALUE, never at 0, in case every value is negative.

Code

int max = Integer.MIN_VALUE;
int min = Integer.MAX_VALUE;
for (int x = -8; x <= -2; x += 3) {
  if (x > max) max = x;
  if (x < min) min = x;
}
System.out.println(min + " " + max);

Output

-8 -2

Divisibility and digits

Code

int n = 36;
int factors = 0;
for (int d = 1; d <= n; d++) {
  if (n % d == 0) factors++;
}
System.out.println("36 has " + factors + " factors");
int num = 9045;
int reversed = 0;
while (num > 0) {
  reversed = reversed * 10 + num % 10;
  num /= 10;
}
System.out.println(reversed);

Output

36 has 9 factors
5409

Stop early with a flag

To check whether any value meets a condition, stop as soon as you find one. To check whether all do, stop as soon as one fails.

Code

int n = 91;
boolean prime = n > 1;
for (int d = 2; d * d <= n && prime; d++) {
  if (n % d == 0) prime = false;
}
System.out.println(prime);

Output

false

Key points

Divisibility: n % d == 0.
Digits: n % 10 is the last digit; n / 10 removes it.
Count matches, find min/max, compute sum and average.

Watch out

Start a max at the first value (or Integer.MIN_VALUE), not 0, when values can be negative.
Cast before dividing for an average: (double) sum / count.
Initialize accumulators before the loop, not inside it.

Quick check

What does this compute for n = 5?

int r = 1;
for (int i = 2; i <= n; i++) r *= i;

Show answer

120, which is 5 factorial.

Practice 2.9 (11 questions)