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, pe ecran se va afișa: "Datele sunt introduse corect.", apoi pe un rând nou afișează numărul nivelului pe care se află fracția sau o fracție echivalentă (având aceeași valoare) cu aceasta.
În caz contrar, 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
- Datele de intrare
- Introduceti doua numere naturale:
- 13 8
- Datele de ieșire
- Datele sunt introduse corect.
- 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
def validare_input(n, m):
"""
Verifică dacă datele de intrare sunt valide.
"""
if n < 1 or n > 2000000000 or m < 1 or m > 2000000000:
return False
return True
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("Datele sunt introduse corect.")
print(nivel_fracție(n, m))
else:
print("Datele nu corespund restricțiilor impuse.")
Explicatie cod:
Codul dat începe cu o funcție nivel_fracție care primește două numere întregi pozitive n și m. Scopul funcției este de a determina nivelul la care fracția n/m apare în șirul de fracții în ordine crescătoare generat astfel:
nivelul 1: 1/1
nivelul 2: 1/2, 2/1
nivelul 3: 1/3, 2/3, 3/2, 3/1
nivelul 4: 1/4, 2/4, 3/4, 4/3, 4/2, 4/1 și așa mai departe.
Pentru a face acest lucru, se pornește de la fracția 1/1 și se generează toate fracțiile posibile la nivelul curent, folosindu-se de fracțiile de la nivelul anterior. De exemplu, pentru a genera fracțiile nivelului 2, se iau fracțiile de la nivelul 1 și se adaugă la ele fracțiile de forma k/1 și 1/k, unde k este un număr întreg pozitiv mai mare decât 1. În cazul de față, se folosește o listă fracții pentru a ține evidența fracțiilor de la nivelul anterior, iar la fiecare iterație se creează o listă nouă fracții_nivel care conține toate fracțiile la nivelul curent, generându-se astfel toate fracțiile pentru nivelurile următoare.
Funcția se oprește când fracția n/m apare la un anumit nivel nivel și returnează nivel + 1, adică nivelul la care apare această fracție. Dacă fracția nu apare în primele 100 de niveluri, se consideră că nu apare deloc și se returnează -1.
Funcția validare_input este o funcție auxiliară care verifică dacă datele de intrare sunt valide, adică dacă n și m sunt numere întregi pozitive între 1 și 2 miliarde.
În blocul principal, se citește de la tastatură două numere întregi pozitive n și m. Se verifică dacă datele de intrare sunt valide, apelându-se funcția validare_input, și se afișează un mesaj corespunzător. Dacă datele de intrare sunt valide, se apelează funcția nivel_fracție și se afișează rezultatul.
