Şirul lui Cantor

Matematicianul Georg Ferdinand Ludwig Philipp Cantor a demonstrat că mulţimea numerelor raţionale este numărabilă, considerând reprezentarea de mai jos-stânga.
Pornind de la această se generează şirul indicat de săgeţi: 1/1, 1/2, 2/1, 3/1, 2/2, 1/3, 1/4, 2/3, 3/2, 4/1, … Pentru un număr n dat (

$1 \leq n \leq 4.000.000$

) să se determine al n-lea termen din acest şir sub formă nr/num. Programul implementat în C va citi de la consola o serie de m numere (neordonate) şi va scrie termenii corespunzători din şirul descris.

$\begin{array}{ccccccccc}1/1 & \rightarrow & 1/2 & & 1/3 & \rightarrow & 1/4 & & \ldots\\& \swarrow & & \nearrow & & \swarrow & & & \ldots\\2/1 & & 2/2 & & 2/3 & & 2/4 & & \ldots\\\downarrow & \nearrow & & \swarrow & & & & &\ldots\\3/1 & & 3/2 & & 3/3 & & 3/4 & & \ldots\\& \swarrow & & & & & & &\ldots\\4/1 & & 4/2 & & 4/3 & & 4/4 & & \ldots\\\ldots & & \ldots & & \ldots & &\ldots & & \ldots\end{array}$

$\begin{array}{cccccc}linia_1: & 1/1 & & & & \\linia_2: & 1/2 & 2/1 & & & \\linia_3: & 3/1 & 2/2 & 1/3 & & \\linia_4: & 1/4 & 2/3 & 3/2 & 4/1 & \\linia_5: & 5/1 & 4/2 & 3/3 & 2/4 & 1/5 \\\end{array}$

Dacă aranjăm elementele şirului pe linii vom obţine reprezentarea de sus-dreapta. Elementele şirului se parcurg apoi în ordine pe linii, de la stânga la dreapta. Un element al şirului poate fi dedus pe baza următoarelor proprietăţi:

linia i are i elemente,
$\forall i \geq 1$
;
suma
$num+nr$
a fiecărui element (
$nr/num$
) de pe linia i este i+1,
$\forall i \geq 1$
;
dacă i este linie pară, primul element este 1/i, numărătorul şi numitorul următoarelor elemente se obţin adunând, respectiv scăzând 1 din numărătorul şi respectiv numitorul elementului precedent;
dacă i este linie împără, primul element este i/1, numărătorul şi numitorul următoarelor elemente se obţin scăzând, respectiv adunând 1 din numărătorul şi respectiv numitorul elementului precedent.

Exemple: termenul 1 este 1/1; termenul 3.999.999 este 2621/208; termenul 3 este 2/1; termenul 14 este 2/4; termenul 2.000.000 este 1000/1001; termenul 789 este 9/32.