2308 - Fractzii

Sursa: [1]

Cerinţa

O proprietate interesanta a fracțiilor ireductibile este ca orice fracție se poate obține după următoarele reguli: - pe primul nivel se afla fracția 1/1; - pe al doilea nivel, în stânga fracției 1/1 de pe primul nivel, plasam fracția 1/2 iar în dreapta ei fracția 2/1;

nivelul 1: 1/1 nivelul 2: 1/2 2/1

- pe fiecare nivel k se plasează sub fiecare fracție i / j de pe nivelul de deasupra, fracția i / (i + j) în stânga, iar fracția (i + j) / j în dreapta.

nivelul 1: 1/1 nivelul 2: 1/2 2/1 nivelul 3: 1/3 3/2 2/3 3/1

Dându-se o fracție oarecare prin numărătorul și numitorul său, determinați numărul nivelului pe care se află fracția sau o fracție echivalentă (având aceeași valoare) cu aceasta.

Date de intrare

Programul conține pe prima linie două numere naturale nenule N M, separate printr-un spațiu, reprezentând numărătorul și respectiv numitorul unei fracții.

Date de ieșire

Programul va conţine o ingură linie, pe care va fi scris număr natural nenul, reprezentând numărul nivelului care corespunde fracţiei."

Dacă datele sunt introduse corect, programul va rula.

În cazul în care datele nu respectă restricțiile, se va afișa pe ecran: "Datele nu corespund restricțiilor impuse.".

Restricţii şi precizări

1 ≤ N, M ≤ 2 000 000 000

Exemplul 1

Intrare: 13 8
Ieșire: 6

Rezolvare

2308

def nivel_fracție(n, m):

   nivel = 1
   fracții = 1, 1

   while True:
       fracții_nivel = []
       for fracție in fracții:
           fracții_nivel.append([fracție[0], fracție[0] + fracție[1]])
           fracții_nivel.append([fracție[0] + fracție[1], fracție[1]])

       if [n, m] in fracții_nivel:
           return nivel + 1
       elif nivel == 100:  # pentru a evita o buclă infinită
           return -1

       fracții = fracții_nivel
       nivel += 1

if __name__ == '__main__':

   n, m = map(int, input("Introduceti doua numere naturale: ").split())

   if n >= 1 and n <= 2000000000 and m >= 1 and m <= 2000000000:
       print(nivel_fracție(n, m))
   else:
       print("Numerele introduse trebuie sa fie in intervalul [1, 2000000000].")

</syntaxhighlight>

Explicatie cod:

Această funcție calculează nivelul fracției într-un șir de fracții construit prin regula Farey. Funcția primește două numere naturale, n și m, și returnează nivelul fracției corespunzătoare lui n/m în șirul de fracții.

Regula Farey spune că șirul de fracții proprii în ordine crescătoare și cu numitor mai mic sau egal cu m poate fi generat astfel:

Începem cu fracția 0/1 și 1/1 Pentru fiecare fracție consecutivă, adăugăm fracția imediat superioară și fracția imediat inferioară, cu condiția ca numitorul să nu depășească m. De exemplu, pentru m = 5, șirul de fracții este: 0/1, 1/5, 1/4, 1/3, 2/5, 1/2, 3/5, 2/3, 3/4, 4/5, 1/1

Funcția utilizează o buclă while pentru a genera șirul de fracții în mod iterativ, pornind de la fracția 1/1 și verificând dacă fracția n/m apare în șir. Dacă apare, funcția returnează nivelul la care apare în șir (adică numărul de fracții adăugate la șir până la fracția căutată, plus 1). Dacă fracția nu apare în șir și s-a ajuns la nivelul maxim (nivel == 100), se returnează -1 pentru a semnala că fracția nu există în șir.

Pentru a valida intrările utilizatorului, se verifică dacă cele două numere sunt în intervalul [1, 2000000000]. Funcția map este folosită pentru a converti cele două valori introduse de utilizator din string-uri în numere întregi.