Basic loop algorithms

Section 5.3 Basic loop algorithms

Now that we have the basics of if statements and for and while loops under our belts, we’re ready to implement some actual algorithms. There are quite a few algorithms we can build out of a single loop with an occasional if inside the body of the loop. In later units we will apply these ideas to to data types like String, arrays, ArrayList which contain multiple elements and are naturally processed with loops. But in this section we will stick with loops dealing with the data types we’ve already learned, mostly int and double.

🔗

We’ll start with algorithms for counting, summing, and averaging sequences of numbers. Then we’ll look at finding the minimum and maximum values within a sequence of numbers. And finally we’ll take apart an int value, using a loop to extract the individual digits.

🔗

Subsection 5.3.1 Summing and counting

Lots of loop algorithms use an accumulator pattern to accumulate some kind of value by updating a variable each time the loop body runs. The value of the accumulator variable when the loop is complete is the result the algorithm is intended to compute. If you’ve ever counted on your fingers you already understand the basic idea. In this section we’ll apply the accumulator pattern to summing, counting, and averaging algorithms.

🔗

The accumulator pattern has three parts:

🔗

An accumulator variable that is initialized before the loop.
🔗

🔗
A loop that loops sum number of times to produce the values we want to distill into our accumulator variable.
🔗

🔗
Code in the body that updates the accumulator variable in some way.
🔗

🔗

🔗

Note, the accumulator variable is different than the loop variable that controls the loop itself; this is a variable that is going to hold the eventual answer we are trying to compute such as a count or a sum.

🔗

Let’s start with a really simple example. This loop calculates the sum of the numbers from one to one hundred. The variable sum is the accumulator variable while i is the loop variable.

🔗

int sum = 0;
for (int i = 1; i <= 100; i++) {
    sum += i;
}
System.out.println("The sum of 1 through 100 is " + sum);

The first line initializes the accumulator variable sum to 0. In general we should initialize the variable to the value that would be the right answer if the loop didn’t run at all. That is, if instead of adding up one hundred numbers we were adding up no numbers at all, what would the sum be? Zero. So that’s our initial value.

🔗

Then each time through the loop, sum is incremented by the current value of i and as a result when the loop ends sum is the total we want.

🔗

For the next few examples, let’s assume we are working in a program for anayzing rainfall data in which we have a method nextMeasurement() which every time it is called returns a double representing an amount of rainfall per hour from some sequence of data.

🔗

We can implement a summing loop to get the total rainfall from the next day’s worth of hourly measurements:

🔗

double total = 0;
for (int i = 0; i < 24; i++) {
    total += nextMeasurement();
}
System.out.println(total + " cm of total rainfall.");

A loop for counting is similar to a summing loop, but instead of adding up values, it counts how many times through the loop the value meets some criteria. For instance, suppose we wanted to count how many hours we measured more than twelve centemeters of rain.

🔗

int count = 0;
for (int i = 0; i < 24; i++) {
    if (nextMeasurement() > 12.0) {
        count++;
    }
}
System.out.println(total + " hours with over 12.0 cm of rainfall.");

If we compare this loop to the summing loop we can see the two key difference between summing and counting: when counting we only increase the accumulator by one each time, usually with ++, and we use an if to decide when to update it at all. For instance, this loop looks at all the measurements from a twenty-four hour period but only counts the ones that satisfy the criteria. Finally, the accumulator when we’re counting is typically an int since we don’t need any fractional parts while in a summing loop in might be an int or a double, depending on what the values we’re summing are.

🔗

On the AP exam, they often will provide a method to call to get a boolean that determines whether something should be counted or not. For instance, continuing the theme of previous example, they might provide a method, extraRainy, that takes a measurement and returns true if it qualifies as extra rainy and should be counted. To use such a method, just call it in the condition of the if:

🔗

int count = 0;
for (int i = 0; i < 24; i++) {
    if (extraRainy(nextMeasurement())) { // change the condition to use the provided method
        count++;
    }
}
System.out.println(total + " extra rainy hours.");

🔗

Subsection 5.3.2 Averaging

Averaging isn’t really its own separate loop pattern. Since the average of a set of values is the sum of the values divided by the count, we just need to combine summing and counting. And in a simple average computation we don’t even need to count the values separately because we may know how many there are. For instance here’s a loop to get the average rainfall in a day:

🔗

double total = 0;
for (int i = 0; i < 24; i++) {
    total += nextMeasurement();
}
System.out.println("Average rainfall: " + total / 24);

But if we wanted to do something more complicated like getting the average of just the hours with more than twelve centemeters of rainfall, we could combine the summing and counting patterns:

🔗

double total = 0;
int count = 0;
for (int i = 0; i < 24; i++) {
    double m = nextMeasurement();
    if (m > 12.0) {
        total += nextMeasurement();
        count++;
    }
}
System.out.println("Average rainfall in rainy hours: " + total / count);

Try the accumulator practice below.

🔗

Activity 5.3.1.

Complete the methods below to compute the sum and average of a set of numbers.

🔗

public class Accumulator {
    // sum calculates and returns the sum of the numbers 1 to n
    public static int sum(int n) {
        int sum = 0;
        // 1. Add a loop to calculate the sum of 1 to n

return sum;
    }

// average calculates and returns the average of numbers 1 to n
    public static double average(int n) {
        int sum = 0;
        // 2. Add a loop to calculate the sum of 1 to n

// 3. Calculate the average using sum and n
        double average = 0;

return average;
    }

public static void main(String[] args) {
        int n = 10;
        System.out.println("The sum of 1 to " + n + " is " + sum(n));
        System.out.println("The average of 1 to " + n + " is " + average(n));
    }
}
====
import static org.junit.Assert.*;

import org.junit.*;

import java.io.*;

public class RunestoneTests extends CodeTestHelper
{
    public RunestoneTests()
    {
        super("Accumulator");
    }

@Test
     public void test1() throws IOException
     {
         String code = getCode();
         String target = "for (int * = 1; * ? n; *~)";

int num = countOccurencesRegex(code, target);

boolean passed = num == 2;

getResults("2", "" + num, "Each method should have a for loop that counts from 1 to n", passed);
        assertTrue(passed);
     }

@Test
    public void testMain() throws IOException
    {
        String expected = "The sum of 1 to 10 is 55\nThe average of 1 to 10 is 5.5";
        String output = getMethodOutput("main");
        boolean passed = getResults(expected, output, "Checking main output");
        assertTrue(passed);
    }

@Test
   public void testCall() throws IOException
   {
       Object[] args = {5};
       String output = getMethodOutput("sum", args);
       String expect = "15";

boolean passed =
               getResults(
                       expect,
                       output,
                       "sum(5)"
                       );
       assertTrue(passed);
   }
}

🔗

We can also use a while loop to calculate the average of an arbitrary number of numbers given to us as input from the user. Intead of a loop that runs a specific number of times, the loop runs as long as the number provided by the user is not -1.

🔗

// 1. initialize the loop variable (get the first number)
System.out.print("Please enter a number to average in or -1 to stop: ");
number = scan.nextInt();

// 2. test the loop variable (against sentinel value)
while (number != -1)
{
  sum += number; // add number to sum
  count++; // count the number
  // 3. Update the loop variable (get a new number)
  System.out.print("Please enter a number to average in or -1 to stop: ");
  number = scan.nextInt();
}
System.out.println(count);
// calculate average
average = (double) sum/count;
System.out.println("The average is " + average);

You can try this below on the input numbers below the code or for more interactive input, try it in your own IDE online with JuiceMind or replit.

🔗

Activity 5.3.2.

Try the code below with an input-controlled loop that prints out the numbers entered by the user until -1 is entered. Then, change it to calculate the sum and average of the numbers entered.

🔗

import java.util.Scanner;

public class InputLoop
{
  public static void main(String[] args)
  {
      Scanner scan = new Scanner(System.in);
      // Initialize the accumulators
      int sum = 0;
      int count = 0;

// Initialize the loop variable (get the first number)
      System.out.print("Please enter a number to average in or -1 to stop: ");
      int number = scan.nextInt();

// Test the loop variable against sentinel value
      while (number != -1)
      {
          // 1. TODO: add number to sum and increment count

// Update the loop variable (get a new number)
          System.out.println("You entered " + number);
          System.out.print("Please enter a number to average in or -1 to stop: ");
          number = scan.nextInt();
      }
      System.out.println("You entered " + count + " numbers.");
      System.out.println("Their sum is " + sum);

// 2. TODO: calculate average
      double average = 0;

System.out.println("The average is " + average);
  }
}
====
import static org.junit.Assert.*;

import org.junit.*;

import java.io.*;

public class RunestoneTests extends CodeTestHelper
{
    public RunestoneTests()
    {
        super("InputLoop");
    }
    @Test
    public void test1()
    {
        String input = "80 90 100 -1";
        String output = getMethodOutputWithInput("main", input);

boolean passed = getResults("The average is 90.0", output, "Average calculated correctly");

assertTrue(passed);
    }

@Test
    public void test2()
    {

String input = "1 4 -1";
        String output = getMethodOutputWithInput("main", input);

boolean passed = getResults("The average is 2.5", output, "Trying with input 1 4 -1 (did you typecast to double?)");

assertTrue(passed);
    }
  }

🔗

Subsection 5.3.3 Finding minimums and maximums

Another variation of the accumulator pattern is a loop that updates the accumulator with the value returned by some method that takes the current value of the accumulator and the new value in each iteration. Two commonly used methods in this pattern are Math.min and Math.max that we discussed in Section 3.3 The Math class. This is a very common pattern in the AP exam for FRQ #1.

🔗

To determine the minimum or maximum value in a sequence of numbers, use a variable to store the current minimum or maximum value. Use a loop to go through the sequence of numbers and update the minimum or maximum value by calling either Math.min or Math.max. For example, this loop chooses ten random numbers and finds the minimum value among them.

🔗

int min = Integer.MAX_VALUE;
for (int i = 0; i < 10; i++) {
    int num = (int) (Math.random() * 100);
    min = Math.min(min, num);
}
System.out.println("The minimum value is " + min);

If didn’t remember about the Math.min method, you could always implement the logic yourself with an if statement:

🔗

int min = Integer.MAX_VALUE;
for (int i = 0; i < 10; i++) {
    int num = (int) (Math.random() * 100);
    if (num < min) {
        min = num;
    }
}
System.out.println("The minimum value is " + min);

That code works essentially the same way with the very sight difference that the first version always assigns a value to min but sometimes it’s the current value and in the second version we only assign to min when we’ve actually found a smaller value. Either way is fine though avoiding if statements that we don’t need often leads to clearer code.

🔗

Activity 5.3.3.

Run to see the min method in action. Then, complete the max method to find the maximum of a set of random numbers. (Bonus question: after you’ve correctly implemented max, is it possible that the program will report a minimum value that is larger than the maximum value?)

🔗

public class MinMax {
    // min calculates and returns the minimum of n random numbers
    public static int min(int n) {
        int min = Integer.MAX_VALUE;
        for (int i = 0; i < n; i++) {
            int num = (int) (Math.random() * 100);
            System.out.println(num);
            min = Math.min(min, num);
        }
        return min;
    }

// max calculates and returns the maximum of n random numbers
    public static int max(int n) {
        int max = Integer.MIN_VALUE;
        // TODO: write a loop to find the maximum value
        // of n random numbers from 0 to 100

return max;
    }

public static void main(String[] args) {
        int n = 10;
        System.out.println("The minimum value is " + min(n));
        System.out.println("The maximum value is " + max(n));
    }
}
====
import static org.junit.Assert.*;

import org.junit.*;

import java.io.*;

public class RunestoneTests extends CodeTestHelper
{

@Test
     public void test1() throws IOException
     {
         String code = getCode();
         String target = "for (int * = #; * ? n; *~)";

int num = countOccurencesRegex(code, target);

boolean passed = num == 2;

getResults("2", "" + num, "Each method should have a for loop that uses n", passed);
        assertTrue(passed);
     }
     @Test
    public void containsCall()
    {
        boolean passed = checkCodeContains("num > max", "num > max");
        assertTrue(passed);
    }
}

🔗

Subsection 5.3.4 Exctacting digits with % and /

In the previous examples we were using numbers to control our loops and as the values to be summed, counted, averaged, minimized, and maximized. In this section we’ll use a while loop to take apart an int into its individual digits.

🔗

Before we got to the loop part of this problem there are two key facts to keep in mind about some arithmetic operators we first talked about in Section 2.3 Arithmetic expressions. First off, we need to realize that to get the rightmost digit of any int value is the remainder when divided by ten. For example 1234 % 10 ⟹ 4. Second, dividing an int value by ten effectively throws away the rightmost digit because of truncation. 1234 / 10 ⟹ 123. Also note, that if we divide an int value less than ten by ten, we get 0 after the last digit is thrown away: 9 / 10 ⟹ 0.

🔗

Putting those facts together, we can outline a while loop that we can use to extract the digits from a positive int from right (one’s place) to left:

🔗

while (n > 0) { // i.e. n still has at least one non-0 digit
    int d = n % 10;
    n /= 10;
    // Do something with d
}

We could use a loop like this to do anything we want with the digits of a number: reverse them, add them up, or check if the number contains a certain digit. The last one is your goal in the next exercise.

🔗

Activity 5.3.4. Check for specific digit.

Complete the checkDigit method below to determine if a positive number contains a given single-digit number as one of its digits.

🔗

public class CheckDigitTest {
      // checkDigit checks whether a number has a given digit in it
      public static boolean checkDigit(int number, int digit) {
         // Use a while loop to process the digits in number
         // and return true if the desired digit is found

// if loop finishes, return false
        return false; // Digit not found
    }

public static void main(String[] args) {
        System.out.println(checkDigit(12345, 3)); // should be true
        System.out.println(checkDigit(9876, 2));  // should be false
    }
}
====
import static org.junit.Assert.*;

import org.junit.*;

import java.io.*;

public class RunestoneTests extends CodeTestHelper
{
    public RunestoneTests()
    {
        super("CheckDigitTest");
    }

@Test
    public void test1() throws IOException
    {
        String target = "while";
        boolean passed = checkCodeContains("while loop", target);
        assertTrue(passed);
    }

@Test
    public void testMain() throws IOException
    {
        String expected = "true\nfalse";
        String output = getMethodOutput("main");
        boolean passed = getResults(expected, output, "Checking main output");
        assertTrue(passed);
    }

@Test
   public void testCall() throws IOException
   {
       Object[] args = {13579, 7};
       String output = getMethodOutput("checkDigit", args);
       String expect = "true";

boolean passed =
               getResults(
                       expect,
                       output,
                       "checkDigit(13579, 7)"
                       );
       assertTrue(passed);
   }

@Test
   public void testBool() throws IOException
   {
       String target = "number % 10";
       boolean passed = checkCodeContains(target, target);
       assertTrue(passed);
   }
}

🔗

Subsection 5.3.5 Summary

(AP 2.9.1) There are standard algorithms to:
1. Identify if an integer is or is not evenly divisible by another integer
  
  🔗
2. Identify the individual digits in an integer
  
  🔗
3. Determine the frequency with which a specific criterion is met
  
  🔗
4. Determine a minimum or maximum value
  
  🔗
5. Compute a sum or average
  
  🔗
🔗
🔗
The accumulator pattern is an algorithm that involves storing and updating an accumulator value within a loop, for example to compute a sum or average of a set of values.
🔗

🔗
A common algorithm pattern is an if statement within a loop to test each value against a criterion, such as finding the minimum or maximum value in a sequence of numbers.
🔗

🔗

🔗

You have attempted of activities on this page.

🔗

Prev Top Next