Machine Problem 3, due October 17

Part of the homework for 22C:60 (CS:2630), Fall 2011
by Douglas W. Jones
THE UNIVERSITY OF IOWA Department of Computer Science

Submit the source file mp4.a (or mp4.txt if you must) for your solution on or before the indicated date.

The Problem

     /             /         /         /
    /\            /\        /\        /
     /\/           /\/        \/
    / /           / /         /
 / /\    /     / /
/\/  \  /\    /\/
  \/  \  /\/    \/
  /    \/ /     /
     / /      
    /\/       
      \/      
      /

The above figure shows 4 H-trees. On the left is a 4^th-order H-tree, while on the right is a 1^st-order H-tree. H-trees are an example of a fractal figure. Each higher-order H-tree is composed of two of the next-smaller order H-trees connected by a diagonal line. These H figures are formed of ASCII characters, just slashes and backslashes.

Write a recursive subroutine haich(x,y,n) that plots an n'th order H-tree centered (as much as is possible) at location x,y on the screen. And, write a main program that calls haich() to plot the largest H-tree that will fit on the screen, centered on the screen.

Notes: The hawk monitor calls the main program with two parameters, the width (in R3) and height (in R4) of the display screen. Resize your terminal window before starting the emulator. The center coordinates of the screen are simply the width and height over two. To figure out the size of H-tree, you'll need to do some computing, probably counting up to the H-tree size while you compute the size as a function of the previous size. Work out this logic in a high level language first before you try writing code!

To find the center of the screen, you will have to divide the height and width by two. The Hawk manual has a section on multiplication and division that includes a subsection on dividing by powers of two. Divide by two takes just one instruction.

Mutual recursion of two different H-tree routines may be a good idea here, since the even and odd H-trees tilt in opposite directions. Write code one that leans left and a separate version that leans right. As a result, your top-level haich() will call either haichl() or haichr() (left leaning or right leaning H) depending on whether n is even or odd.

The sequence of two monitor calls, putat(x,y) followed by putchar('c') will put the letter c on the screen at the indicated x and y coordinates.

Finally, note that the Hawk emulator will run in any size terminal window, but you must resize the window before launching the emulator. If you set the font size very small and stretch the window large, you can plot some huge H-trees.