1846 - OrdonareSecvF REC - Revision history

Catalin Moje at 21:59, 14 May 2023

2023-05-14T21:59:44Z

← Older revision		Revision as of 21:59, 14 May 2023
Line 10:		Line 10:

	==Restricţii şi precizări==		==Restricţii şi precizări==
	0 < n <= 1000		*0 < n <= 1000
	numele subprogramului cerut este ordonare		*numele subprogramului cerut este ordonare
	parametrii sunt, în această ordine: a, n, st, dr		*parametrii sunt, în această ordine: a, n, st, dr
	0≤st≤dr<n		*0≤st≤dr<n
	elementele tabloului a sunt indexate de la zero		*elementele tabloului a sunt indexate de la zero
	se recomandă realizarea unei soluții recursive		*se recomandă realizarea unei soluții recursive

	==Exemplu==		==Exemplu==
	===Exemplu 1===		===Exemplu 1===
	~~<syntaxhighlight lang="python" line>~~		:Intrare:
	Introduceti numarul de elemente: 6		;Introduceti numarul de elemente: 6
	Introduceti cele 6 numere separate prin spatiu: 63 273 9 83 93 123		;Introduceti cele 6 numere separate prin spatiu: 63 273 9 83 93 123
	Introduceti indexul stanga: 1		;Introduceti indexul stanga: 1
	Introduceti indexul dreapta: 3		;Introduceti indexul dreapta: 3
			:Iesire:
	[63, 9, 83, 273, 93, 123]		[63, 9, 83, 273, 93, 123]
	~~</syntaxhighlight>~~
	===Exemplu 2===		===Exemplu 2===
	~~<syntaxhighlight lang="python" line>~~		:Intrare:
	Introduceti numarul de elemente: 1001		;Introduceti numarul de elemente: 1001
	Datele de intrare nu corespund cerinței.		:Iesire:
	~~</syntaxhighlight>~~		;Datele de intrare nu corespund cerinței.

	==Important==		==Important==
	Soluţia propusă va conţine doar definiţia subprogramului cerut. Prezenţa în soluţie a altor instrucţiuni poate duce erori de compilare sau de execuţie care vor avea ca efect depunctarea soluţiei.		Soluţia propusă va conţine doar definiţia subprogramului cerut. Prezenţa în soluţie a altor instrucţiuni poate duce erori de compilare sau de execuţie care vor avea ca efect depunctarea soluţiei.

	==Rezolvare==		==Rezolvare==
	<syntaxhighlight lang="python" line>		<syntaxhighlight lang="python" line="1">
	def validare_numar(numar):		def validare_numar(numar):
	if not numar.isdigit():		if not numar.isdigit():

Catalin Moje at 16:24, 4 April 2023

2023-04-04T16:24:03Z

Show changes

Catalin Moje at 11:31, 25 March 2023

2023-03-25T11:31:11Z

← Older revision		Revision as of 11:31, 25 March 2023
Line 20:		Line 20:
	==Exemplu==		==Exemplu==
	Dacă n=6, a=(63,273,9,83,93,123), st=1 și dr=3 după apelul subprogramului tabloul a devine (63,9,83,273,93,123).		Dacă n=6, a=(63,273,9,83,93,123), st=1 și dr=3 după apelul subprogramului tabloul a devine (63,9,83,273,93,123).

			==Important==
			Soluţia propusă va conţine doar definiţia subprogramului cerut. Prezenţa în soluţie a altor instrucţiuni poate duce erori de compilare sau de execuţie care vor avea ca efect depunctarea soluţiei.

	==Rezolvare==		==Rezolvare==

	def ordonare(a, n, st, dr):		Funcția de validare
	if st >= dr:		Pentru a valida datele de intrare vom verifica dacă valorile sunt numere naturale mai mici decât 1.000.000.000 și dacă valorile indiciilor st și dr sunt în intervalul [0, n), unde n este lungimea tabloului a.
	~~return~~

			def validare(n: int, st: int, dr: int) -> bool:
			if not (0 < n <= 1000):
			return False
			if not (0 <= st <= dr < n):
			return False
			return True
			Funcția de rezolvare
			Pentru a ordona crescător elementele tabloului a cu indici între st și dr, inclusiv aceștia, vom folosi o implementare a algoritmului quicksort.


			def ordonare(a: List[int], n: int, st: int, dr: int) -> None:
			if st < dr:
			pivot = partition(a, st, dr)
			ordonare(a, n, st, pivot - 1)
			ordonare(a, n, pivot + 1, dr)


			def partition(a: List[int], st: int, dr: int) -> int:
	pivot = a[dr]		pivot = a[dr]
	i = st - 1		i = st - 1
	for j in range(st, dr):		for j in range(st, dr):
	if a[j] < pivot:		if a[j] <= pivot:
	i += 1		i += 1
	a[i], a[j] = a[j], a[i]		a[i], a[j] = a[j], a[i]
	i += 1		a[i + 1], a[dr] = a[dr], a[i + 1]
	~~a[i~~], a[dr] = a[dr], a[i]		return i + 1
	~~ordonare(~~a, n, st, ~~i - 1)~~		Funcția partition este implementarea unei etape a algoritmului quicksort, care selectează un element pivot și împarte tabloul în două subtablouri, astfel încât elementele mai mici decât pivot sunt înaintea sa, iar cele mai mari sunt după. Funcția întoarce indicele poziției pivot după ce tabloul a fost partitionat.
	ordonare(a, n, ~~i + 1~~, ~~dr)~~
	~~Pentru a testa subprogramul, se poate apela în felul următor~~:		Funcția ordonare este implementarea recursivă a algoritmului quicksort pentru a ordona crescător elementele tabloului a cu indici între st și dr, inclusiv aceștia. Pe baza valorii pivotului returnate de partition, subtabloul din stânga pivotului și cel din dreapta pivotului sunt ordonate recursiv cu apeluri recursive la ordonare.
	n = int(input(~~"Introduceti numarul de elemente: "~~))
	a = []		Funcția main
	~~for i in range~~(~~n):~~		Funcția main va citi datele de intrare, le va valida și, în cazul în care acestea sunt corecte, va apela funcția ordonare pentru a ordona elementele tabloului a. Dacă datele de intrare nu corespund restricțiilor impuse, va afișa un mesaj corespunzător.
	~~a.append~~(int(~~input~~(~~f"Introduceti elementul {i}: "~~)))
	st = int(~~input~~(~~"Introduceti indicele st: "~~))
	dr ~~= int(input~~("~~Introduceti indicele dr:~~ "))		def main() -> None:
	~~if 0 <= st <= dr < n:~~		n = int(input())
			a = list(map(int, input().split()))
			st, dr = map(int, input().split())

			if not validare(n, st, dr):
			print("Datele de intrare nu corespund restricțiilor impuse.")
			return

	ordonare(a, n, st, dr)		ordonare(a, n, st, dr)
	~~print(a)~~		print("Datele de intrare co
	~~else:~~
	print("Datele de intrare ~~nu corespund restricțiilor impuse.")~~

Catalin Moje: Pagină nouă: ==Cerinţa== Scrieţi definiția completă a subprogramului recursiv ordonare care are 4 parametri: a, prin care primeşte un tablou unidimensional cu maximum 1000 de numere naturale mai mici decât 1.000.000.000 și n, numărul efectiv de elemente ale tabloului și doi indici st dr. Subprogramul ordonează crescător elementele tabloului a cu indici între st și dr, inclusiv aceștia,fără a modifica celelalte elemente ale tabloului. ==Date de intrare== Se va introduce de...

2023-03-21T22:07:57Z

Pagină nouă: ==Cerinţa== Scrieţi definiția completă a subprogramului recursiv ordonare care are 4 parametri: a, prin care primeşte un tablou unidimensional cu maximum 1000 de numere naturale mai mici decât 1.000.000.000 și n, numărul efectiv de elemente ale tabloului și doi indici st dr. Subprogramul ordonează crescător elementele tabloului a cu indici între st și dr, inclusiv aceștia,fără a modifica celelalte elemente ale tabloului. ==Date de intrare== Se va introduce de...

New page

==Cerinţa==
Scrieţi definiția completă a subprogramului recursiv ordonare care are 4 parametri: a, prin care primeşte un tablou unidimensional cu maximum 1000 de numere naturale mai mici decât 1.000.000.000 și n, numărul efectiv de elemente ale tabloului și doi indici st dr.
Subprogramul ordonează crescător elementele tabloului a cu indici între st și dr, inclusiv aceștia,fără a modifica celelalte elemente ale tabloului.

==Date de intrare==
Se va introduce de la tastatură un număr natural care va fi transmis ca perimetru

==Date de ieșire==
Pe ecran se va afișa mesajul: "Datele de intrare corespund restricțiilor impuse."
În cazul în care datele introduse de la tastatură nu îndeplinesc cerințele enunțate, pe ecran se va afișa mesajul "Datele de intrare nu corespund restricțiilor impuse.".

==Restricţii şi precizări==
0 < n <= 1000
numele subprogramului cerut este ordonare
parametrii sunt, în această ordine: a, n, st, dr
0≤st≤dr<n
elementele tabloului a sunt indexate de la zero
se recomandă realizarea unei soluții recursive

==Exemplu==
Dacă n=6, a=(63,273,9,83,93,123), st=1 și dr=3 după apelul subprogramului tabloul a devine (63,9,83,273,93,123).

==Rezolvare==

def ordonare(a, n, st, dr):
if st >= dr:
return
pivot = a[dr]
i = st - 1
for j in range(st, dr):
if a[j] < pivot:
i += 1
a[i], a[j] = a[j], a[i]
i += 1
a[i], a[dr] = a[dr], a[i]
ordonare(a, n, st, i - 1)
ordonare(a, n, i + 1, dr)
Pentru a testa subprogramul, se poate apela în felul următor:
n = int(input("Introduceti numarul de elemente: "))
a = []
for i in range(n):
a.append(int(input(f"Introduceti elementul {i}: ")))
st = int(input("Introduceti indicele st: "))
dr = int(input("Introduceti indicele dr: "))
if 0 <= st <= dr < n:
ordonare(a, n, st, dr)
print(a)
else:
print("Datele de intrare nu corespund restricțiilor impuse.")