Chapter 6
<< Chapter 5 | HomeworkTrailIndex | Chapter 7 >>
Iteration (Loops)
Demos
Review Exercises
- R6.2 What does the following code print?
for (int i = 0; i < 10; i++)
{
for (int j = 0; j < 10; j++)
System.out.print(i * j % 10);
System.out.println();
}
- R6.3 How often do the following loops execute? Assume that i is an integer variable that is not changed in the loop body.
for (i = 1; i <= 10; i++) . . . for (i = 0; i < 10; i++) . . . for (i = 10; i > 0; i––) . . . for (i = -10; i <= 10; i++) . . . for (i = 10; i > = 0; i++) . . . for (i = -10; i <= 10; i = i + 2) . . . for (i = -10; i <= 10; i = i + 3) . . .
- R6.4 Rewrite the following for loop into a while loop.
int s = 0; for (int i = 1; i <= 10; i++) s = s + i;
- R6.11 What is an “off-by-one error”? Give an example from your own programming experience.
- R6.20 Which of the following varies the control variable from 100 to 1 in increments of -1?
- R6.22 What is the value of x after the following nested loop?
int x = 0; for(int i = 0; i <= 5; i++) for(int j = 0; j < i; j++) x = x + j;
Programming Exercises
Do one for 8 points, 2 for 9 points or all 3 for 10 points
P6.5 Mean and Standard deviation
The formula for the mean (or arithmetic mean or average) is
{⚠ $ \overline{x}=\frac{\sum x_i}{n}$} where {⚠ $\sum x_i = x_1 + x_2 + \dots + x_n $} for {⚠ $n$} scores
The formula for standard deviation is
{⚠ $s=\sqrt{\frac{\sum x_i^2 - \frac{1}{n}\left( \sum x_i \right)^2}{n-1}}$}
You can compute this by keeping track of the count, the sum, and the sum of squares.
Here is a sample program run:
Enter Value, Q to quit: 5 Enter Value, Q to quit: 6 Enter Value, Q to quit: 8 Enter Value, Q to quit: 9 Enter Value, Q to quit: Q There is a total of 4 values The average is 7.0 The standard deviation is 1.8257418583505538
Here is some starter code for a dynamic tester:
import java.util.Scanner;
public class DynamicDataSetTester
{
public static void main(String[] args)
{
DataSet data = new DataSet();
Scanner kb=new Scanner(System.in);
String input="";
while( notDone(input) )
{
System.out.print("Enter an integer (Q to quit): ");
input = kb.nextLine();
if ( isAnInt(input) ){
data.add(Integer.parseInt(input));
System.out.println("score "+data.getN()+" added");
}
}
System.out.println("DataSet data has "+data.getN()+" scores");
}
public static boolean notDone(String s){
boolean result=true;
if (s.length()>0 && s.substring(0,1).equalsIgnoreCase("Q") )
result=false;
return result;
}
public static boolean isAnInt(String s)
{
boolean result = true;
try {
Integer.parseInt(s);
} catch (NumberFormatException e){
result = false;
}
return result;
}
}
Here is a static tester program to use to test your DataSet class:
public class DataSetTester
{
public static void main(String[ ] args)
{
DataSet a = new DataSet();
a.add(5);
a.add(6);
a.add(8);
a.add(9);
System.out.println("count: " + a.getCount());
System.out.println("Expected: 4");
System.out.println("average: " + a.getAverage());
System.out.println("Expected: 7");
System.out.println(
"standard deviation: " + a.getStandardDeviation());
System.out.println("Expected: 1.83");
}
}
- P6.12 Monte Carlo Simulation for computing {
⚠ $\pi$}
Program the following simulation: Darts are thrown at random points onto the square with corners (1,1) and (−1,−1). If the dart lands inside the unit circle (that is, the circle with center (0,0) and radius 1), it is a hit. Otherwise it is a miss. Run this simulation and use it to determine an approximate value for {⚠ $\pi$}
You should supply a Dart class with the following interface:
public class Dart
{
public Dart() { . . . }
/**
Throws a dart into the square [-1,1] x [1,1] and records
whether it hits the unit circle.
*/
public void throwIntoSquare() { . . . }
/**
Gets the number of hits inside the unit circle.
@return hits number of hits
*/
public int getHits() { . . . }
/**
Gets the number of tries.
@return the number of times the dart was thrown
*/
public int getTries() { . . . }
// private implementation
. . .
}
Here is a tester for your class:
public class DartTester
{
public static void main(String[] args)
{
int n=100000;
Dart dart=new Dart();
for (int i=0; i<n; i++)
dart.throwIntoSquare();
System.out.println("Hits: "+dart.getHits());
System.out.println("Tries: "+dart.getTries());
double percent=(double)(dart.getHits())/dart.getTries();
System.out.println("percent = "+percent );
System.out.println("4*percent = "+4.0*percent+" (should be close to Pi)");
}
}
This works since {⚠ $ \frac{\pi}{4} =\frac{\pi r^2}{4r^2}= \frac{\pi r^2}{(2r)^2} $} and this is the ratio of the Area of a circle divided by the Area of the square. The ratio of the darts that land in the circle of radius 1 divided by the darts in the area of the square should be the same ratio, if we throw enough random darts. Why 4 times the percent?
{⚠ $ \pi=\frac{4\pi}{4}=4\left(\frac{\pi}{4}\right)=4\left(\frac{\pi r^2}{(2r)^2} \right)=$}4*percent
- P6.15 Write a graphical application that displays a checkerboard with 64 squares, alternating white and black.
CheckerBoard.java
import java.awt.Graphics2D;
import java.awt.Rectangle;
/**
This class displays a checkerboard with squares,
alternating between white and black.
*/
public class CheckerBoard
{
/**
Creates a CheckerBoard object with a given number of squares.
@param aNumSquares the number of squares in each row
@param aSize the size of each square
*/
public CheckerBoard(int aNumSquares, int aSize)
{
numSquares = aNumSquares;
size = aSize;
}
/**
Method used to draw the checkerboard.
@param g2 the graphics content
*/
public void draw(Graphics2D g2)
{
// your code here
}
private int numSquares;
private int size;
}
CheckerBoardComponent.java
import javax.swing.JComponent;
import java.awt.Graphics;
import java.awt.Graphics2D;
public class CheckerBoardComponent extends JComponent
{
public void paintComponent(Graphics g)
{
Graphics2D g2 = (Graphics2D) g;
final int NSQUARES = 8;
int size = Math.min(getWidth(), getHeight()) / NSQUARES;
CheckerBoard cb = new CheckerBoard(NSQUARES, size);
cb.draw(g2);
}
}
CheckerBoardViewer.java
import javax.swing.JFrame;
/**
This program displays a checkerboard.
*/
public class CheckerBoardViewer
{
public static void main(String[] args)
{
JFrame frame = new JFrame();
final int FRAME_WIDTH = 330;
final int FRAME_HEIGHT = 360;
frame.setSize(FRAME_WIDTH, FRAME_HEIGHT);
frame.setTitle("CheckerBoardViewer");
frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
CheckerBoardComponent component = new CheckerBoardComponent();
frame.add(component);
frame.setVisible(true);
}
}
11 points: Nim
The game of Nim. This is a well-known game with a number of variants. We will consider the following variant, which has an interesting winning strategy. Two players alternately take sticks from a pile. In each move, a player chooses how many sticks to take. The player must take at least one but at most half of the sticks. Then the other player takes a turn. The player who takes the last stick loses.
Write a program in which the computer plays against a human opponent. Generate a random integer between 10 and 100 to denote the initial size of the pile. Generate a random integer between 0 and 1 to decide whether the computer or the human takes the first turn. Generate a random integer between 0 and 1 to decide whether the computer plays smart or dumb. In dumb mode, the computer simply takes a random legal value (between 1 and n/2) from the pile whenever it has a turn. In smart mode the computer takes off enough marbles to make the size of the pile a power of two minus 1—that is, 3, 7, 15, 31, or 63. That is always a legal move, except if the size of the pile is currently one less than a power of 2. In that case, the computer makes a random legal move.
Note that the computer cannot be beaten in smart mode when it has the first move, unless the pile size happens to be 15, 31, or 63. Of course, a human player who has the first turn and knows the winning strategy can win against the computer.
When you implement this program, be sure to use classes Pile, Player, and Game. A player can be either dumb, smart, or human. (Human Player objects prompt for input.)
GameRunner.java
import java.util.Scanner;
import java.util.Random;
/**
* GameRunner will create a Nim Game by randomly
* choosing who starts (human or computer), and
* randomly deciding whether the computer is in
* smart or dumb mode.
*
* @author Chris Thiel, OFMCap
* @version 31 October 2009
*/
public class GameRunner
{
public static boolean tossCoin()
{
Random coin=new Random();
int toss=coin.nextInt(2);
return toss==1;
}
public static void main(String[] args)
{
int compType=Player.DUMB_COMPUTER;
if (tossCoin()) compType=Player.SMART_COMPUTER;
boolean computersTurn=tossCoin();
Player comp = new Player(compType);
Player user = new Player();
Game theGame= new Game(computersTurn, comp, user);
System.out.println(theGame.getGameStatus());
if (compType==Player.SMART_COMPUTER) {
System.out.println("Computer is in smart mode");
}else{
System.out.println("Computer is in random mode");
}
if(computersTurn)
{
System.out.println("Computer goes first");
}else{
System.out.println("You go first");
}
while (theGame.isInProgress() )
{
System.out.println(theGame.getNextMove() );
}
System.out.println(theGame.getWinner() );
}
}
Player.java
import java.util.Scanner;
/**
* Player is a Nim game player.
* There are 3 types:
* 1. Human (get move from the keyboard)
* 2. Dumb Computer
* 3. Smart Computer
*
* @author Chris Thiel, OFMCap
* @version 31 Oct 2009
*/
public class Player
{
/**
* Constants
*/
public static final int HUMAN=0;
public static final int DUMB_COMPUTER=1;
public static final int SMART_COMPUTER=2;
/**
* Fields
*/
int type;
Scanner keyboard;
/**
* Constructors
*/
public Player()
{
type = HUMAN;
keyboard= new Scanner (System.in);
}
public Player(int theType)
{
type=theType;
if (type==HUMAN)
keyboard= new Scanner (System.in);
}
/**
* Methods
*/
/**
* getMove returns the Player's choice
*
* @param n the number of sticks left
* @return how many sticks to take
*/
public int getMove(int n)
{
int max = n/2;
if (max==0) max=1;
if (type==HUMAN)
{
System.out.println("Take at least 1, but no more than "+max+" sticks");
int result = Integer.parseInt(keyboard.nextLine());
while (result<1 || result>max)
{
System.out.println(result+"??? No, that is not legal. Try Again\nTake at least 1, but no more than "+max+" sticks");
result = Integer.parseInt(keyboard.nextLine());
}
return result;
}
System.out.println("The computer must take at least 1, but no more than "+max+" sticks");
if (type ==SMART_COMPUTER)
{
int result=1;
//your code here
return result;
}
return 1; //your code here-make it random choice of legal moves
}
public String toString() {
if (type==HUMAN)
return "Human";
return "Computer";
}
}
Pile.java
import java.util.Random;
/**
* Pile represents the pile of sticks for a Nim Game.
*
* @author Chris Thiel, OFMCap
* @version 31 Oct 2009
*/
public class Pile
{
/**
* Fields
*/
private int sticks;
/**
* Constructors
*/
public Pile(int low, int high)
{
//your code here--initialize the number of sticks in the pile
// make sure the random choice is between low and high
}
public int total()
{
//your code here
}
public boolean hasSticks()
{
//your code here
}
public void remove(int n)
{
//your code here
}
public String toString()
{
return "There are "+sticks+" sticks in the pile";
}
}
Game.java
import java.util.Scanner;
import java.util.Random;
/**
* Game represents a particular Nim Game
* between two Players with a Pile of sticks.
*
* It keeps track of who's turn it is,
* whether the game is still in progress or
* if it has ended, who the Winner was.
*
* @author Chris Thiel, OFMCap
* @version 31 Oct 2009
*/
public class Game
{
/**
* Fields
*/
boolean computersTurn;
Player user;
Player comp;
Pile thePile;
Player winner;
/**
* Constructors
*/
public Game(boolean isComputersTurn, Player theComp, Player theUser)
{
//your code here
}
/**
* Methods
*/
public String getGameStatus()
{
String result = thePile.toString();
result+="\n";
if(computersTurn) {
result+="Computer's turn";
} else{
result+="Your Turn";
}
return result;
}
public boolean gameOver()
{
//your code here
}
public boolean isInProgress()
{
//your code here
}
/**
* getNextMove will say "Game Over" unless
* there are still sticks in thePile. If there
* Sticks in thePile, it will determine who's turn it is
* and get the next move from the correct player.
* It removes the sticks from the Pile, and
* keeps track who has the next Turn.
*
* @return a String reporting which Player took sticks and how many sticks taken, or if the game is over, who won.
*/
public String getNextMove()
{
//your code here
}
public Player getWinner() {return winner;}
public boolean isComputersTurn()
{
return computersTurn;
}
}
Sample Run of the Nim Game
There are 68 sticks in the pile. You go first. Take at least 1, but no more than 34 sticks 34 You take 34 There are 34 sticks in the pile The computer must take at least 1, but no more than 17 sticks Computer takes 7 There are 27 sticks in the pile Take at least 1, but no more than 13 sticks 13 You take 13 There are 14 sticks in the pile The computer must take at least 1, but no more than 7 sticks Computer takes 4 There are 10 sticks in the pile Take at least 1, but no more than 5 sticks 3 You take 3 There are 7 sticks in the pile The computer must take at least 1, but no more than 3 sticks Computer takes 3 There are 4 sticks in the pile Take at least 1, but no more than 2 sticks 1 You take 1 There are 3 sticks in the pile The computer must take at least 1, but no more than 1 sticks Computer takes 1 There are 2 sticks in the pile Take at least 1, but no more than 1 sticks 1 You take 1 There are 1 sticks in the pile The computer must take at least 1, but no more than 1 sticks The computer had to take the last one -- YOU WIN!