Editing 4261 - Altern Div Imp

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

<syntaxhighlight lang="python" line>
int AlternDivImp(int a[], int st, int dr)
</syntaxhighlight>

care primind ca parametri un vector a de numere naturale și două numere întregi st și dr, returnează 1 dacă în secvența a[st], a[st+1], ..., a[dr] numerele impare alternează cu cele pare, sau returnează 0 dacă există cel puțin două numere alăturate de aceeași paritate.

==Restricții și precizări==
*st ≤ dr
*Numele funcției este AlternDivImp.
*Vectorul a este indexat de la 1
*Se recomandă utilizarea metodei Divide et Impera în rezolvarea problemei.

==Exemplu==
Dacă a = (1,2,3,4,5,6,7,8,9,11), atunci AlternDivImp(a, 1, 10) = 0, deoarece numerele 9 și 11 aflate pe poziții alăturate au aceeași paritate. De asemenea, AlternDivImp(a, 1, 8) = 1.

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

==Rezolvare==
<syntaxhighlight lang="python" line>
#4261 AlternDivImp
def AlternDivImp(a, st, dr):
    if st == dr:
        return 1  # Secvența de lungime 1 este alternantă

    mijloc = (st + dr) // 2

    # Verificăm dacă secvența este alternantă în prima jumătate
    alternanta_stanga = AlternDivImp(a, st, mijloc)

    # Verificăm dacă secvența este alternantă în a doua jumătate
    alternanta_dreapta = AlternDivImp(a, mijloc + 1, dr)

    # Verificăm dacă ultimul element din prima jumătate și primul element din a doua jumătate au aceeași paritate
    if a[mijloc] % 2 == a[mijloc + 1] % 2:
        return 0  # Două numere consecutive au aceeași paritate

    # Secvența este alternantă doar dacă ambele jumătăți sunt alternante
    return alternanta_stanga and alternanta_dreapta

def main():
    # Exemplu de date de intrare
    a = [1, 2, 3, 4, 5, 6, 7, 8]
    st = 0
    dr = len(a) - 1

    # Apelăm funcția și afișăm rezultatul
    rezultat = AlternDivImp(a, st, dr)
    print(rezultat)

if __name__ == "__main__":
    main()

</syntaxhighlight>