0519 - Secventa1: Diferență între versiuni

De la Universitas MediaWiki
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 c''', reprezentând valoarea cerută. În cazul contrar, se va afișa pe ecran: '''"Datele nu corespund restricțiilor impuse."'''.
'''"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.
: 3
 


== Rezolvare ==  
== Rezolvare ==  
Linia 27: Linia 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.


Desigur, cu placere!
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 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.
Î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."