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.