KöMaL - Középiskolai Matematikai és Fizikai Lapok
Sign In
Sign Up
 Magyar
Information
Contest
Journal
Articles

 

Problem I. 259. (February 2011)

I. 259. Recursion is a tool often used both in mathematics and in informatics. It can appear in different stages during the solution of a problem, for example, in the specification part, in algorithmic planning, or during the coding in the programming language.

One typically uses a function to give the specification. This function effectively establishes a connection between the input and the output. Let us first consider the power function for example. A possible definition is the following: \(\displaystyle x^{n}=x\cdot x^{n-1}\) and \(\displaystyle x^{0}=1\), or, in other words,

\(\displaystyle \mathop{\rm power}\, (x,n)= \begin{cases} 1 & \text{if \ } n=0, \\ x \cdot \mathop{\rm power}\, (x,n-1) & \text{if \ } n>0. \end{cases} \)

In this way, the computation of \(\displaystyle 5^{3}\) is reduced to \(\displaystyle 5\cdot 5^{2}\), that is to \(\displaystyle 5^{2}\), then to \(\displaystyle 5^{1}\), finally, to \(\displaystyle 5^{0}\), which is defined separately. The above task can be solved effectively with a recursive algorithm:

In functional programming languages, like ImagineLogo, coding simply follows from the above:

Non-recursive languages, like Pascal, may also allow this coding to be implemented:

Algorithms and programs defined iteratively can be rewritten in a recursive fashion. Sequences and conditionals, as the most important algorithmic blocks, can be transformed without any difficulty or modification. Loops however require some revision to make them recursive. The following scheme illustrates how to reformulate a pre-test loop (that is, a loop in which the loop test is evaluated before the body of the loop):

Example. Create the sequence of natural numbers between \(\displaystyle A\) and \(\displaystyle B\) (\(\displaystyle 1\le A,B\le 100\)). In the solution below, the procedure Előállít(5, 10, Sor, 1) puts the sequence 5 6 7 8 9 10 into the array Sor.

I. Iterative solution:

II. Recursive solution:

Your task is to create a program that produces the following sequences without using any loop.

\(\displaystyle a)\) Write a function to create a ``mountain of numbers'' of height \(\displaystyle N\) (\(\displaystyle N\ge 1\)). Example: mountain 5 Result: 1 2 3 4 5 4 3 2 1;

\(\displaystyle b)\) Write a function to create a ``mountain chain of numbers'' of height \(\displaystyle N\). Example: chain 4 Result: 1 1 2 1 1 2 3 2 1 1 2 3 4 3 2 1;

\(\displaystyle c)\) Write a function to create a ``staircase of numbers'' of height \(\displaystyle N\). Example: staircase 6 Result: 1 2 2 3 3 3 4 4 4 4 5 5 5 5 5 6 6 6 6 6 6;

\(\displaystyle d)\) Write the first \(\displaystyle N\) elements of the following recursive sequence: \(\displaystyle a_{1}=-1\) and \(\displaystyle a_{n}=-4 - 3a_{n-1}\).

The first argument to your program is the value of \(\displaystyle N\), while the output file is specified by the second argument. The output file should contain one sequence in each line. Elements of a sequence should be separated by a space. You should not use loops when writing into the file.

The source code (i259.pas, i259.cpp, ...) together with a short documentation (i259.txt, i259.pdf, ...) -- also describing which developer environment to use for compiling, further a brief description of your solution -- should be submitted.

(10 pont)

Deadline expired on 10 March 2011.


Sorry, the solution is available only in Hungarian. Google translation

Mintamegoldásként Szabó Attila (Pécs, Leőwey Klára Gimnázium, 10. osztály) tanuló munkáját közöljük: i259.pas


Statistics:

11 students sent a solution.
10 points:Gema Barnabás, Hoffmann Áron, Kalló Kristóf, Seres Márk Dániel, Szabó 928 Attila.
9 points:Barta 111 János, Kocsis 789 Mátyás, Leitereg András, Sztanka-Tóth Tamás, Varga 256 Erik.
7 points:1 student.

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