0112 - Fractie Minima

Cerinţa

Să se scrie un program care citește un șir de n numere naturale şi determină cea mai mică fracţie care poate fi scrisă cu numărătorul şi numitorul dintre cele n numere.

Date de intrare

Programul citește de la tastatură numărul n, iar apoi n numere naturale nenule, separate prin spaţii.

Date de ieşire

Programul afișează pe ecran numărul fracţia cerută, în forma fractie.

Restricții și precizări

• n ∈ Ν
• 0 < n < 1.001
• cele n numere citite vor fi mai mici decât 2.000.000.000
• fracţia afişată va fi ireductibilă

Exemplu1

Intrare

5

6 10 3 2 5

Ieșire

Datele de intrare corespund restricțiilor impuse.

1/5

Explicație

Cea mai mică fracţie care se poate scrie cu numerele din şire este 2/10. Prin simplificare se obţine fracţia ireductibilă 1/5.

Exemplu2

Intrare

4

5 9 2 14

Ieșire

Datele de intrare corespund restricțiilor impuse.

1/7

Explicație

Cea mai mică fracţie care se poate scrie cu numerele din şire este 2/14. Prin simplificare se obţine fracţia ireductibilă 1/7.

Rezolvare

def validare_date(numar, numere):
    flag = False
    if 0 < int(numar) < 1001:
        flag = all(isinstance(x, int) and 1 <= x <= 2_000_000_000 for x in numere)
    return flag


def gcd(a, b):
    while b:
        a, b = b, a % b
    return a


def fractie_minima(numere):
    max_numar = -1
    min_numar = float('inf')
    for numar in numere:
        if numar < min_numar:
            min_numar = numar
        if numar > max_numar:
            max_numar = numar
    div = gcd(max_numar, min_numar)
    x = min_numar // div
    y = max_numar // div
    m = gcd(x, y)
    return str(x // m) + '/' + str(y // m)


if __name__ == '__main__':
    n = int(input())
    numere = list(map(int, input().split()))
    if validare_date(n, numere):
        print("\nDatele de intrare corespund restricțiilor impuse.\n")
        fractie = fractie_minima(numere)
        print(fractie)
    else:
        print("Datele de intrare nu corespund restricțiilor impuse.")

Explicație

Acest program primește la intrare un număr întreg n și o listă de n numere întregi numere. Scopul programului este să găsească cea mai mică fracție care poate fi obținută prin împărțirea oricărui număr din listă la alt număr din listă, și să o afișeze în formă de fracție simplificată.

Funcția gcd calculează cel mai mare divizor comun al doi întregi folosind algoritmul lui Euclid.

Funcția fractie_minima găsește cea mai mică fracție care poate fi obținută prin împărțirea oricărui număr din listă la alt număr din listă, și o afișează în formă de fracție simplificată. Funcția ia fiecare pereche de numere din listă și calculează fracția obținută prin împărțirea celui mai mic dintre ele la cel mai mare dintre ele. Apoi, calculează cel mai mare divizor comun al celor două numere, simplifică fracția și o stochează în variabila fractie. La sfârșit, funcția returnează fracția sub forma unui șir de caractere.

În funcția principală, programul citeste valorile de intrare și apoi verifică dacă respectă condițiile impuse de funcția validare_date. Dacă valorile sunt valide, programul apelează funcția fractie_minima și afișează rezultatul.