0519 - Secventa1: Diferență între versiuni
Fără descriere a modificării |
Fără descriere a modificării |
||
Linia 75: | Linia 75: | ||
</syntaxhighlight> | </syntaxhighlight> | ||
== Explicatie Rezolvare == | == Explicatie Rezolvare == | ||
Î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. | Î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. |
Versiunea de la data 28 aprilie 2023 20:24
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
# 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)
Explicatie Rezolvare
Î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.