
Exercises and problems in Informatics May 2002 
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}=0, F_{1}=1 and
F_{k}=F_{k1}+F_{k2}
(k>1).
Given a natural number n (1n 10^{7}),
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
onethird 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 oneninth
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
statetransition 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
iwave stays for 1 time step in each cell before moving to its
right neighbour. The jwave stays for 2, while the
kwave stays for 5 time steps in a cell before moving to the
next one. The iwave 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: iwaves give blue,
jwaves give white and kwaves give red colour to the
cells they pass over. If a cell meets a reflected iwave, its
colour is unchanged in the future.
If the leftmost cell is disturbed once more, then
it initiates i, j and kwaves, 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 email address:
Deadline: 13 June 2002
