
Exercises and problems in Informatics September 2002 
I. 28. It is well known that every permutation
can be decomposed into independent cycles, where, as usual, the
cycle (i_{1},...,i_{k}) means
that the i_{1}^{th} element should be moved
into the i_{2}^{th}, the
i_{2}^{th} element to the
i_{3}^{th},..., the
i_{k1}^{th} element to the
i_{k}^{th} position, finally the
i_{k}^{th} element to the
i_{1}^{th} position to sort those elements in
the canonical order. For example, the permutation (4,3,2,7,5,1,6) of
the numbers (1,2,3,4,5,6,7) can be decomposed into 3 cycles:
(1,4,7,6), (2,3), (5), meaning that in order to recover the original
canonical order, the first element should be moved to the fourth
position, the fourth element to the seventh position, and so on. Your
program (I28.pas, ...) should read a number N and a permutation
of the first N positive integers, then list the independent
cycles which sort that permutation into ascending
order. (10 points)
I. 29. A disc is given by its centre and its
radius. We cut out parts from the disc either by removing a sector
(beginning at ALPHA degrees relative to the north direction
clockwise and with angle BETA degrees), or by removing a ring
(with inner radius B and outer radius K). Your
program (I29.pas, ...) should apply a given number of these operations
to a disc, and draw the remaining figures in each step. The example in
the figure shows the stepwise results of the
operations. (10 points)
     Disc(150,150,100)  Sector(0,30)  Ring(10,20)  Sector(120,45)  Ring(50,75) 
I. 30. Binomial coefficients can be arranged in
the usual Pascal's triangle pattern (see the figure), in which
every element  with the exception of the outermost ones 
is the sum of its upper and upperleft neighbours. Prepare your Excel
sheet (I30.xls) which gives the first 50 rows of Pascal's triangle. It
is important that the size of the table should be 50x50 cells, every
cell should contain the result of the same formula, and the
first element should be placed in cell B2.
1        1  1       1  2  1      1  3  3  1     1  4  6  4  1    1  5  10  10  5  1   1  6  15  20  15  6  1 

Note that this problem is quite similar to the last year's one
I. 9., but the requirements are now different, so
the solution of that problem will not be
accepted. (10 points)
Send your solutions to the following email address:
Deadline: 13 October 2002
