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>

1. 4261 AlternDivImp

def verifica_restrictii(a, st, dr):

   if st > dr:
       return False
   if st < 0 or dr >= len(a):
       return False
   for elem in a[st:dr+1]:
       if elem < 0:
           return False
   return True

def citeste_date():

   input_str = input("Introduceți elementele vectorului separate prin virgulă: ")
   elemente = input_str.split(',')
   a = [int(elem) for elem in elemente]
   return a

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():

   # Citim datele de la tastatură
   a = citeste_date()
   st = 0
   dr = len(a) - 1

   # Verificăm restricțiile
   if not verifica_restrictii(a, st, dr):
       print("Datele introduse nu respectă restricțiile!")
       return

   # Apelăm funcția și afișăm rezultatul
   rezultat = AlternDivImp(a, st, dr)
   if rezultat:
       print("Secvența este alternantă!")
   else:
       print("Există cel puțin două numere alăturate de aceeași paritate!")

if __name__ == "__main__":

   main()

</syntaxhighlight>