0523 - SecvEgale

Cerinţa

Se dă un vector cu n elemente, numere naturale. Determinați cea mai lungă secvență de elemente egale din vector. Dacă în vector există mai multe secvențe de elemente egale de lungime maximă se va determina cea mai din dreapta.

Date de intrare

Programul citește de la tastatură numărul n, iar apoi n numere naturale, reprezentând elementele vectorului.

Date de ieșire

Dacă datele sunt introduse corect, pe ecran se va afișa: "Datele sunt introduse corect.", apoi pe un rând nou numărul c, reprezentând valoarea cerută. În cazul contrar, se va afișa pe ecran: "Datele nu corespund restricțiilor impuse.".

Restricţii şi precizări

1 ≤ n ≤ 1000
cele n numere citite vor fi mai mici decât 1000
indicii elementelor vectorului sunt cuprinși între 1 și n

Exemplu

Intrare: 10; 5 5 1 1 1 1 2 2 2 2
Ieșire: Datele nu corespund restricțiilor impuse.; 7 10

Rezolvare

Rezolvare ver. 1

0523 - SecvEgale

def validare(v):

   return len(v) > 0 and all(isinstance(x, int) for x in v)

def citire_date():

   try:
       n = int(input("Introduceti lungimea vectorului: "))
       v = []
       for i in range(n):
           v.append(int(input("Introduceti elementul " + str(i + 1) + " al vectorului: ")))
       if validare(v):
           print("Datele sunt introduse corect.")
           return v
       else:
           print("Datele nu corespund restricțiilor impuse.")
           return None
   except ValueError:
       print("Datele nu corespund formatului așteptat.")
       return None

def rezolvare(v):

   st, dr = 0, 0
   max_lungime = 0
   i = 0
   while i < len(v):
       j = i + 1
       while j < len(v) and v[j] == v[i]:
           j += 1
       lungime = j - i
       if lungime >= max_lungime:
           max_lungime = lungime
           st, dr = i, j - 1
       i = j
   return st, dr

if __name__ == "__main__":

   v = citire_date()
   if v is not None:
       st, dr = rezolvare(v)
       print(f"Perechea cu cea mai mare lungime de elemente egale: ({st + 1}, {dr + 1})")

</syntaxhighlight>

Explicație rezolvare

Funcția citire_date() citește de la tastatură numărul n, apoi n numere întregi, reprezentând elementele vectorului v. Acestea sunt stocate în lista v, care este întoarsă la sfârșitul funcției. Funcția rezolvare(v) primește ca parametru lista v și determină cea mai lungă secvență de elemente egale din vector, returnând indicii de la început și sfârșit ai acestei secvențe. Algoritmul utilizat este unul clasic de parcurgere a vectorului și ținere a unor variabile auxiliare pentru stocarea lungimii maxime a secvenței, precum și indicii corespunzători. Funcția validare(v) primește ca parametru lista v și verifică dacă aceasta este nevidă și conține doar numere întregi. Verificarea se face cu ajutorul funcției încorporate all() și a expresiei isinstance(x, int). În blocul if __name__ == "__main__", se citesc datele de intrare cu ajutorul funcției citire_date(), se validează cu funcția validare(v) și se calculează rezultatul cu ajutorul funcției rezolvare(v). Dacă datele de intrare sunt valide, se afișează rezultatul pe ecran, iar dacă nu, se afișează un mesaj corespunzător.