0518 - SecvZero: Difference between revisions

From Bitnami MediaWiki
← Older editNewer edit →
VisualWikitext
Flaviu (talk | contribs)
277 edits
No edit summary
Flaviu (talk | contribs)
277 edits
No edit summary
Line 34: Line 34:
# 0518 - SecvZero
# 0518 - SecvZero


def validate_input(n, v):
def gaseste_secventa_maxima(vector):
     if n < 1 or n > 1000:
     lungime_maxima = 0
        print("n nu respecta restricțiile impuse")
     pozitie_start = -1
        return False
     lungime_curenta = 0
     if all(elem == 0 for elem in v):
        print("vectorul nu poate contine doar elemente nule")
        return False
     for i in range(n):
        if v[i] < 0 or v[i] > 1000000:
            print("valorile din v trebuie sa fie in intervalul [0, 1000000]")
            return False
    return True


def find_longest_sequence(n, v):
    for i, element in enumerate(vector):
    max_len = 0
         if element == 0:
    start = -1
             lungime_curenta += 1
    end = -1
    i = 0
    while i < n:
         if v[i] == 0:
             i += 1
         else:
         else:
            j = i
             if lungime_curenta > lungime_maxima:
            while j < n and v[j] != 0:
                 lungime_maxima = lungime_curenta
                j += 1
                 pozitie_start = i - lungime_maxima
             if j - i > max_len:
             lungime_curenta = 0
                 max_len = j - i
                 start = i
                end = j-1
             i = j
    return (start+1, end+1)


def read_input():
    if lungime_curenta > lungime_maxima:
     try:
        lungime_maxima = lungime_curenta
        n = int(input("Introduceti valoarea lui n: "))
        pozitie_start = len(vector) - lungime_maxima
        v = list(map(int, input("Introduceti valorile vectorului, separate prin spatiu: ").split()))
 
         if not validate_input(n, v):
     return (lungime_maxima, pozitie_start)
 
 
# functia main
if __name__ == "__main__":
    n = int(input())
    vector = input().split()
 
    # validare date de intrare
    if n <= 0 or n > 1000 or len(vector) != n:
        print("Datele nu corespund restricțiilor impuse.")
    else:
         try:
            vector = [int(elem) for elem in vector]
        except ValueError:
             print("Datele nu corespund restricțiilor impuse.")
             print("Datele nu corespund restricțiilor impuse.")
             return None, None
             exit(0)
        print("Datele sunt introduse corect.")
        return n, v
    except ValueError:
        print("Datele nu corespund formatului așteptat.")
        return None, None


if __name__ == '__main__':
        if max(vector) >= 1000:
    n, v = read_input()
            print("Datele nu corespund restricțiilor impuse.")
    if n is not None and v is not None:
        else:
        start, end = find_longest_sequence(n, v)
            lungime_maxima, pozitie_start = gaseste_secventa_maxima(vector)
        print(start, end)
            print("Datele sunt introduse corect.")
            print(lungime_maxima, pozitie_start)




Line 90: Line 82:
== Explicație rezolvare==
== Explicație rezolvare==


validate_input(n, v) valideaza datele de intrare. Se verifica daca n este in intervalul permis, daca fiecare element din v este mai mic decat 1000 si daca vectorul contine cel putin un element 0. Daca una dintre aceste conditii nu este indeplinita, se afiseaza un mesaj de eroare si se returneaza False.
Funcția validate_input verifică dacă datele introduse de utilizator corespund cerințelor problemei, adică dacă numărul n este în intervalul [1, 1000], toate numerele citite sunt mai mici decât 1000 și vectorul conține cel puțin un element nul. Dacă datele sunt valide, funcția returnează True, altfel returnează False.
find_longest_sequence(n, v) determina cea mai lunga secventa de elemente nule din vector. Se foloseste o metoda de tip "sliding window", unde se parcurge vectorul, se identifica toate secventele de elemente nule si se retine cea mai lunga si pozitia ei de inceput. Deoarece dorim sa identificam cea mai din stanga secventa de lungime maxima, pozitia de inceput a secventei se retine prin variabila start. Se returneaza o pereche de indici, reprezentand capetele secventei.
 
read_input() citeste datele de intrare si le valideaza cu ajutorul functiei validate_input(). Daca datele sunt valide, functia returneaza n si v.
Funcția find_longest_sequence_of_zeros primește ca argument vectorul citit și returnează două numere: lungimea celei mai lungi secvențe de elemente nule din vector și poziția de început a acestei secvențe. Pentru a găsi aceste valori, funcția parcurge vectorul și numără lungimea fiecărei secvențe de elemente nule întâlnite. De fiecare dată când găsește o secvență de elemente nule mai lungă decât cea găsită anterior, funcția actualizează lungimea maximă și poziția de început a acestei secvențe.
In if __name__ == '__main__' se citesc datele de intrare cu ajutorul functiei read_input() si se apeleaza functia find_longest_sequence(), care determina cea mai lunga secventa de elemente nule din vector. Indicii capetelor secventei se afiseaza cu ajutorul functiei print().
 
În main, se citesc datele de intrare de la tastatură, se validează și se apelează funcția find_longest_sequence_of_zeros. Dacă datele introduse sunt valide, se afișează mesajul "Datele sunt introduse corect." și rezultatul returnat de funcția find_longest_sequence_of_zeros. În caz contrar, se afișează mesajul "Datele nu corespund restricțiilor impuse.".

Revision as of 20:53, 13 May 2023

Sursa: 0518 - SecvZero

Cerinţa

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

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 va afișa pe ecran numărul de perechi care îndeplinesc condițiile cerute, 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
  • vectorul va conține cel puțin un element nul

Exemplu 1

Intrare
10
0 1 0 0 0 5 0 0 0 2
Ieșire
Datele sunt introduse correct.
3 5

Exemplu 2

Intrare
2
2 1 1 0 0 3 4
Ieșire
Datele nu corespund restricțiilor impuse.
2 5

Rezolvare

Rezolvare ver. 1

<syntaxhighlight lang="python" line>

  1. 0518 - SecvZero

def gaseste_secventa_maxima(vector): 

   lungime_maxima = 0
   pozitie_start = -1
   lungime_curenta = 0

   for i, element in enumerate(vector):
       if element == 0:
           lungime_curenta += 1
       else:
           if lungime_curenta > lungime_maxima:
               lungime_maxima = lungime_curenta
               pozitie_start = i - lungime_maxima
           lungime_curenta = 0

   if lungime_curenta > lungime_maxima:
       lungime_maxima = lungime_curenta
       pozitie_start = len(vector) - lungime_maxima

   return (lungime_maxima, pozitie_start)


  1. functia main

if __name__ == "__main__": 

   n = int(input())
   vector = input().split()

   # validare date de intrare
   if n <= 0 or n > 1000 or len(vector) != n:
       print("Datele nu corespund restricțiilor impuse.")
   else:
       try:
           vector = [int(elem) for elem in vector]
       except ValueError:
           print("Datele nu corespund restricțiilor impuse.")
           exit(0)

       if max(vector) >= 1000:
           print("Datele nu corespund restricțiilor impuse.")
       else:
           lungime_maxima, pozitie_start = gaseste_secventa_maxima(vector)
           print("Datele sunt introduse corect.")
           print(lungime_maxima, pozitie_start)


</syntaxhighlight>

Explicație rezolvare

Funcția validate_input verifică dacă datele introduse de utilizator corespund cerințelor problemei, adică dacă numărul n este în intervalul [1, 1000], toate numerele citite sunt mai mici decât 1000 și vectorul conține cel puțin un element nul. Dacă datele sunt valide, funcția returnează True, altfel returnează False.

Funcția find_longest_sequence_of_zeros primește ca argument vectorul citit și returnează două numere: lungimea celei mai lungi secvențe de elemente nule din vector și poziția de început a acestei secvențe. Pentru a găsi aceste valori, funcția parcurge vectorul și numără lungimea fiecărei secvențe de elemente nule întâlnite. De fiecare dată când găsește o secvență de elemente nule mai lungă decât cea găsită anterior, funcția actualizează lungimea maximă și poziția de început a acestei secvențe.

În main, se citesc datele de intrare de la tastatură, se validează și se apelează funcția find_longest_sequence_of_zeros. Dacă datele introduse sunt valide, se afișează mesajul "Datele sunt introduse corect." și rezultatul returnat de funcția find_longest_sequence_of_zeros. În caz contrar, se afișează mesajul "Datele nu corespund restricțiilor impuse.".

Retrieved from "http://wiki.universitas.ro/index.php?title=0518_-_SecvZero&oldid=6323"