4261 - Altern Div Imp
Cerința
Folosind metoda Divide et Impera, scrieți funcția recursivă cu antetul
int AlternDivImp(int a[], int st, int dr)
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. Programul va afișa: "Există cel puțin două numere alăturate de aceeași paritate!". De asemenea, AlternDivImp(a, 1, 8) = 1. Programul va afișa: "Secvența este alternantă!".
Dacă a = (1,2,3,4,5,6,7,8,9,-1), atunci programul va afișa: "Datele introduse nu respectă restricțiile!".
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
#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()