View source for 4260 - Nr X Div Imp

= Cerința =
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 <code>a</code> de numere întregi și trei numere întregi <code>st</code>, <code>dr</code> și <code>x</code>, returnează numărul de apariții ale numărului <code>x</code> în vectorul secvența <code>a[st], a[st+1], ..., a[dr]</code>.

= Restricții și precizări =

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

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

= Important =
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>