0519 - Secventa1: Difference between revisions

From Bitnami MediaWiki
← Older edit
Flaviu (talk | contribs)
277 edits
No edit summary
Flaviu (talk | contribs)
277 edits
No edit summary
 
(One intermediate revision by the same user not shown)
Line 30: Line 30:
; Ieșire
; Ieșire
: Datele nu corespund restricțiilor impuse.
: Datele nu corespund restricțiilor impuse.
: 6
 


== Rezolvare ==  
== Rezolvare ==  
Line 37: Line 37:
# 0519 - Secventa1
# 0519 - Secventa1


def validate_input(n, x, m, y):
def find_sequence(x, y):
    if not (1 <= n <= 100000 and 1 <= m <= 100000):
        print("Datele nu corespund restricțiilor impuse.")
        return False
    if not all(1 <= xi <= 1000000 for xi in x) or not all(1 <= yi <= 1000000 for yi in y):
        print("Datele nu corespund restricțiilor impuse.")
        return False
    return True


def is_subsequence(n, x, m, y):
    n = len(x)
    m = len(y)
    if m > n:
        return -1
     for i in range(n - m + 1):
     for i in range(n - m + 1):
         if x[i:i + m] == y:
         if x[i:i+m] == y:
             return i + 1
             return i + 1
     return -1
     return -1


def read_input():
def validate_input(n, m):
    try:
        n = int(input("Introduceti numarul de elemente al vectorului x: "))
        x = list(map(int, input("Introduceti elementele vectorului x, separate prin spatiu: ").split()))
        m = int(input("Introduceti numarul de elemente al vectorului y: "))
        y = list(map(int, input("Introduceti elementele vectorului y, separate prin spatiu: ").split()))
        if not validate_input(n, x, m, y):
            print("Datele nu corespund restricțiilor impuse.")
            return None, None, None, None
        print("Datele sunt introduse corect.")
        return n, x, m, y
    except ValueError:
        print("Datele introduse trebuie sa fie numere intregi.")
        return None, None, None, None


    if not(1 <= m <= n <= 1000):
        return False
    return True


def validate_output(result):
if __name__ == '__main__':
     if result != -1:
     # Citim input-ul
        print(result)
    n = int(input())
     else:
     x = list(map(int, input().split()))
        print("NU")
     m = int(input())
 
     y = list(map(int, input().split()))
 
if __name__ == "__main__":
     n, x, m, y = read_input()
     if n is not None and x is not None and m is not None and y is not None:
        result = is_subsequence(n, x, m, y)
        validate_output(result)


    # Validam input-ul
    if not validate_input(n, m):
        print('Datele nu corespund restrictiilor impuse.')
        exit()


    # Gasim secventa si afisam raspunsul
    poz = find_sequence(x, y)
    if poz != -1:
        print('Datele sunt introduse corect.')
        print(poz)
    else:
        print('Datele sunt introduse corect.')
        print('NU')


</syntaxhighlight>
</syntaxhighlight>
== Explicatie Rezolvare ==  
== Explicatie Rezolvare ==  
   
   
Funcția validate_input verifică restricțiile impuse și returnează True dacă datele sunt valide, sau False în caz contrar.


În acest cod, funcția `read_input()` citeste valorile de intrare de la utilizator și le returnează într-o tuplă, în ordinea în care au fost citite.
Funcția find_subsequence caută secvența y în vectorul x și returnează poziția de început a secvenței sau -1 dacă secvența nu a fost găsită.
 
Funcția `is_subsequence(n, x, m, y)` primește 4 argumente, primele două fiind lungimea și elementele listei `x`, iar ultimele două fiind lungimea și elementele listei `y`. Funcția verifică dacă lista `y` este o subsecvență a listei `x` și returnează indexul primului element al primei apariții a listei `y` în lista `x` dacă da, sau `-1` în caz contrar.


Funcția `validate_output(result)` primește rezultatul obținut de la `is_subsequence()` și îl afișează în funcție de cerințele problemei, adică afișează indexul primului element al primei apariții a listei `y` în lista `x`, dacă aceasta este o subsecvență a listei `x`, sau afișează "NU" în caz contrar.
În funcția main citim datele de intrare și le trimitem la funcția de validare. Dacă datele sunt valide, afișăm mesajul "Datele sunt introduse corect." și apoi apelăm funcția de rezolvare pentru a găsi poziția de început a secvenței y în vectorul x. În caz contrar, afișăm mesajul "Datele nu corespund restricțiilor impuse."

Latest revision as of 19:43, 14 May 2023

Sursa: 0519 - Secventa1

Cerinţa[edit]

Se dă un vector x cu n elemente, numere naturale și un vector y cu m elemente, numere naturale. Să se verifice dacă vectorul y este secvență în vectorul x.

Date de intrare[edit]

Programul citește de la tastatură numărul n, iar apoi n numere naturale, elementele vectorului x, apoi numărul m, iar apoi m numere naturale, elementele vectorului y.

Date de ieșire[edit]

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 p, reprezentând poziția din vectorul x de unde începe secvența y, dacă y este secvență în x, respectiv mesajul NU dacă y nu este secvență în x, reprezentând valoarea cerută. În cazul contrar, se va afișa pe ecran: "Datele nu corespund restricțiilor impuse.".

Restricţii şi precizări[edit]

  • 1 ≤ m ≤ n ≤ 1000
  • elementele celor doi vectori vor fi indexate de la 1
  • dacă vectorul y este de mai multe ori secvență în x se va afișa poziția de început a primei apariții

Exemplu 1[edit]

Intrare
10
8 5 8 5 2 3 10 7 1 6
6
8 5 2 3 10 7
Ieșire
Datele sunt introduse corect.
3

Exemplu 2[edit]

Intrare
1
2 3 4 5 6 7 8 3 1 11 2
4
1 2 3 4 5 6
Ieșire
Datele nu corespund restricțiilor impuse.


Rezolvare[edit]

Rezolvare ver. 1[edit]

<syntaxhighlight lang="python" line>

  1. 0519 - Secventa1

def find_sequence(x, y): 

   n = len(x)
   m = len(y)
   if m > n:
       return -1
   for i in range(n - m + 1):
       if x[i:i+m] == y:
           return i + 1
   return -1

def validate_input(n, m): 

   if not(1 <= m <= n <= 1000):
       return False
   return True

if __name__ == '__main__': 

   # Citim input-ul
   n = int(input())
   x = list(map(int, input().split()))
   m = int(input())
   y = list(map(int, input().split()))

   # Validam input-ul
   if not validate_input(n, m):
       print('Datele nu corespund restrictiilor impuse.')
       exit()

   # Gasim secventa si afisam raspunsul
   poz = find_sequence(x, y)
   if poz != -1:
       print('Datele sunt introduse corect.')
       print(poz)
   else:
       print('Datele sunt introduse corect.')
       print('NU')

</syntaxhighlight>

Explicatie Rezolvare[edit]

Funcția validate_input verifică restricțiile impuse și returnează True dacă datele sunt valide, sau False în caz contrar.

Funcția find_subsequence caută secvența y în vectorul x și returnează poziția de început a secvenței sau -1 dacă secvența nu a fost găsită.

În funcția main citim datele de intrare și le trimitem la funcția de validare. Dacă datele sunt valide, afișăm mesajul "Datele sunt introduse corect." și apoi apelăm funcția de rezolvare pentru a găsi poziția de început a secvenței y în vectorul x. În caz contrar, afișăm mesajul "Datele nu corespund restricțiilor impuse."

Retrieved from "http://wiki.universitas.ro/index.php?title=0519_-_Secventa1&oldid=6400"