0519 - Secventa1: Difference between revisions

From Bitnami MediaWiki
Flaviu (talk | contribs)
No edit summary
Flaviu (talk | contribs)
No edit summary
Line 6: Line 6:
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.
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 ==  
== Date de ieșire ==  
Programul 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.
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 ==
== Restricţii şi precizări ==
* 1 ≤ m ≤ n ≤ 1000
* 1 ≤ m ≤ n ≤ 1000
Line 18: Line 19:
: 8 5 2 3 10 7
: 8 5 2 3 10 7
; Ieșire
; Ieșire
: Datele nu corespund restricțiilor impuse.
: 3
: 3


Line 25: Line 27:
# 0519 - Secventa1
# 0519 - Secventa1


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


def is_subsequence(n, x, m, y):
def is_subsequence(n, x, m, y):
Line 38: Line 41:
             return i + 1
             return i + 1
     return -1
     return -1
def read_input():
    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




def validate_output(result):
def validate_output(result):
     print(result) if result != -1 else print("NU")
     if result != -1:
        print(result)
    else:
        print("NU")




if __name__ == "__main__":
if __name__ == "__main__":
     n, x, m, y = read_input()
     n, x, m, y = read_input()
     result = is_subsequence(n, x, m, y)
     if n is not None and x is not None and m is not None and y is not None:
    validate_output(result)
        result = is_subsequence(n, x, m, y)
        validate_output(result)
 




Line 53: Line 76:
== Explicatie Rezolvare ==  
== Explicatie Rezolvare ==  


Funcția read_input citește datele de intrare de la tastatură și returnează valorile citite sub formă de tuple.
Desigur, cu placere!


Funcția is_subsequence primește cele patru variabile și parcurge vectorul x cu o fereastră de lungime m. Dacă fereastra curentă este identică cu vectorul y, atunci întoarce poziția de început a secvenței (i + 1). Dacă nu găsește nicio secvență, întoarce -1.
Î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 validate_output primește rezultatul întors de is_subsequence și afișează poziția găsită sau mesajul "NU" în caz contrar.
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.


În blocul if __name__ == "__main__":, apelăm funcțiile în ordinea potrivită pentru a rezolva problema.
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.

Revision as of 17:47, 27 April 2023

Sursa: 0519 - Secventa1


Cerinţa

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

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

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

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

Rezolvare

Rezolvare ver. 1

<syntaxhighlight lang="python" line>

  1. 0519 - Secventa1

def validate_input(n, x, m, 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):

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

def read_input():

   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


def validate_output(result):

   if result != -1:
       print(result)
   else:
       print("NU")


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)


</syntaxhighlight>

Explicatie Rezolvare

Desigur, cu placere!

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