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

• 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:

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

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.

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}')