You cannot submit for this problem because the homework's deadline is due.

Related Topics: abstraction, specification, recursion

Description

Scientists have predicted an upcoming earthquake. You live in an square area full of buildings. The scientists say that how the earthquake destroys buildings will follow the following algorithm:

1. Equally divide the square into 4 smaller squares, and the left-upper part will all be destroyed.
2. For each of the remaining 3 smaller squares, also divide them into 4 smaller squares, and the left-upper part will be destroyed
3. Repeat until the square can no longer be divided

To save your life, you need to write a program to calculate which buildings will be destroyed.

Requirement

You will use simple recursion to solve this exercise. Recursion is to call the function itself inside the function body, as if the function has already been implemented. See Takeaway for some hints.

Input Format

An integer \(n\) (1 <= n <= 10) that stands for a 2^n by 2^n square.

Output Format

A 2^n by 2^n square , where 0 indicates destroyed, 1 indicates safe.

Sample Input

3

Sample Output

0 0 0 0 0 0 0 1
0 0 0 0 0 0 1 1
0 0 0 0 0 1 0 1
0 0 0 0 1 1 1 1
0 0 0 1 0 0 0 1
0 0 1 1 0 0 1 1
0 1 0 1 0 1 0 1
1 1 1 1 1 1 1 1

Takeaway

We used simple recursion in this exercise. Many people think recursion is the first difficult concept when learning programming. However if you are familiar with the concept of procedural abstraction and specification comment, you can understand recursion easily by imagining the function as a black box with properly defined behavior, and calling the function inside itself is like using that black box in advance.