 Mathematical and Physical Journal
for High Schools
Issued by the MATFUND Foundation
 Already signed up? New to KöMaL? # Exercises and problems in InformaticsSeptember 2002

I. 28. It is well known that every permutation can be decomposed into independent cycles, where, as usual, the cycle (i1,...,ik) means that the i1th element should be moved into the i2th, the i2th element to the i3th,..., the ik-1th element to the ikth position, finally the ikth element to the i1th 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 upper-left 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)