1154 - Cautare Div Imp - Revision history

Andrada378: /* Rezolvare */

2024-01-05T10:13:32Z

Rezolvare

@@ Line 38: / Line 38: @@
 def main():
      n = int(input())
      a = list(map(int, input().split()))
      m = int(input())
      b = list(map(int, input().split()))
      for i in range(1, m + 1):

Andrada378 at 14:37, 2 January 2024

2024-01-02T14:37:57Z

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

	Se dă un vector x cu n elemente numere naturale, și un vector y cu m elemente, de asemenea numere naturale. Folosind metoda Divide et Impera, verificați pentru fiecare element al vectorului y dacă apare în x.		Se dă un vector x cu n elemente numere naturale, și un vector y cu m elemente, de asemenea numere naturale. Folosind metoda Divide et Impera, 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,m ≤ 1000		* 1 ≤ n,m ≤ 1000
			* elementele celor doi vectori vor fi mai mici decât 1.000.000.000

	~~elementele celor doi vectori vor fi mai mici decât 1.000.000.000~~		=== Exemplu: ===
			'''Intrare'''
	Exemplu

	Intrare

	7		7
Line 29:		Line 24:
	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

	~~''<u>~~Rezolvare</u>''		== Rezolvare ==
			<syntaxhighlight lang="python">
	def ~~cautare_divide_et_impera~~(x, y):		def gasesc(elem, a, st, dr):
			if st == dr:
	~~rezultat~~ = []		return a[st - 1] == elem
			else:
	~~for elem in y~~:		mij = (st + dr) // 2
			return gasesc(elem, a, st, mij) or gasesc(elem, a, mij + 1, dr)
	~~rezultat.append(cauta_element(x, elem))~~

	return ~~rezultat~~

	~~def cauta_element(x, elem):~~

	~~stanga, dreapta = 0, len(x)~~ - 1

	~~while stanga <= dreapta~~:

	~~mijloc~~ = (~~stanga~~ + ~~dreapta~~) // 2

	~~if x[mijloc] ==~~ elem:

	~~return 1~~

	~~elif x[mijloc] <~~ elem:

	~~stanga = mijloc~~ + 1

	~~else:~~

	~~dreapta = mijloc - 1~~

	~~return 0~~

	def main():		def main():
			n = int(input())
			a = list(map(int, input().split()))
			m = int(input())
			b = list(map(int, input().split()))

	~~n = int~~(~~input("Introduceți lungimea vectorului x~~: ~~"))~~		for i in range(1, m + 1):
			if gasesc(b[i - 1], a, 1, n):
	~~x = list~~(~~map(int~~, ~~input("Introduceți elementele vectorului x separate prin spațiu: ").split()~~))		print(1, end=' ')
			else:
	~~m = int(input("Introduceți lungimea vectorului y~~: ~~"))~~		print(0, end=' ')

	~~y = list~~(~~map(int~~, ~~input("Introduceți elementele vectorului y separate prin spațiu: ").split()))~~

	~~rezultat~~ = ~~cautare_divide_et_impera(sorted(x), y~~)

	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, și un vector y cu m elemente, de asemenea numere naturale. Folosind metoda Divide et Impera, 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....

2023-12-15T16:38:19Z

Pagină nouă: Cerinta Se dă un vector x cu n elemente numere naturale, și un vector y cu m elemente, de asemenea numere naturale. Folosind metoda Divide et Impera, 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....

New page

Cerinta

Se dă un vector x cu n elemente numere naturale, și un vector y cu m elemente, de asemenea numere naturale. Folosind metoda Divide et Impera, 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,m ≤ 1000

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

Exemplu

Intrare

7

9 6 5 14 2 1 10

8

8 14 9 14 16 15 4 2

Iesire

0 1 1 1 0 0 0 1

''<u>Rezolvare</u>''

def cautare_divide_et_impera(x, y):

rezultat = []

for elem in y:

rezultat.append(cauta_element(x, elem))

return rezultat

def cauta_element(x, elem):

stanga, dreapta = 0, len(x) - 1

while stanga <= dreapta:

mijloc = (stanga + dreapta) // 2

if x[mijloc] == elem:

return 1

elif x[mijloc] < elem:

stanga = mijloc + 1

else:

dreapta = mijloc - 1

return 0

def main():

n = int(input("Introduceți lungimea vectorului x: "))

x = list(map(int, input("Introduceți elementele vectorului x separate prin spațiu: ").split()))

m = int(input("Introduceți lungimea vectorului y: "))

y = list(map(int, input("Introduceți elementele vectorului y separate prin spațiu: ").split()))

rezultat = cautare_divide_et_impera(sorted(x), y)

print(*rezultat)

if __name__ == "__main__":

main()