0519 - Secventa1: Diferență între versiuni
Fără descriere a modificării |
Fără descriere a modificării |
||
(Nu s-au afișat 3 versiuni intermediare efectuate de același utilizator) | |||
Linia 7: | Linia 7: | ||
== 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 | '''"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 == | == Restricţii şi precizări == | ||
* 1 ≤ m ≤ n ≤ 1000 | * 1 ≤ m ≤ n ≤ 1000 | ||
* elementele celor doi vectori vor fi indexate de la 1 | * 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 | * dacă vectorul y este de mai multe ori secvență în x se va afișa poziția de început a primei apariții | ||
== Exemplu == | == Exemplu 1 == | ||
; Intrare | ; Intrare | ||
: 10 | : 10 | ||
Linia 18: | Linia 18: | ||
: 6 | : 6 | ||
: 8 5 2 3 10 7 | : 8 5 2 3 10 7 | ||
; Ieșire | |||
: Datele sunt introduse corect. | |||
: 3 | |||
== Exemplu 2 == | |||
; Intrare | |||
: 1 | |||
: 2 3 4 5 6 7 8 3 1 11 2 | |||
: 4 | |||
: 1 2 3 4 5 6 | |||
; Ieșire | ; Ieșire | ||
: Datele nu corespund restricțiilor impuse. | : Datele nu corespund restricțiilor impuse. | ||
== Rezolvare == | == Rezolvare == | ||
Linia 27: | Linia 37: | ||
# 0519 - Secventa1 | # 0519 - Secventa1 | ||
def | def find_sequence(x, 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 | 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> | </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. | |||
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 | |||
Î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." |
Versiunea curentă din 14 mai 2023 19:43
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 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
- 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
- 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
- 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
Rezolvare ver. 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')
Explicatie Rezolvare
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."