The Sierpinski Fractal
InterviewTime limit1sMemory limit128 MB
Draw the outline of a depth-n Sierpinski triangle in ASCII, 2^n rows tall, with no trailing spaces and blank lines between the test cases.
- Level
Medium5 of 10
- Topics
- Divide and conquer, Recursion, Implementation, String
- Solved
- No attempts yet
Problem
Consider a solid equilateral-triangular region. Divide it into four congruent triangles of half the height and remove the middle one. Apply the same operation recursively to each of the three remaining triangles. Repeating this procedure infinitely many times yields a shape whose area is zero. The fractal produced this way is called the Sierpinski Triangle. Although its topological dimension is , its Hausdorff–Besicovitch dimension is , a non-integer value (which is why it is called a fractal). For comparison, the Hausdorff–Besicovitch dimension of the Norwegian coastline is about , while its topological dimension is .
In this problem you must draw the outline of the Sierpinski Triangle up to a given recursion depth, using only ASCII characters. Because the drawing resolution is fixed, the picture must grow with the recursion depth. Draw the smallest triangle (the one that is not subdivided any further) with two slashes (/), two backslashes (\), and two underscores (_) like this:
/\
/__\
To see how larger triangles are drawn, look at the example outputs below. A picture of depth consists of exactly rows: a triangle of depth is formed from three triangles of depth — one placed at the bottom left, one at the bottom right, and one centered above the other two.
Input
The input contains several test cases. Each test case is a single integer . The input is terminated by . Otherwise , where is the recursion depth.
Output
For each test case, draw the outline of the Sierpinski Triangle; the picture has rows. Align the output to the left, that is, print the bottom-left slash in the first column. No line may contain trailing blanks. Print a single empty line between consecutive test cases, and do not print an extra empty line after the last test case.