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.

Exemplu

DivImpRec(24) = 3.

Explicație

Funcția DivImpRec primește un număr natural n și întoarce cel mai mare divizor impar al lui n.

Dacă n este impar, atunci funcția va întoarce n, altfel se va apela recursiv funcția cu argumentul n // 2.

Deoarece divizorii unui număr se împart în perechi (d, n//d), cel mai mare divizor impar al unui număr se poate obține prin împărțirea repetată a numărului la 2, până când se ajunge la un număr impar.

Rezolvare

<syntaxhighlight lang="python"> 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)

def 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(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 pozitiv.")

</syntaxhighlight>