Programming Activity 13-2 Guidance ================================== Overview -
ID: 3876604 • Letter: P
Question
Programming Activity 13-2 Guidance
==================================
Overview
--------
This activity strongly demonstrates the power of recursion.
To do so much, with only a few lines of recursive controlling code.
You might want to spend some time thinking about how difficult it would
be to code the Towers of Hanoi problem without using recursion.
Recursion
---------
This program uses recursion.
Only part 2 has a call to moveDisk().
To be recursive, a function MUST call itself.
That is why parts 1 and 3 must call the recursiveTOfH() function itself,
but with simplifying parameters as spelled out in the framework comments.
Calling with simplified parameters
----------------------------------
Calling with simplified parameters is a key part of recursion.
For recursion to work, the chain of self calls must eventually unwind.
This can only happen if each self call is in some way simpler than the
context from which it is being called.
In this week's videos, the concept of simplifying calls is illustrated.
For this assignment, the framework comments spell out what this means.
Part 1
------
This part requires only 1 line of code:
a recursive call to the same function (with simplifying parameters).
Part 2
------
Here is the code to "print a message to the screen":
String moveMessage =
"Move disk " + numDisks +
" from tower " + fromTower +
" to tower " + toTower;
System.out.println(moveMessage);
This code simply displays a message to the system console.
Part 2 requires only 1 other line of code.
Here are the framework code comments for part 2:
// 2. Move one disk from fromTower to toTower
// Print a message to the screen, then
// call moveDisk in order to animate.
The first comment line "2. Move one disk from fromTower to toTower"
summarizes the intended result of this part.
Use the moveDisk() function to do this.
Use numDisks as the disk number to move.
The last comment line "call moveDisk in order to animate"
tells us that there is no need to call an animate() function because
the animation is taken care of for us inside the moveDisk() function.
Part 3
------
This part requires only 1 line of code:
a recursive call to the same function (with simplifying parameters).
1. For the code under comment 2, use numDisks as the disk number to move.
_______________________________________________________________________________
/* HanoiClient
* LeBlanc, Stephen
*/
import javax.swing.JOptionPane;
import javax.swing.JFrame;
import java.awt.Graphics;
public class HanoiClient extends JFrame
{
private TowersOfHanoi tOfH;
boolean started = false;
public HanoiClient()
{
tOfH = new TowersOfHanoi(4);
setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
setSize(500, 300);
setVisible(true);
}
public TowersOfHanoi getTOfH()
{
return tOfH;
}
public void setStarted(boolean b)
{
started = b;
}
public void recursiveTOfH(int numDisks, int fromTower, int toTower, int useTower)
{
// ***** Student writes the body of this method *****
//
// Using recursion, transfer numDisks disks from the tower
// fromTower to the tower toTower using the tower
// useTower
// The disks are numbered as follows: if we started with n disks,
// the disk at the top is disk # 1
// and the disk at the bottom is disk # n
// We call the moveDisk method inside the body of this method
// The moveDisk method moves one disk and takes 3 arguments:
// an int, representing the disk number to be moved
// an int, representing the tower to move the disk from
// an int, representing the tower to move the disk to
// So if these three variables are:
// diskNumber, fromTower, and toTower
// then the call to moveDisks will be:
// moveDisk(diskNumber, fromTower, toTower);
if (numDisks > 0)
{
// Student code starts here:
// 1. Move (numDisks - 1) disks from fromTower
// to useTower using toTower
// 2. Move one disk from fromTower to toTower
// Print a message to the screen, then
// call moveDisk in order to animate.
// 3. Move (numDisks - 1) disks from useTower to toTower
// using fromTower
}
// Base case: 0 disks to move ==> do nothing
//
// Student code ends here.
}
public void moveDisk(int diskNumber, int fromTower, int toTower)
{
repaint();
try
{
Thread.sleep(1000); // wait for the animation to finish
}
catch (Exception e)
{
}
// update parameters
tOfH.updateTowers(diskNumber, fromTower, toTower);
}
public void paint(Graphics g)
{
if (started)
{
super.paint(g);
tOfH.draw(g);
}
}
public int getNumberOfDisks()
{
boolean goodInput = false;
int numberDisks = 4; // will be reassigned - default is 4
while (!goodInput)
{
try
{
String answer = JOptionPane.showInputDialog(null, "Enter number of disks between 1 and 9");
if (answer != null)
{
numberDisks = Integer.parseInt(answer);
goodInput = true;
}
else
{
System.exit(0);
}
}
catch (Exception e)
{
}
}
return numberDisks;
}
public static void main(String[] args)
{
HanoiClient app = new HanoiClient();
// ask user for number of disks
while (true)
{
int numDisks = app.getNumberOfDisks();
(app.getTOfH()).setDisks(numDisks);
app.setStarted(true);
// start
app.recursiveTOfH((app.getTOfH()).getDisks(), 0, 2, 1);
// finish last step in animation
app.repaint();
System.out.println("Done ");
// done
try
{
Thread.sleep(5000); // wait for the animation to finish
}
catch (Exception e)
{
}
JOptionPane.showMessageDialog(null, "Done");
}
}
}
Explanation / Answer
//Please see the below java code
1) TowersOfHanoi.java
import javax.swing.JFrame;
import java.awt.Graphics;
import java.awt.Color;
import java.util.ArrayList;
public class TowersOfHanoi
{
// constants for Towers' parameters
private static final int TOWER_LENGTH = 200;
// x coordinates of towers
private static final int XT1 = 100;
private static final int XT2 = 250;
private static final int XT3 = 400;
// y coordinate of the top of the towers
private static final int YT = 250;
// height of the disks
private static final int HD = 15;
// coefficient of expansion for the width of the disks
private static final int WDC = 15;
// int array representing the disks on the tower
int [][] towers;
// int array representing the top disk in each tower
int [] top;
// Number of disks
private int disks;
public TowersOfHanoi( int d )
{
setDisks( d );
}
public void setTowers( int [][] t )
{
towers = t;
}
public int [][] getTowers( )
{
return towers;
}
public void setTop( int [] t )
{
top = t;
}
public int [] getTop( )
{
return top;
}
public void setDisks( int d )
{
if ( d >= 1 && d <= 9 )
disks = d;
else
disks = 4;
towers = new int[3][disks];
// put all disks inside tower 1 to start
for ( int i = 0; i < disks; i++ )
towers[0][i] = disks - i;
top = new int[3];
top[0] = disks - 1; // index of top disk on tower 0
top[1] = -1; // index of top disk on tower 1
top[2] = -1; // index of top disk on tower 2
}
public int getDisks( )
{
return disks;
}
public void printMe( )
{
System.out.println( "Tower 0" );
for ( int i = 0 ; i <= top[0]; i++ )
System.out.print( towers[0][i] + " " );
System.out.println( " top = " + top[0] );
System.out.println( "Tower 1" );
for ( int i = 0 ; i <= top[1]; i++ )
System.out.print( towers[1][i] + " " );
System.out.println( " top = " + top[1] );
System.out.println( "Tower 2" );
for ( int i = 0 ; i <= top[2]; i++ )
System.out.print( towers[2][i] + " " );
System.out.println( " top = " + top[2] );
System.out.println( );
}
public void updateTowers( int diskNumber, int fromTower, int toTower )
{
if ( enforceRules( diskNumber, fromTower, toTower ) )
{
// update toTower
towers[toTower][top[toTower] + 1] = diskNumber;
top[toTower] = top[toTower] + 1;
// update fromTower
towers[fromTower][top[fromTower]] = 0;
top[fromTower] = top[fromTower] - 1;
}
else
{
System.out.println( "Illegal Move: action cancelled" );
}
}
public boolean enforceRules( int diskNumber, int fromTower, int toTower )
{
boolean rule = true;
if ( fromTower < 0 || fromTower > 2 )
rule = false;
else if ( toTower < 0 || toTower > 2 )
rule = false;
else if ( fromTower == toTower )
{
rule = false;
System.out.println( "Trying to move a disk within one tower" );
}
else if ( top[fromTower] == -1 ) // fromTower empty
{
rule = false;
System.out.println( "Trying to move a disk from tower " + fromTower + " which is empty" );
}
else if ( top[toTower] == ( disks - 1 ) ) // toTower full
{
rule = false;
System.out.println( "Trying to move a disk to tower " + toTower + " which is full" );
}
else if ( top[toTower] != - 1 && diskNumber != towers[fromTower][top[fromTower]] ) // not correct disk
{
rule = false;
System.out.println( "Trying to move a disk which is not at the top of its tower" );
}
else if ( top[toTower] != -1 && towers[toTower][top[toTower]] != 0 && diskNumber > towers[toTower][top[toTower]] ) // big disk on top of small disk
{
rule = false;
System.out.println( "Trying to place a disk on top of a smaller disk" );
}
else if ( towers[fromTower][top[fromTower]] != diskNumber )
{
rule = false;
System.out.println( "Trying to move a disk not on top of a tower" );
}
return rule;
}
public void draw( Graphics g )
{
g.setColor( Color.BLUE );
// display tower 1
g.drawLine( XT1, YT + HD, XT1, YT - TOWER_LENGTH );
// display tower 2
g.drawLine( XT2, YT + HD, XT2, YT - TOWER_LENGTH );
// display tower 3
g.drawLine( XT3, YT + HD, XT3, YT - TOWER_LENGTH );
// display tower numbers
g.drawString( "0", XT1 - 3, YT + 35 );
g.drawString( "1", XT2 - 3, YT + 35 );
g.drawString( "2", XT3 - 3, YT + 35 );
// display disks on tower 1
for ( int i = 0; i <= top[0]; i++ )
{
g.setColor( Color.RED );
g.fillRoundRect( XT1 - ( WDC * towers[0][i] )/2 ,YT - i * ( HD + 2 ), WDC * towers[0][i], HD, 10, 10 );
g.setColor( Color.BLACK );
g.drawString( "" + towers[0][i], XT1 - 3, YT - i * ( HD + 2 ) + 3 * HD / 4 );
}
// display disks on tower 2
for ( int i = 0; i <= top[1]; i++ )
{
g.setColor( Color.RED );
g.fillRoundRect( XT2 - ( WDC * towers[1][i] )/2 ,YT - i * ( HD + 2 ), WDC * towers[1][i], HD, 10, 10 );
g.setColor( Color.BLACK );
g.drawString( "" + towers[1][i], XT2 - 3, YT - i * ( HD + 2 ) + 3 * HD / 4 );
}
// display disks on tower 3
for ( int i = 0; i <= top[2]; i++ )
{
g.setColor( Color.RED );
g.fillRoundRect( XT3 - ( WDC * towers[2][i] )/2 ,YT - i * ( HD + 2 ), WDC * towers[2][i], HD, 10, 10 );
g.setColor( Color.BLACK );
g.drawString( "" + towers[2][i], XT3 - 3, YT - i * ( HD + 2 ) + 3 * HD / 4 );
}
}
}
2) HanoiClient .java
import javax.swing.JOptionPane;
import javax.swing.JFrame;
import java.awt.Graphics;
public class HanoiClient extends JFrame
{
private TowersOfHanoi tOfH;
boolean started = false;
public HanoiClient( )
{
tOfH = new TowersOfHanoi( 4 );
setDefaultCloseOperation( JFrame.EXIT_ON_CLOSE );
setSize( 500, 300 );
setVisible( true );
}
public TowersOfHanoi getTOfH( )
{
return tOfH;
}
public void setStarted( boolean b )
{
started = b;
}
public void recursiveTOfH( int numDisks, int fromTower, int toTower, int useTower )
{
// ***** Student writes the body of this method *****
//
// Using recursion, transfer numDisks disks from the tower
// fromTower to the tower toTower using the tower
// useTower
// The disks are numbered as follows: if we started with n disks,
// the disk at the top is disk # 1
// and the disk at the bottom is disk # n
// We call the moveDisk method inside the body of this method
// The moveDisk method moves one disk and takes 3 arguments:
// an int, representing the disk number to be moved
// an int, representing the tower to move the disk from
// an int, representing the tower to move the disk to
// So if these three variables are:
// diskNumber, fromTower, and toTower
// then the call to moveDisks will be:
// moveDisk( diskNumber, fromTower, toTower );
if ( numDisks > 0 )
{
// Student code starts here
// 1. Move ( numDisks - 1 ) disks from fromTower
// to useTower using toTower
// 2. Move one disk from fromTower to toTower
// Print a message to the screen, then
// call moveDisk in order to animate.
// 3. Move ( numDisks - 1 ) disks from useTower to toTower
// using fromTower
}
// Base case: 0 disks to move ==> do nothing
//
// end of student code
//
}
public void moveDisk( int diskNumber, int fromTower, int toTower )
{
repaint( );
try
{
Thread.sleep( 1000 ); // wait for the animation to finish
}
catch ( Exception e )
{
}
// update parameters
tOfH.updateTowers( diskNumber, fromTower, toTower );
}
public void paint( Graphics g )
{
if ( started )
{
super.paint( g );
tOfH.draw( g );
}
}
public int getNumberOfDisks( )
{
boolean goodInput = false;
int numberDisks = 4; // will be reassigned - default is 4
while ( !goodInput )
{
try
{
String answer = JOptionPane.showInputDialog( null, "Enter number of disks between 1 and 9" );
if ( answer != null )
{
numberDisks = Integer.parseInt( answer );
goodInput = true;
}
else
{
System.exit( 0 );
}
}
catch ( Exception e )
{}
}
return numberDisks;
}
public static void main( String [] args )
{
HanoiClient app = new HanoiClient( );
// ask user for number of disks
while ( true )
{
int numDisks = app.getNumberOfDisks( );
( app.getTOfH( ) ).setDisks( numDisks );
app.setStarted( true );
// start
app.recursiveTOfH( ( app.getTOfH( ) ).getDisks( ), 0, 2, 1 );
// finish last step in animation
app.repaint( );
System.out.println( "Done " );
// done
try
{
Thread.sleep( 5000 ); // wait for the animation to finish
}
catch ( Exception e )
{
}
JOptionPane.showMessageDialog( null, "Done" );
}
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.