1155 - Cautare Binara - Revision history

Andrada378: /* Rezolvare */

2024-01-05T10:33:07Z

Rezolvare

← Older revision		Revision as of 10:33, 5 January 2024
Line 31:		Line 31:
	== Rezolvare ==		== Rezolvare ==
	<syntaxhighlight lang="python">		<syntaxhighlight lang="python">
			def validate_input(n, a, m, b):
			# Verificare pentru n
			if not (1 <= n <= 25000):
			print("Valoarea lui n nu respectă restricțiile.")
			return False

			# Verificare pentru elementele vectorului a
			if any(not -1000000000 <= ai <= 1000000000 for ai in a):
			print("Elementele vectorului a depășesc limita de 1.000.000.000.")
			return False

			# Verificare pentru m
			if not (1 <= m <= 200000):
			print("Valoarea lui m nu respectă restricțiile.")
			return False

			# Verificare pentru elementele vectorului b
			if any(not -1000000000 <= bi <= 1000000000 for bi in b):
			print("Elementele vectorului b depășesc limita de 1.000.000.000.")
			return False

			return True
	def cautare_binara(arr, obiectiv):		def cautare_binara(arr, obiectiv):

Line 69:		Line 91:

	for elem in y:		for elem in y:

	if cautare_binara(x, elem):		if cautare_binara(x, elem):

Line 75:		Line 96:

	else:		else:

	rezultat.append(0)		rezultat.append(0)

Line 81:		Line 101:

	def main():		def main():

	rezultat = verifica_elementele()		rezultat = verifica_elementele()

	print(*rezultat)		print(*rezultat)

	if __name__ == "__main__":		if __name__ == "__main__":

	main()		main()
	</syntaxhighlight>		</syntaxhighlight>

Andrada378 at 14:17, 2 January 2024

2024-01-02T14:17:20Z

← Older revision		Revision as of 14:17, 2 January 2024
Line 1:		Line 1:
	~~Cerinta~~		== Cerința ==

	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.		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		== 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 cele m elemente ale lui y.		Programul citește de la tastatură numărul n, iar apoi cele n elemente ale vectorului x. Apoi și citește m și cele m elemente ale lui y.

	Date de ~~iesire~~		== Date de ieșire ==

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

	~~Restrictii~~ si ~~precizari~~		== Restricții si precizări ==

	~~1 ≤ n ≤ 25000~~

	~~1 ≤ m ≤ 200000~~

	~~elementele celor 2 vectori vor fi mai mici decât 1.000.000.000~~

	~~Exemplu~~		* 1 ≤ n ≤ 25000
			* 1 ≤ m ≤ 200000
			* elementele celor 2 vectori vor fi mai mici decât 1.000.000.000

	Intrare		=== Exemplu: ===
			'''Intrare'''

	7		7
Line 31:		Line 25:
	8 14 9 14 16 15 4 2		8 14 9 14 16 15 4 2

	~~Iesire~~		'''Ieșire'''

	0 1 1 1 0 0 0 1		0 1 1 1 0 0 0 1

	Rezolvare:		== Rezolvare ==
			<syntaxhighlight lang="python">
	def cautare_binara(arr, obiectiv):		def cautare_binara(arr, obiectiv):

	left, right = 0, len(arr) - 1 ~~#initializam 2 variabile , left va fi indicele de start iar~~		left, right = 0, len(arr) - 1

	~~#right indicele de final~~

	while left <= right:		while left <= right:

	mij = left + (right - left) // 2		mij = left + (right - left) // 2

	if arr[mij] == obiectiv: ~~#Verificam daca valoarea din mijloc este egala cu obiectivul,~~		if arr[mij] == obiectiv:

	~~#Daca da, inseamna ca am gasit elementul cautat si returnam True~~

	return True		return True

	elif arr[mij] < obiectiv:		elif arr[mij] < obiectiv:

	left = mij + 1		left = mij + 1

	else:		else:

	right = mij - 1		right = mij - 1

	return False		return False

	def verifica_elementele():		def verifica_elementele():

	n = int(input())		n = int(input())

	x = list(map(int, input().split()))		x = list(map(int, input().split()))

	m = int(input())		m = int(input())

	y = list(map(int, input().split()))		y = list(map(int, input().split()))

	rezultat = []		rezultat = []

	x.sort() ~~# Sortăm vectorul x pentru a folosi căutarea binară~~		x.sort()

	for elem in y:		for elem in y:

	if cautare_binara(x, elem):		if cautare_binara(x, elem):

	rezultat.append(1)		rezultat.append(1)

	else:		else:

	rezultat.append(0)		rezultat.append(0)

	return rezultat		return rezultat

	def main():		def main():

	rezultat = verifica_elementele()		rezultat = verifica_elementele()

	print(*rezultat)		print(*rezultat)

	if __name__ == "__main__":		if __name__ == "__main__":

	main()		main()
			</syntaxhighlight>

Andrada378: Pagină nouă: Cerinta 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 cele m elemente ale lui y. Date de iesire Programul va afișa pe ecran m valori 0 sau 1, separate prin exact un spațiu. A j-a valoare...

2023-12-15T16:04:48Z

Pagină nouă: Cerinta 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 cele m elemente ale lui y. Date de iesire Programul va afișa pe ecran m valori 0 sau 1, separate prin exact un spațiu. A j-a valoare...

New page

Cerinta

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 cele m elemente ale lui y.

Date de iesire

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.

Restrictii si precizari

1 ≤ n ≤ 25000

1 ≤ m ≤ 200000

elementele celor 2 vectori vor fi mai mici decât 1.000.000.000

Exemplu

Intrare

7

1 2 5 6 9 10 14

8

8 14 9 14 16 15 4 2

Iesire

0 1 1 1 0 0 0 1

Rezolvare:

def cautare_binara(arr, obiectiv):

left, right = 0, len(arr) - 1 #initializam 2 variabile , left va fi indicele de start iar

#right indicele de final

while left <= right:

mij = left + (right - left) // 2

if arr[mij] == obiectiv: #Verificam daca valoarea din mijloc este egala cu obiectivul,

#Daca da, inseamna ca am gasit elementul cautat si returnam True

return True

elif arr[mij] < obiectiv:

left = mij + 1

else:

right = mij - 1

return False

def verifica_elementele():

n = int(input())

x = list(map(int, input().split()))

m = int(input())

y = list(map(int, input().split()))

rezultat = []

x.sort() # Sortăm vectorul x pentru a folosi căutarea binară

for elem in y:

if cautare_binara(x, elem):

rezultat.append(1)

else:

rezultat.append(0)

return rezultat

def main():

rezultat = verifica_elementele()

print(*rezultat)

if __name__ == "__main__":

main()