2808 - Produs4

Cerința

Subprogramul produs are doi parametri, în această ordine:

• a, prin care primește un număr natural (a∈[1,106]);
• k, prin care furnizează cea mai mare valoare naturală impară cu proprietatea că produsul tuturor numerelor impare din intervalul [1,k] este mai mic sau egal cu a.

Scrieți definiția completă a subprogramului în Python.

Date de intrare

• a - un număr natural (a∈[1,106])
• k - cea mai mare valoare naturală impară cu proprietatea că produsul tuturor numerelor impare din intervalul [1,k] este mai mic sau egal cu a.

Date de ieșire

• Funcția trebuie să returneze un singur număr întreg - valoarea lui k, conform cerinței.

Exemplu

Dacă a=200, atunci k=7 (1⋅3⋅5⋅7 ≤ 200 <1⋅3⋅5⋅7⋅9).

Rezolvare

<syntaxhighlight lang="python"> def validate_produs(a, k):

   if not isinstance(a, int) or a < 1 or a > 10**6:
       return False
   if not isinstance(k, int) or k < 1 or k > 10**6 or k % 2 == 0:
       return False
   return True

def produs(a, k):

   i = int(a**0.5) | 1
   p = 1
   while i > 0 and p * i <= a:
       p *= i
       i -= 2
   if p > a:
       return None
   return i + 2

def main():

   a = int(input("Introduceti numarul a: "))
   k = int(input("Introduceti numarul k: "))
   if not validate_produs(a, k):
       print("Date de intrare invalide")
       return
   print("Valoarea maxima pentru k este:", produs(a, k))

</syntaxhighlight>

Explicație

• Pe prima linie, calculăm cel mai mare număr impar mai mic sau egal cu radicalul lui a. Folosim operatorul bitwise OR (|) cu 1 pentru a ne asigura că numărul întors este impar.
• Inițializăm produsul cu 1 și folosim un loop while pentru a verifica dacă produsul tuturor numerelor impare de la 1 la k este mai mic sau egal cu a. Pornim de la i și decrementăm cu 2 la fiecare iterație pentru a număra doar numerele impare. Dacă produsul devine mai mare decât a, ieșim din buclă.
• Verificăm dacă produsul este mai mare decât a și returnăm None dacă da, altfel returnăm ultimul număr impar găsit (i + 2), deoarece produsul tuturor numerelor impare până la acel număr este mai mic sau egal cu a.