Recursion Class/Home work #2

  1. Sort an array with merge sort.
  1. Write TowerOfHanoi application that will print the steps to solve Tower Of Hanoi puzzle and the number of steps it took.

Example input:

How many discs? 3

Example of output:

Move disc from 1 to 3

Move disc from 1 to 2

Move disc from 3 to 2

Move disc from 1 to 3

Move disc from 2 to 1

Move disc from 2 to 3

Move disc from 1 to 3

7 steps.

Visual representation of this output will be:

Tower of Hanoi funny facts:

If the monks move disks at the rate of one per second, it would take more than 348 centuries for them to finish a 40-disc problem (assuming that they do not make a mistake) and the 64-disc problem would take more than 1.4 million centuries. Even computers are no match for exponential growth. A computer that can do a billion operations per second will still take centuries to do 2^64 operations, and no computer will ever do, say 2^1000 operations. The lesson is profound: Your computer is just not fast enough to run every short Java program that you write, no matter how simple the program might seem!

2. Create array of 20 integers, populate it with random numbers, display it, sort it using Merge sort, and display it again.

BONUS: Write a java application that creates the following figure:

The only drawing method this figure uses is drawLine(). The basic figure is a triangle. But rather than draw the full sized triangle, draw three half-sized triangles:

  • The left vertex of the lower left triangle is the same as the left vertex of the big triangle. Its other two vertices are halfway along the bottom and left sides of the big triangle.
  • The right vertex of the lower right triangle is the same as the right vertex of the big triangle. Its other two vertices are halfway along the bottom and right sides of the big triangle.
  • The top vertex of the top triangle is the same as the top vertex of the big triangle. Its other two vertices are halfway along the right and left sides of the big triangle.

Write a method drawTriangle( int centerX, int centerY, int side ) that draws the three sides of the triangle centered at (centerX, centerY) if side is small. Otherwise, it draws three triangles.

Instead of using coordinates of the center, you can use the coordinates of the left corner of the circle( drawTriangle( int cornerX, int cornerY, int side ) )

You can do Sierpinski carpet instead of Sierpinski triangle.