KöMaL - Középiskolai Matematikai és Fizikai Lapok
Sign In
Sign Up
 Magyar
Information
Contest
Journal
Articles
Contest Rules
Entry Form
Problems
Results
Previous years

 

Exercises and problems in Informatics
September 2002

Please read The Conditions of the Problem Solving Competition.

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      
11     
121    
1331   
14641  
15101051 
1615201561

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 e-mail address:

Deadline: 13 October 2002

Our web pages are supported by:   Ericsson   Cognex   Emberi Erőforrás Támogatáskezelő   Emberi Erőforrások Minisztériuma   Nemzeti Tehetség Program    
MTA Energiatudományi Kutatóközpont   MTA Wigner Fizikai Kutatóközpont     Nemzeti
Kulturális Alap   ELTE   Morgan Stanley