3981 - DivImpRec

Cerința

Scrieți funcția recursivă DivImpRec care primind ca parametru un număr natural nenul n, returnează cel mai mare divizor impar al său.

Restricții și precizări

• 1 ⩽ n ⩽ 2.000.000.000
• Numele funcției este DivImpRec.
• Se recomandă utilizarea recursivității în rezolvarea problemei.

Date de intrare

Programul citește de la tastatură numărul n.

Date de ieșire

Dacă datele sunt introduse corect, pe ecran se va afișa: "Datele introduse sunt corecte.", apoi pe un rând nou valoarea returnată de funcția DivImpRec, reprezentând numărul cerut. În cazul în care numărul introdus depășește limitele date, se va afișa "Numarul introdus nu este valid.", iar dacă numărul introdus nu este întreg, se va afișa "Nu ati introdus un numar intreg."

Exemplu

Intrare

Introduceți un număr întreg pozitiv între 1 și 2.000.000.000: 24

Ieșire

Datele introduse sunt valide.

Cel mai mic divizor impar al numărului 24 este: 3

Rezolvare

def validate_n(n):
    if isinstance(n, int) and 1 <= n <= 2000000000:
        return True
    else:
        return False


def DivImpRec(n):
    if n % 2 == 1:
        return n
    else:
        return DivImpRec(n // 2)


if __name__ == "__main__":
    n = input("Introduceți un număr întreg pozitiv între 1 și 2.000.000.000: ")
    try:
        n = int(n)
        if validate_n(n):
            result = DivImpRec(n)
            print("Datele introduse sunt corecte.")
            print(f"Cel mai mic divizor impar al numărului {n} este: {result}")
        else:
            print("Numărul introdus nu este valid.")
    except ValueError:
        print("Nu ați introdus un număr întreg.")

Explicație

Funcția `validate_n(n)` verifică dacă numărul `n` este un număr întreg între 1 și 2.000.000.000, iar dacă această condiție este îndeplinită, returnează `True`, altfel `False`.

Funcția `DivImpRec(n)` primește un număr întreg `n` și încearcă să găsească cel mai mic divizor impar al lui `n`. Dacă `n` este impar, atunci el este cel mai mic divizor impar și funcția returnează `n`. Dacă `n` este par, atunci îl împarte la 2 și apelează recursiv aceeași funcție cu noul număr.

În `if __name__ == "__main__":` se cere utilizatorului să introducă un număr întreg pozitiv între 1 și 2.000.000.000, care este verificat dacă este valid. Apoi se apelează funcția `DivImpRec(n)` și se afișează cel mai mic divizor impar al numărului `n`, dacă acesta există.