Lab 4
Repetition

Due: Tue 2/20 at the start of lab

Introduction

This week's lab focuses on writing programs that involve repetition.

Collaboration

Labs and projects are for practice and learning. While it can be very productive to work on problems with your peers, it is also easy to underestimate how much you yourself understand and can do in such situations — so often something looks easy when someone else does it! With this in mind, you should always make the first attempt on a problem or programming task yourself using only the resources provided for the course (textbook, slides and examples posted on the schedule page, other resources linked on the course webpages). After that point, you are encouraged to come to office hours and/or go to Teaching Fellows. You may not collaboratively write solutions or code, and you may not copy solutions or code written by others, even if you contributed ideas.

You can discuss specific exercises with other students in general terms — such as how you might get started on that problem, or how or when to use various programming constructs, or strategies for debugging — but how to use a particular programming construct to solve a specific problem or debugging a particular program should only be discussed in office hours or with the Teaching Fellows.

Setup

Program Development With Loops

When you identify that a task in your program involves repetition, following the steps below can help you construct a loop:

• identify what repeats (this will go into the loop body)
• identify the form or pattern (to provide a template for the loop syntax)
• adjust timing of loop condition test as needed
• adjust variable declarations as needed

Adjusting the timing of the loop condition: In both for and while loops, the condition is checked before the loop body is run. Sometimes, however, this isn't what you want. Consider when the loop condition check should happen in your situation:

• before any part of the repeated task — this fits the normal semantics of the loop (put the condition in the "condition" part of the for or while loop structure)

• in the middle of the repeated task — this fits the fencepost pattern (use one of the two options for that)

• after the task — put the test in the "condition" part of the for or while loop structure and initialize the variable(s) involved in the condition so that the condition is true the first time it is checked (prime the loop)

Note the difference between the first and last situations — if the condition is checked before the repeated task, it is possible that the loop body never executes (the condition could be false on the first check), while if the condition is checked after the repeated task, the repeated task always happens at least once.

Adjusting variable declarations as needed: Variables should always be declared as locally as possible. Depending on the context of your loop, you may need to adjust where you put declarations for loop variables.

• If the variable is only needed for one repetition of a loop (or in one case of an if), declare the variable inside the curly brackets defining the loop body or if case. Note that for loops, this isn't saying that only one repetition needs the variable and other repetitions don't, but rather that the variable's value doesn't need to carry over from one repetition to the next - it's not involved in the loop condition and is just used for temporary storage as the loop executes.

• For for loops, if the variable is only needed in the loop but its value needs to be remembered from one repetition to the next or the variable is involved in the loop condition, declare the variable in the initialization part of the loop if you can.

• Otherwise declare the variable before the first time it is used and in the correct scope so that it is visible everywhere you need to use it.

Loop Forms and Patterns

Loop Forms

When you identify that a task involves repetition, identify "what repeats?" (which gives you the loop body) and look for a pattern to help you construct the loop. Four basic forms of loops were discussed in class:

• repeat until condition (condition is a stopping condition)

        for ( ; !condition ; ) {
          body
        }
        while ( !condition ) {
  	body
        }
      

• repeat as long as condition (condition is a keep-going condition)

        for ( ; condition ; ) {
          body
        }
        while ( condition ) {
          body
        }
      

• repeat n times

        for ( int count = 0 ; count < n ; count++ ) {
          body
        }
      

  Use a more descriptive name than count or i for the counter variable when possible. (What's being counted? numthing can be a good name, where thing is what is being counted.)

• repeat from a to b by interval c

        for ( int i = a ; i <= b ; i = i+c ) {
          body
        }
      

  Use a more descriptive name than i for the loop variable when possible.

Loop Patterns

The four loop forms provide a starting point for structuring a loop, but there are some common situations involving loops. Recognizing one of these situations provides a more complete template for building a loop than just identifying the form. Examples of some of these patterns were seen in class.

  for ( int count = 0 ; count < n ; count++ ) {
    // task
  }

Error-checking user input. When the user is asked to enter a value and legal values are a subset of the values supported by a particular type. For example, the user is asked to enter an integer between 1 and 10 - there are many integers not in that range.

This is also an example application of the fencepost pattern.

  // prompt user
  // read input
  // repeat until the input value is legal
  //   print error message
  //   prompt user
  //   read input

Another version of the pattern:

  // repeat 
  //   prompt user
  //   read input
  //   if the input value is legal
  //     break
  //   print error message

Fencepost. When part of the repeated action needs to be done before you can determine whether or not the loop should continue. It can take two forms:

  // repeat 
  //   do part of task
  //   if the stopping condition is true
  //     break
  //   do rest of task

  // do part of task
  // repeat until the stopping condition is true
  //   do rest of task
  //   do part of task

Accumulator pattern. When the desired result is built up bit-by-bit over the course of the loop iterations. This involves a variable holding the value being accumulated - the variable is declared before the loop (so it can be used after the loop is complete and it holds the desired answer) and its value is updated in the body of the loop.

  // declare and initialize accumulator variable
  // repeat until condition   (or as long as condition or n times or ...)
  //   do task, updating the accumulator

For example, sum the values entered by the user:

  int sum = 0;   // initial sum is 0
  for ( int i = 0 ; i < 10 ; i++ ) {   // user enters 10 numbers
    System.out.print("enter a number: ");
    int number = scanner.nextInt();
    sum = sum+number;   // add current number to sum
  }
  System.out.println("sum: "+sum);

A special case of this pattern is counting the number of repetitions (or a subset of the repetitions). Note that this is different from a counting loop because in a counting loop the number of iterations is known and the counter keeps track of the progress towards completion of the loop, while in this pattern the loop condition is entirely separate from the desired counting. For example, count the number of divisors in number:

  int numdivisors = 0;    // the number-of-divisors counter
  for ( int div = 1 ; div <= number ; div++ ) {  // repeat from 1 to number
    if ( number % div == 0 ) {   // check whether number is evenly divisible by div
      numdivisors++;
    }
  }
  System.out.println("number of divisors: "+numdivisors);

Best-so-far pattern. This is typical of minimum- and maximum-finding tasks but also comes up in searching tasks - the loop goes through a series of elements one at a time; a variable is used to keep track of the best answer so far and updated accordingly when a new better element is seen.

  // declare and initialize best-so-far variable to worst possible result
  // repeat until condition   (or as long as condition or n times or ...)
  //   if current value is better than best-so-far
  //     best-so-far = current

For example, find the smallest value entered by the user:

  int min = 10000000;  // pick a sufficiently large number
  for ( int i = 0 ; i < 10 ; i++ ) {   // user enters 10 numbers
    System.out.print("enter a number (max 10,000,000): ");
    int number = scanner.nextInt();
    if ( number < min ) {  // if current number is smaller...
      min = number;
    }
  }
  System.out.println("the smallest number you entered is "+min);

Exercises

For all exercises:

• Utilize incremental development, keeping in mind two key strategies: use placeholder variables so you can implement (simpler) parts of the task before tackling the computation of those values, and tackle more complex tasks by first solving a slightly modified (and simpler) version of the problem first.

• Document your loop development process by identifying the form and pattern (where applicable) of the loops in comments in your code.

• Employ good programming style, including choosing descriptive variable names and autoformatting your code.

• Include your name and a description of the program in each program.

Exercise #1

Once upon a time, schoolchildren were punished for bad behavior by having to write a particular line (such as "I will not do anything bad ever again") over and over. This, of course, is quite tedious, so you've decided to write a program instead.

Exercise #2

For example: (bold underline is used to distinguish the user's input from your program's output; you do not need to have your program display things with bold underline)

  enter low: 10
  enter high: 30
  enter skip: 3

  10, 13, 16, 19, 22, 25, 28
  30, 27, 24, 21, 18, 15, 12

The range is inclusive, so both low and high should be printed if appropriate.

The program's output should be exactly as shown in terms of the text of the prompts, the positioning of where the user's input appears, the blank line between the input prompts and the lists, and the formatting of the lists themselves. In particular, note that there should not be a comma or space after the last number on each line.

Exercise #3

Assuming that you can keep folding a piece of paper in half no matter how thick it gets, how many folds do you need in order to have the folded paper reach from the Earth to the moon? To the sun? Across the solar system?

A standard piece of paper is 0.05-0.1mm thick. From the Earth to the moon is approximately 384,400 km and from the Earth to the sun is approximately 150 million km. Across the solar system is approximately 14.5 billion km.

For convenience, your program might ask the user to enter the paper thickness in a small unit (such as mm) and the desired distance in a large unit (such as km). Make sure you do the appropriate conversions in your calculations so that you are using the same units when you compare paper thickness and desired distance. (1km = 1000m, 1m = 1000mm)

Exercise #4

A dice game allows a player to choose how many dice to roll on their turn. The score for the turn is the highest number rolled, unless a 1 is rolled, in which case the score is 0.

Note that you do not need arrays for this — identify an appropriate loop pattern that lets you deal with each roll and its effect on the player's score as the roll happens instead of first rolling all the dice and then figuring out the score.

Exercise #5

One round of the casino game of craps is played as follows:

• The player rolls two dice. The sum of the numbers rolled is called the "initial sum".
• If the initial sum is 7 or 11, the player wins immediately.
• If the initial sum is 2, 3, or 12, the player loses immediately.
• If the initial sum is anything else (4, 5, 6, 8, 9, 10), the player keeps rolling the dice until the sum of the numbers rolled is equal to the initial sum (she wins) or 7 (she loses).

Casino games usually favor the house - that is, over time, you'll lose money. Your task is to figure out the odds of winning at craps.

Note that your program will not have any interaction with the user - even though the game rules say things like "the player rolls two dice", the user isn't involved (the program rolls the dice for the player).

Also note that the final program's output should consist of only the percentage of rounds won - while it is very useful to print out other things (such as "win" or "lose" for each round) as you develop and test your program, be sure to remove any extra output before you hand in your program.

Think about how to approach this problem before revealing the hint below. (Highlight with the mouse to see the text.)

Handin and Grading

Don't forget to hand in your work when you are done!

As in lab 2 (and all labs), grading will be based on both functionality and style. Style means following the good programming style conventions outlined in lab 2, as well as producing reasonably compact and elegant solutions. "Reasonably compact and elegant" means that your program is not significantly longer or more complex than it needs to be. In particular, you must use loops when loops are appropriate — achieving repetition by copying-and-pasting a bunch of code will not earn credit.