Cerința[edit | edit source]

Folosind metoda Divide et Impera, scrieți funcția recursivă cu antetul

int NrXDivImp(int a[], int st, int dr, int x)

care primind ca parametri un vector a de numere întregi și trei numere întregi st, dr și x, returnează numărul de apariții ale numărului x în vectorul secvența a[st], a[st+1], ..., a[dr].

Restricții și precizări[edit | edit source]

st ≤ dr
Numele funcției este NrXDivImp.
Vectorul a este indexat de la 1
Se recomandă utilizarea metodei Divide et Impera în rezolvarea problemei.

Exemplu:[edit | edit source]

Dacă a = (2,5,1,5,3,5,5,5,7,6), atunci NrXDivImp(a, 1, 6, 5) = 3, deoarece în secvența 2,5,1,5,3,5 numărul 5 apare de 3 ori. De asemenea, NrXDivImp(a, 9, 10, 5) = 0.

Important[edit | edit source]

Soluția propusă va conține doar funcția cerută. Introducerea în soluție a altor instrucțiuni poate duce la erori de compilare sau de execuție, care vor duce la depunctarea soluției.<syntaxhighlight lang="python3"> def NrXDivImp(numar_a, stanga, dreapta, numar_x):

   # Caz de bază: intervalul are un singur element
   if stanga == dreapta:
       return int(numar_a[stanga] == numar_x)

   # Împărțim intervalul în două jumătăți
   mijloc = (stanga + dreapta) // 2

   # Apelăm funcția pentru fiecare jumătate și adunăm rezultatele
   return (NrXDivImp(numar_a, stanga, mijloc, numar_x) +
           NrXDivImp(numar_a, mijloc + 1, dreapta, numar_x))

Punct de intrare în program

if __name__ == "__main__":

   # Vectorul de numere
   numar_a = [0, 2, 5, 1, 5, 3, 5, 5, 5, 7, 6]

   # Apelăm funcția pentru intervalul [1, 6] și [9, 10]
   rezultat1 = NrXDivImp(numar_a, 1, 6, 5)
   rezultat2 = NrXDivImp(numar_a, 9, 10, 5)

   # Afișăm rezultatele
   print(f'NrXDivImp(a, 1, 6, 5) = {rezultat1}')
   print(f'NrXDivImp(a, 9, 10, 5) = {rezultat2}')

</syntaxhighlight>