Exercises and problems in Informatics May 2002

Please read The Conditions of the Problem Solving Competition.

I. 25. According to Zeckendorf's theorem, every natural number n can uniquely be expressed as a sum of Fibonacci numbers n=F_k1+F_k2+...+F_kr such that k_i$\displaystyle \ge$k_i+1+2 and k_r$\displaystyle \ge$2 hold for all i (1i<r), where, as usual, Fibonacci numbers satisfy F₀=0, F₁=1 and F_k=F_k-1+F_k-2 (k>1).

Given a natural number n (1n 10⁷), your program (I25.pas,...) should decompose it into a sum of Fibonacci numbers. (Efficiency of your solution will also be taken into account.) (10 points)

I. 26. Let us consider a square. The Sierpinski carpet is obtained by recursively taking off smaller and smaller squares: at the first level the middle square with side being one-third of the original one is removed. Then, in the second level, divide the remaining area into 8 smaller squares and repeat the previous process again. The remaining 8

.8 squares (with area being one-ninth of the previous squares each) are handled in the same way in the third level, and so on.

level 1	level 2	level 3	level 4

Prepare your program (I26.pas,...) which reads the number of the level, and draws the corresponding Sierpinski carpet. (Parts that have not been removed should be coloured grey.) (10 points)

I. 27. The French flag problem is the following control problem. N adjacent cells (operating in the same way) should be equipped with and appropriate state-transition function (that is a formula to be written into the cell) such that the cells form a French flag pattern as a result (i.e. N/3 cells become red, N/3 cells become white and N/3 cells become blue).

In the initial state, on disturbing the leftmost cell, 3 waves (i,j,k) emerge from it. The i-wave stays for 1 time step in each cell before moving to its right neighbour. The j-wave stays for 2, while the k-wave stays for 5 time steps in a cell before moving to the next one. The i-wave is reflected from the rightmost cell and annihilates each of the waves it encounters.

The original grey colour of a cell changes according to the type of the wave: i-waves give blue, j-waves give white and k-waves give red colour to the cells they pass over. If a cell meets a reflected i-wave, its colour is unchanged in the future.

Figure 1	Figure 2	Figure 3

If the leftmost cell is disturbed once more, then it initiates i-, j- and k-waves, and the pattern is formed again (see Figure 2). Finally, if the row of cells is pulled apart (that is an empty column is inserted), then the pattern will appear in both parts (see Figure 3). (Figures are on the bottom page of this paper.) Prepare an Excel sheet (I27.XLS) that solves the French flag problem. (10 points)

Send your solutions to the following e-mail address:

infotech@komal.elte.hu.

Deadline: 13 June 2002