Programming Activity 13-2 Guidance ================================== Overview -

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
*/

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

Hi,

As given in the method desciption, towers of hanoi can be solved recursively by using the following strategy,
1. move n-1 disks from source to auxilary tower
2. move last disk from source to destination tower
3. move n-1 disks on auxilary tower to destination tower.
here methods are already given, so lets try to implement that.

public void recursiveTOfH(int numDisks, int fromTower, int toTower, int useTower)
{

if (numDisks > 0)
{
recursiveTOfH(numDisks -1, fromTower, useTower, toTower); //first step

String moveMessage =

    "Move disk " + numDisks +

    " from tower " + fromTower +

    " to tower " + toTower;

System.out.println(moveMessage);

  moveDisk(numDisks, fromTower, toTower); //second step

recursiveTOfH(numDisks -1, useTower, toTower, fromTower); // 3rd step

}

else

return;
}

Thumbs up if this was helpful, otherwise let me know in comments.Good Day.

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.