0304 - Secvente: Diferență între versiuni

De la Universitas MediaWiki
Fără descriere a modificării
 
(Nu s-au afișat 2 versiuni intermediare efectuate de un alt utilizator)
Linia 9: Linia 9:
== Date de ieșire ==  
== Date de ieșire ==  


Dacă datele sunt introduse corect, pe ecran se va afișa:  
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 numărul de secvenţe cu elementele ordonate crescător din şirul dat''', reprezentând valoarea cerută. În cazul contrar, se va afișa pe ecran: '''"Datele nu corespund restricțiilor impuse."'''.
'''"Datele sunt introduse corect."''', apoi fișierul secv.out conține ''' numărul C, reprezentând numărul de secvenţe cu elementele ordonate crescător din şirul dat''', reprezentând valoarea cerută. În cazul contrar, se va afișa pe ecran: '''"Datele nu corespund restricțiilor impuse."'''.


== Restricţii şi precizări ==
== Restricţii şi precizări ==
Linia 29: Linia 29:
; Intrare
; Intrare
: secvente.in
: secvente.in
: ...
:  
: 10 12 14
: 10 12 14
; Ieșire
; Ieșire
: Datele nu corespund restricțiilor impuse.
: Datele nu corespund restricțiilor impuse.
: secvente.out
 
: Datele sunt introduse incorrect


== Rezolvare ==  
== Rezolvare ==  
Linia 41: Linia 40:
# 0304 - Secvente
# 0304 - Secvente


def count_increasing_sequences(n, a):
def count_maximal_sequences(n, arr):
     cnt = 0
     sequences = 0
     for i in range(n):
     i = 0
         j = i
    while i < n:
         while j + 1 < n and a[j] < a[j + 1]:
         j = i + 1
         while j < n and arr[j] > arr[j-1]:
             j += 1
             j += 1
         cnt += (j > i)
         sequences += j - i
     return cnt
        i = j
    return sequences
 
def validate_input(n, arr):
    if not 1 <= n <= 1000:
        return False
    for x in arr:
        if not 1 <= x <= 9999:
            return False
     return True


if __name__ == "__main__":
if __name__ == "__main__":
     try:
     try:
         with open("secvente.in", "r") as f:
         with open("secvente.in", "r") as f_in:
             n = int(f.readline())
             n = int(f_in.readline().strip())
             a = []
             arr = []
             for line in f:
             for _ in range(n):
                 a += list(map(int, line.strip().split()))
                 arr += list(map(int, f_in.readline().strip().split()))
            if len(a) != n:
        if validate_input(n, arr):
                print("Datele nu corespund restricțiilor impuse.")
            with open("secvente.out", "w") as f_out:
            else:
                f_out.write(str(count_maximal_sequences(n, arr)))
                 print("Datele sunt introduse corect.")
                 print("Datele sunt introduse corect.")
                with open("secvente.out", "w") as g:
        else:
                    g.write(str(count_increasing_sequences(n, a)))
            print("Datele nu corespund restricțiilor impuse.")
     except FileNotFoundError:
     except FileNotFoundError:
         print("Fisierul secvente.in nu exista.")  
         print("Nu exista fisierul de intrare!")  
 


</syntaxhighlight>
</syntaxhighlight>
== Explicatie Rezolvare ==
== Explicatie Rezolvare ==
Functia def count_increasing_sequences primeste 2 parametri:
Functia count_maximal_sequences() calculeaza numarul de secvente maximale cu elementele ordonate crescator din sirul de intrare. Folosim doua variabile, i si j, pentru a parcurge sirul. Variabila i marcheaza inceputul unei secvente, iar variabila j cauta finalul secventei. Atunci cand gasim finalul secventei, adaugam la numarul de secvente maximale lungimea secventei curente, adica j-i. Apoi setam variabila i la valoarea lui j pentru a cauta urmatoarea secventa.
 
n: reprezintă numărul de elemente din lista a
a: lista de n elemente
Funcția utilizează o metodă iterativă pentru a număra secvențele maximale în care elementele sunt ordonate crescător. Aceasta lucrează astfel:


Inițializăm o variabilă cnt cu 0.
Functia validate_input() valideaza datele de intrare conform restrictiilor problemei. Returneaza True daca datele sunt corecte si False in caz contrar.
Parcurgem lista a utilizând un iterator i în intervalul [0, n-1]
Inițializăm un alt iterator j cu valoarea lui i
Utilizând un ciclu while verificăm dacă următorul element din lista a (a[j+1]) este mai mare decât elementul curent (a[j]). Dacă da, incrementăm iteratorul j și continuăm să verificăm dacă elementele sunt în ordine crescătoare.
Dacă j este mai mare decât i, adăugăm 1 la valoarea lui cnt. Acest lucru se face deoarece avem o secvență maximă crescătoare în această secvență, începând de la poziția i și terminând la poziția j.
La final, funcția returnează valoarea lui cnt, care reprezintă numărul de secvențe maximale crescătoare găsite în lista a.


În ceea ce privește blocul if __name__ == "__main__":, acesta verifică dacă fișierul de intrare există și, dacă da, citesc datele din fișierul de intrare secvente.in și le pasează la funcția count_increasing_sequences(). Funcția apoi scrie rezultatul în fișierul de ieșire secvente.out, împreună cu un mesaj corespunzător în cazul în care datele sunt sau nu sunt introduse corect.
In functia principala if __name__ == "__main__": citim datele de intrare din fisierul secvente.in. Apoi verificam daca datele sunt valide folosind functia validate_input(). Daca datele sunt valide, apelam functia count_maximal_sequences() pentru a calcula numarul de secvente maximale si scriem rezultatul in fisierul secvente.out. Afisam mesajul "Datele sunt introduse corect." daca totul a functionat bine. In caz contrar, afisam mesajul "Datele nu corespund restricțiilor impuse." sau "Nu exista fisierul de intrare!" daca fisierul de intrare nu exista.

Versiunea curentă din 14 mai 2023 20:44

Sursa: 0304 - Secvente

Cerinţa

Se dă un şir format din n elemente, numere naturale. Determinaţi câte secvenţe maximale cu elementele ordonate crescător conţine şirul.

Date de intrare

Fişierul de intrare secvente.in conţine pe prima linie numărul n; urmează cele n elemente ale vectorului, dispuse pe mai multe linii şi separate prin spaţii.

Date de ieșire

Dacă datele sunt introduse corect, pe ecran se va afișa: "Datele sunt introduse corect.", apoi fișierul secv.out conține numărul C, reprezentând numărul de secvenţe cu elementele ordonate crescător din şirul dat, 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
  • elementele şirului vor avea cel mult 4 cifre
  • o secvență cu elemente ordonate crescător este maximală dacă adăugând la secvență încă un element ea nu mai are elementele ordonate crescător

Exemplu 1

Intrare
secvente.in
8
12 10 15 17 17
10 12 14
Ieșire
Datele sunt introduse correct.
secvente.out
3

Exemplu 2

Intrare
secvente.in
10 12 14
Ieșire
Datele nu corespund restricțiilor impuse.


Rezolvare

Rezolvare ver. 1

# 0304 - Secvente

def count_maximal_sequences(n, arr):
    sequences = 0
    i = 0
    while i < n:
        j = i + 1
        while j < n and arr[j] > arr[j-1]:
            j += 1
        sequences += j - i
        i = j
    return sequences

def validate_input(n, arr):
    if not 1 <= n <= 1000:
        return False
    for x in arr:
        if not 1 <= x <= 9999:
            return False
    return True

if __name__ == "__main__":
    try:
        with open("secvente.in", "r") as f_in:
            n = int(f_in.readline().strip())
            arr = []
            for _ in range(n):
                arr += list(map(int, f_in.readline().strip().split()))
        if validate_input(n, arr):
            with open("secvente.out", "w") as f_out:
                f_out.write(str(count_maximal_sequences(n, arr)))
                print("Datele sunt introduse corect.")
        else:
            print("Datele nu corespund restricțiilor impuse.")
    except FileNotFoundError:
        print("Nu exista fisierul de intrare!")

Explicatie Rezolvare

Functia count_maximal_sequences() calculeaza numarul de secvente maximale cu elementele ordonate crescator din sirul de intrare. Folosim doua variabile, i si j, pentru a parcurge sirul. Variabila i marcheaza inceputul unei secvente, iar variabila j cauta finalul secventei. Atunci cand gasim finalul secventei, adaugam la numarul de secvente maximale lungimea secventei curente, adica j-i. Apoi setam variabila i la valoarea lui j pentru a cauta urmatoarea secventa.

Functia validate_input() valideaza datele de intrare conform restrictiilor problemei. Returneaza True daca datele sunt corecte si False in caz contrar.

In functia principala if __name__ == "__main__": citim datele de intrare din fisierul secvente.in. Apoi verificam daca datele sunt valide folosind functia validate_input(). Daca datele sunt valide, apelam functia count_maximal_sequences() pentru a calcula numarul de secvente maximale si scriem rezultatul in fisierul secvente.out. Afisam mesajul "Datele sunt introduse corect." daca totul a functionat bine. In caz contrar, afisam mesajul "Datele nu corespund restricțiilor impuse." sau "Nu exista fisierul de intrare!" daca fisierul de intrare nu exista.

Adus de la „http://wiki.universitas.ro/index.php?title=0304_-_Secvente&oldid=6453”