THINK FIRST·CODE LATER

← All labs

The Sierpinski triangle and T(n) = 3T(n − 1) + 1

Problem

The Sierpinski triangle of order 0 is a single star. A triangle of order n is made of three triangles of order n − 1: one on top, one at the bottom left, one at the bottom right.

Write Sierpinski: read the order n (0 to 6) and draw the triangle on a grid of characters with a recursive method

draw(order, top, centre)     // a triangle whose top star is at row 'top', column 'centre'

A triangle of order n is 2ⁿ rows high; its three parts are placed at (top, centre), (top + half, centre − half) and (top + half, centre + half) with half = 2ⁿ⁻¹. Print the grid without spaces at the end of the lines, then the number of stars and of calls. For the input

3

the program prints

       *
      * *
     *   *
    * * * *
   *       *
  * *     * *
 *   *   *   *
* * * * * * * *
Order 3: 27 stars, 40 calls

Before running it for order 5: how many stars, and how many calls?

Data for this lab

Your program reads its data from standard input. Download the file, then give it to your program as shown below. Start with data set 1: its expected output is given.

d7-8-data-1.txt

3
What your program must print for d7-8-data-1.txt
       *
      * *
     *   *
    * * * *
   *       *
  * *     * *
 *   *   *   *
* * * * * * * *
Order 3: 27 stars, 40 calls

Run your program first, then open this and compare line by line: your output must contain these lines exactly.

How to give the file to my program

Terminal (macOS, Linux, or Windows Command Prompt), after compiling:

java Main < d7-8-data-1.txt

Windows PowerShell does not understand <:

Get-Content d7-8-data-1.txt | java Main

IntelliJ IDEA: Run → Edit Configurations → Redirect input from. Or simply paste the content of the file into the console when the program waits for input.

Write it here or in your IDE, then paste it. Compile and test it yourself before comparing. Your code stays in your browser — it is never sent to or stored on the server.