
Exercises and problems in Informatics September 2004 
New exercises of sign I
I. 82. Write a program (i82.pas, ...) that  after a number r>0 has been entered  displays the circle of inversion with radius r, further
a) if the real numbers a, b and c are given, it displays the image of the parabola y = ax^{2} +bx+c under the inversion,
b) if the real numbers a and b are given, it displays the image of the line y=ax+b under the inversion.
The program should be able to display more images (either of type a) or b)) simultaneously. If the circle of inversion with radius r is centered at the origin, then the image of a point (x,y) in the plane (different from the origin) under this transformation is defined to be
\(\displaystyle
\left(\frac{x\cdot r^2}{x^2+y^2},\frac{y\cdot r^2}{x^2+y^2}\right).
\)
(10 points)
I. 83. Let us define a set H consisting of numbers of the form \(\displaystyle x+y\sqrt5\) with x and y being arbitrary integers. It can be seen that sums, differences, products and powers with positive integral exponents of elements of H also belong to H. However, the quotient of two such elements does not necessarily lie in H. To include these, it is enough to consider an extended set B, consisting of elements of H divided by positive integers. (To see this, multiply the numerator and denominator of the quotient with the conjugate root \(\displaystyle xy\sqrt5\) of the denominator and simplify.)
Write a program (i83.pas, ...) that can perform the four fundamental operations of arithmetic as well as raising to powers with integral exponents on the elements of B. The program should be able to do this in a sequential way, where variables may depend on previous ones. The symbol \(\displaystyle \sqrt5\) can be replaced by an otherwise unused character, such as @.
An input may look like this: a=53@; b= 4+7@; c=a/12; d=b/43; e=d^7; f=c+e; g=f/b.
(10 points)
I. 84. Display the sequences defined by the iterations x_{n}=min (x_{n1},x_{n2})x_{n3} (n>3), and x_{n}= max (x_{n1},x_{n2})x_{n3} (n>3) in the first and third columns of your spreadsheet, respectively. The 3 arbitrary integers (that is, the starting values) entered into the first 3 cells of the first column should automatically be copied into the first 3 cells of the third column. If the first (or second) sequence happens to become periodic, a warning (``Per.'') should appear in the corresponding row in the second (or fourth) column. The period length(s) should be indicated in the first two cells of the fifth column. Your sheet is to be submitted (i84.xls).
(10 points)
Send your solutions by email to: i@komal.hu
We recommend our readers to explore the program Euklides (available on the Internet), since some forthcoming problems are planned to be based on this software.
New problem of sign S
S. 1. Write a program which converts decimal fractions to proper fractions. Read the input; each line consists of at most 14 decimal digits and a decimal point. (It is not required to check the input, it can be assumed syntactically correct.) For each line of the input, find the smallest nonnegative integer a and positive integer b such that the initial segment of the decimal expansion of \(\displaystyle \frac{a}{b}\) (without rounding) coincides with the input, then write out the fraction \(\displaystyle \frac{a}{b}\). See example on page 364.
Example: 
Input  Output 
0 1.01 1.010 1.0100 3.14 3.1415926535897 
0/1 52/51 92/91 101/100 22/7 20530996/6535219 
The programs will be tested on datasets of different size  at most 6, 10 and 14 digits per line. To achieve the maximum score, the program must finish within a few minutes. If your program responses only for inputs of six or ten digits in a given time, you can get only 6 or 8 points, respectively.
(10 points)
Send your solutions by email to: s@komal.hu
Deadline: 15 October 2004
