0304 - Secvente: Difference between revisions

From Bitnami MediaWiki
Flaviu (talk | contribs)
No edit summary
Flaviu (talk | contribs)
No edit summary
Line 23: Line 23:
: 10 12 14
: 10 12 14
; Ieșire
; Ieșire
: Datele sunt introduse correct.
: secvente.out
: secvente.out
: Datele sunt introduse correct.
: 3
: 3
== Exemplu 2  ==
== Exemplu 2  ==
; Intrare
; Intrare
: secvente.in
: secvente.in
: 8
: ...
: 12 10 15 17 17
: 10 12 14
: 10 12 14
; Ieșire
; Ieșire
: Datele nu corespund restricțiilor impuse.
: secvente.out
: secvente.out
: Datele nu corespund restricțiilor impuse.
: Datele sunt introduse incorrect
: 9


== Rezolvare ==  
== Rezolvare ==  
Line 42: Line 41:
# 0304 - Secvente
# 0304 - Secvente


def citire_date():
def count_increasing_sequences(n, a):
    n = int(input())
     cnt = 0
    v = list(map(int, input().split()))
    return n, v
 
def secvente_crescatoare(n, v):
     numar_secvente = 0
     for i in range(n):
     for i in range(n):
         j = i + 1
         j = i
         while j < n and v[j] > v[j-1]:
         while j + 1 < n and a[j] < a[j + 1]:
             j += 1
             j += 1
         numar_secvente += j - i
         cnt += (j > i)
        i = j - 1
     return cnt
    return numar_secvente
 
def validare(n, v):
    if len(v) != n:
        return False
    for x in v:
        if x < 0 or x > 9999:
            return False
     return True
 
if __name__ == '__main__':
    n, v = citire_date()
    if validare(n, v):
        print("Datele sunt introduse corect.")
        print(secvente_crescatoare(n, v))
    else:
        print("Datele nu corespund restricțiilor impuse.")


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


</syntaxhighlight>
</syntaxhighlight>
== Explicatie Rezolvare ==
== Explicatie Rezolvare ==
Funcția citeste_date_intrare primește datele de intrare de la tastatură și le returnează sub forma unei liste.
Functia def count_increasing_sequences primeste 2 parametri:


Funcția numara_secvente_crescatoare primește lista de numere și numără secvențele maximale cu elemente ordonate crescător din șirul dat. Algoritmul este simplu: parcurgem lista și ținem minte lungimea maximă a unei secvențe cu elemente ordonate crescător și numărul de astfel de secvențe găsite până în acel moment. Când întâlnim un element mai mic decât cel precedent, înseamnă că secvența curentă s-a încheiat, verificăm dacă are lungimea maximă și actualizăm numărul de secvențe dacă e cazul. La final mai facem o verificare dacă ultima secvență a fost maximă.
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:


Funcția valideaza verifică dacă datele de ieșire sunt valide.
Inițializăm o variabilă cnt cu 0.
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 blocul if __name__ == "__main__": citim datele de intrare, apelăm funcția numara_secvente_crescatoare și afișăm rezultatul.
Î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.

Revision as of 22:09, 13 May 2023

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

Fişierul de ieşire secvente.out va conţine:

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.".

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.
secvente.out
Datele sunt introduse incorrect

Rezolvare

Rezolvare ver. 1

<syntaxhighlight lang="python" line>

  1. 0304 - Secvente

def count_increasing_sequences(n, a):

   cnt = 0
   for i in range(n):
       j = i
       while j + 1 < n and a[j] < a[j + 1]:
           j += 1
       cnt += (j > i)
   return cnt

if __name__ == "__main__":

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

</syntaxhighlight>

Explicatie Rezolvare

Functia def count_increasing_sequences primeste 2 parametri:

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. 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.