Unformatted text preview:

CS112 Lecture: Karel IterationLast revised 1/9/06Objectives:1. To introduce looping2. To introduce definite iteration3. To introduce indefinite iteration4. To introduce reasoning about loops (invariants and termination)Materials:1. Projectable Version of Problem 6.10 in the book2. BlueJ package containing Maze, SimpleEscaperRobot, Maze_while, SimpleEscaper_while, and various worlds (Maze, Maze0, Maze8, Maze20),plus my version of Problem6_10 and HurdlerRobot3. Demonstration of a robot that executes Euclid’s algorithmI. IntroductionA. Today, we learn the last of our simulated robots’ capabilities: iteration (also known as looping.)B. Alas - this is also the end of our time with Karel; but the concepts we have learned will show up again in JavaC. Several times in the programs we have written, it has been necessary to write an instruction or group of instructions over and over.Example: In our two maze examples, Karel was told he would need to move exactly 20 blocks to get out of the maze. The main program consisted of 20 repetitions of calling the advanceOneBlock() method.Clearly, this is an unpleasant and error-prone part of programming. D. Moreover, there are many situations in which we don’t know ahead of time the exact number of repetitions of a block of code that will be required.Example: Consider trying to write a method that picks up all the beepers on a corner, regardless of how many there might be.E. Fortunately, there is an alternative. The Java language (which is the basis of our robot language) has several instructions that specify that a given block of code is to be repeated some number of times:11. One form of instruction is used when we know ahead of time the exact number of repetitions that will be needed. This is called definite iteration.2. Another form of instruction is used when we don’t know ahead of time the exact number of repetitions that will be needed. This is called indefinite iteration. Both the robot language and Java use while for this.II. Definite IterationA. Recall both versions of the maze program, in which the escape() method of the robot involved twenty repetitions of calls to the advanceOneBlock() method:SHOW: SimpleEscaperRobot from last time againB. This can be revised as follows:SHOW: Revised version of SimpleEscaperRobotDEMODiscussion:1. A Java for loop header has 3 parts: initialization, test, and increment2. In this case, in the initialization, we create an integer variable called count, initialized to 0. Notice that we are using count to stand for the number of iterations that have been completed.3. In the test, we continue as long as count is less than 20. (We stop when we have completed 20 iterations.)4. The increment part adds 1 to count. count ++ is Java shorthand for this.5. The for loop is actually a very powerful construct. For now, we will limit ourselves to a “boilerplate” version like this example.C. As was true with if, the instruction controlled by for can be a compound instruction.Example: Recall our bar5 instruction that put down a row of 5 beepers.This could be revised as follows. (Note that we iterate a pair of instructions 4 times, then do one last putBeeper, since we move 4 times but put down 5 beepers - an example of what Bergin calls “the fence post problem”):21. Original:public void bar5(){putBeeper();move();putBeeper();move();putBeeper();move();putBeeper();move();putBeeper();}2. Revised:public void bar5(){for (int count = 0; count < 4; count ++){putBeeper();move();}putBeeper();}Note: In this case, the loop version is not much shorter, but it is immediately clear how many times each operation is done. The difference would be much more dramatic if wanted to produce a bar 10 or 20 (or more) beepers long!III. Indefinite IterationA. A more flexible form of looping is provided by the while instruction, which allows the number of iterations to be determined by the robot's environment, rather than up-front by the programmer.1. For example, let's consider our first maze problem, but with the further assumption that Karel is not told ahead of time how many blocks he must move. Instead, he is told that the exit square from the maze is 3marked by a beeper; when he gets to it, he's out. (Recall that, for the first maze problem, we didn't use beepers to get Karel through the maze - instead, his instructions were to move straight ahead whenever possible, and to turn left otherwise.) 2. This revised task can be accomplished as follows:SHOW: Maze_while.javaDEMO: - with Maze20.world and Maze8.world(NOTE: The world file name is specified as a string parameter to main when starting)B. The iteration provided by the while is called indefinite iteration, as opposed to the definite iteration provided by for. (Actually, the Java for can be used for indefinite iteration too - but that’s a story for another day!) Indefinite iteration allows a robot’s looping to be entirely controlled by its environment. Of course, this opens the possibility of an infinite loop!DEMO: Maze_while specifying Maze.world - which contains no beeperC. One important thing to note about a while loop is that, if the condition it tests is false to begin with, then it will be done zero times.DEMO: Maze_while specifying Maze0.worldD. Another example: Problem 6.10 in the book. 1. The problem: PROJECT2. Developing the program: a) Clearly, Karel is to execute some operation continually until he reaches the beeper that marks the end of the race. Thus, the body of the runRace() method must include a while loop:What should the condition in this loop be?ASKThe while condition is while Karel is NOT next to a beeper. We want to stop when we reach a beeper; so we keep going while we have not yet done so. What should comprise the body of the loop? 4ASKUsing stepwise refinement, we might decide to have Karel go forward one block each time through the loop. This gives:while (! nextToABeeper())advanceOneBlock();b) Now what should comprise the advanceOneBlock() method? ASKHe must do one of two things:(1) if there is no hurdle in front of him, he can simply move.(2) otherwise, he has to climb the hurdle.This gives us the body of the advanceOneBlock() method:if (frontIsClear())move();elseclimbHurdle();c) THE REMAINING CODE WILL NOT GO ON THE BOARD, SINCE I SOMETIMES ASSIGN THIS AS A PROJECT.d) Now, all that is left is to define the method climb-hurdle. In brief, what Karel must do is this:(1) Turn left (so he is facing


View Full Document

Gordon CS 112 - LECTURE

Download LECTURE
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view LECTURE and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view LECTURE 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?