0508 - Cautare Binara
De la Universitas MediaWiki
Cerință
Se dă un vector x cu n elemente numere naturale, ordonate crescător, și un vector y cu m elemente, de asemenea numere naturale. Verificați pentru fiecare element al vectorului y dacă apare în x.
Date de intrare
Programul citește de la tastatură numărul n, iar apoi cele n elemente ale vectorului x. Apoi și citește m și celem m elemente ale lui y.
Date de ieșire
Dacă datele sunt introduse corect, pe ecran se va afișa: "Datele de intrare corespund restricțiilor impuse." Programul va afișa pe ecran m valori 0 sau 1, separate prin exact un spațiu. A j-a valoare afișată este 1, dacă al j-lea element al șirului y apare în x, respectiv 0 în caz contrar. În caz contrar, se va afișa pe ecran: "Datele de intrare nu corespund restricțiilor impuse."
Restricții de precizări
- 1 ⩽ n ⩽ 25000
- 1 ⩽ m ⩽ 25000
- elementele celor 2 vectori vor fi mai mici decât 10000
Exemplul 1
- Intrare
- 5
- 2 4 6 8 10
- 3
- 4 7 9
- Ieșire
- Datele introduse corespund restricțiilor impuse.
- 1 0 0
Exemplul 2
- Intrare
- 3
- 1 5 7
- 4
- 3 8 1 0
- Ieșire
- Datele introduse corespund restricțiilor impuse.
- 0 0 0 0
Rezolvare ver. 1
def validare(n, x, m, y):
return str(n).isdigit() and 1 <= int(n) <= 25000 and str(m).isdigit() and 1 <= int(m) <= 2000000
# Verifică dacă n și m sunt cifre și se află în intervalul specificat
def element_in_vector(x, y):
result = [] # Lista în care se vor stoca rezultatele verificării
j = 0 # Variabilă utilizată pentru a parcurge vectorul x
for i in range(len(y)): # Se parcurge vectorul y
while j < len(x) and x[j] < y[i]: # Se parcurge vectorul x până la valoarea din y[i]
j += 1
if j < len(x) and x[j] == y[i]: # Dacă s-a găsit o valoare din y în x, se adaugă 1 în result
result.append(1)
else: # Altfel, se adaugă 0 în result
result.append(0)
return result # Se returnează lista cu rezultatele verificării
if __name__ == "__main__":
# Citirea vectorului x
n = int(input("Introduceți numărul de elemente în vectorul x: "))
x = []
for i in range(n):
x.append(int(input(f"Introduceți elementul {i + 1} din x: ")))
# Citirea vectorului y
m = int(input("Introduceți numărul de elemente în vectorul y: "))
y = []
for i in range(m):
y.append(int(input(f"Introduceți elementul {i + 1} din y: ")))
if validare(n, x, m, y):
print("Datele introduse corespund restricțiilor impuse.")
# Verificarea elementelor din y în x
result = element_in_vector(x, y)
# Afișarea rezultatului
print("Rezultatul verificării:")
print(*result, sep=" ")
else:
print("Datele introduse nu corespund restricțiilor impuse.")