2427 - Sir 10 - Revision history

Sinn Erich: /* Rezolvare */

2023-04-29T08:43:02Z

Rezolvare

← Older revision		Revision as of 08:43, 29 April 2023
Line 66:		Line 66:
	return False		return False
	return True		return True


			def has_property(sir):
			d = sir[1] - sir[0]
			for i in range(2, len(sir)):
			if sir[i] - sir[i - 1] != d:
			return False
			return True


			def backtracking(sir, pozitie):
			global nr_siruri
			if len(sir) >= nr_termeni:
			if has_property(sir):
			nr_siruri += 1
			for i in range(pozitie + 1, n + 1):
			sir.append(i)
			backtracking(sir, i)
			sir.pop()


Line 75:		Line 94:
	if not has_valid_input(n, nr_termeni):		if not has_valid_input(n, nr_termeni):
	exit()		exit()


	~~def has_property(sir):~~
	~~d = sir[1] - sir[0]~~
	~~for i in range(2, len(sir)):~~
	~~if sir[i] - sir[i - 1] != d:~~
	~~return False~~
	~~return True~~


	~~def backtracking(sir, pozitie):~~
	~~global nr_siruri~~
	~~if len(sir) >= nr_termeni:~~
	~~if has_property(sir):~~
	~~nr_siruri += 1~~
	~~for i in range(pozitie + 1, n + 1):~~
	~~sir.append(i)~~
	~~backtracking(sir, i)~~
	~~sir.pop()~~


	backtracking([], 0)		backtracking([], 0)
	print("Datele sunt introduse corect.")		print("Datele sunt introduse corect.")
	print(nr_siruri)		print(nr_siruri)

	</syntaxhighlight>		</syntaxhighlight>

	'''Explicatie cod:'''		'''Explicatie cod:'''

	~~Această parte~~ de ~~cod definește o funcție numită has_valid_input~~ care ~~primește două argumente, n și k. Această funcție este folosită pentru a valida intrarea utilizatorului~~ și ~~pentru a se asigura că valorile n~~ și ~~k respectă restricțiile de la 3 la 20000~~. ~~Dacă nu sunt respectate, funcția va afișa~~ un ~~mesaj~~ de ~~eroare și va returna valoarea False. Dacă valorile sunt valabile~~, ~~funcția va returna valoarea True~~.		Acest program calculează numărul de șiruri aritmetice de lungime fixă și dimensiune n, care încep cu un element oarecare și au cel puțin trei elemente și diferența constantă între oricare două elemente consecutive. Programul utilizează un algoritm de backtracking pentru a genera toate șirurile posibile, verificând dacă acestea au proprietatea cerută.

	~~În blocul principal de cod~~, ~~programul întâi citește de la tastatură valoarea~~ n. ~~Apoi~~, ~~variabila k este inițializată cu 3~~ și ~~variabila nr_siruri este inițializată cu 0~~.		Funcția has_valid_input(n, nr_termeni) verifică dacă inputul dat este valid, adică dacă n și nr_termeni se încadrează într-un interval specificat. În caz contrar, se afișează un mesaj de eroare și se returnează False.

	~~Apoi, se~~ verifică dacă ~~valorile de intrare sunt valide~~, ~~apelând~~ funcția ~~has_valid_input~~. Dacă funcția returnează False~~, programul se oprește prin apelul exit()~~.		Funcția has_property(sir) verifică dacă un șir dat are proprietatea cerută (adică diferența dintre oricare două elemente consecutive este constantă). Dacă această proprietate este îndeplinită, funcția returnează True. Dacă nu, funcția returnează False.

	~~Următoarele două funcții, has_property și~~ backtracking, ~~sunt definite în blocul principal~~ de ~~cod~~. ~~Funcția has_property~~ primește ~~un șir de numere~~ și ~~verifică dacă acesta~~ are proprietatea ~~de a avea diferențe constante între elementele consecutive~~. ~~Funcția backtracking generează~~ toate combinațiile posibile ~~de șiruri și le verifică folosind~~ funcția ~~has_property. Dacă un șir verifică condiția~~, ~~numărul de șiruri găsite este incrementat~~.		Funcția backtracking(sir, pozitie) utilizează un algoritm de backtracking pentru a genera toate șirurile posibile care îndeplinesc cerințele. Aceasta primește ca argumente sir, care reprezintă șirul curent, și pozitie, care reprezintă poziția curentă în șirul n. Dacă șirul sir are cel puțin nr_termeni elemente și îndeplinește proprietatea cerută, se incrementează nr_siruri. Altfel, se explorează toate combinațiile posibile ale elementelor următoare în șirul n cu ajutorul unei bucle for. În continuare, se adaugă elementul curent în sir, se apelează recursiv funcția backtracking() pentru a explora toate posibilitățile ulterioare, se scoate ultimul element adăugat din sir și se continuă cu următoarea iterație a buclei.

	În ~~cele din urmă~~, ~~programul afișează~~ numărul de șiruri ~~găsite~~.		În blocul if __name__ == '__main__': se citesc datele de intrare n și se inițializează variabilele nr_termeni și nr_siruri. Apoi, se verifică dacă datele introduse sunt valide, utilizând funcția has_valid_input(). Dacă inputul este valid, se apelează funcția backtracking() pentru a calcula numărul de șiruri cerute și se afișează rezultatul.

Sinn Erich: /* Cerinţa */

2023-04-27T22:42:16Z

Cerinţa

← Older revision		Revision as of 22:42, 27 April 2023
Line 1:		Line 1:
	Sursa: [https://www.pbinfo.ro/probleme/4273/prodpp]		Sursa: [https://www.pbinfo.ro/probleme/4273/prodpp]
	== Cerinţa ==		== Cerinţa ==
	Gigel se distrează construind şiruri crescătoare de numere din mulţimea '''{1,2,…,n}'''. La un moment dat observă că unele şiruri, de cel puţin k'''nr_termeni''' '''(k ≥ 3)''', au o proprietate mai aparte: diferența dintre doi termeni consecutivi este constantă. Iată câteva exemple de astfel de şiruri pentru '''n ≥ 22''':		Gigel se distrează construind şiruri crescătoare de numere din mulţimea '''{1,2,…,n}'''. La un moment dat observă că unele şiruri, de cel puţin k '''nr_termeni''' '''(k ≥ 3)''', au o proprietate mai aparte: diferența dintre doi termeni consecutivi este constantă. Iată câteva exemple de astfel de şiruri pentru '''n ≥ 22''':

	2, 3, 4		2, 3, 4

Sinn Erich: /* Cerinţa */

2023-04-27T22:42:07Z

Cerinţa

← Older revision		Revision as of 22:42, 27 April 2023
Line 1:		Line 1:
	Sursa: [https://www.pbinfo.ro/probleme/4273/prodpp]		Sursa: [https://www.pbinfo.ro/probleme/4273/prodpp]
	== Cerinţa ==		== Cerinţa ==
	Gigel se distrează construind şiruri crescătoare de numere din mulţimea '''{1,2,…,n}'''. La un moment dat observă că unele şiruri, de cel puţin '''k''' ~~termeni~~ '''(k ≥ 3)''', au o proprietate mai aparte: diferența dintre doi termeni consecutivi este constantă. Iată câteva exemple de astfel de şiruri pentru '''n ≥ 22''':		Gigel se distrează construind şiruri crescătoare de numere din mulţimea '''{1,2,…,n}'''. La un moment dat observă că unele şiruri, de cel puţin k'''nr_termeni''' '''(k ≥ 3)''', au o proprietate mai aparte: diferența dintre doi termeni consecutivi este constantă. Iată câteva exemple de astfel de şiruri pentru '''n ≥ 22''':

	2, 3, 4		2, 3, 4

Sinn Erich: /* Rezolvare */

2023-04-27T22:41:43Z

Rezolvare

← Older revision		Revision as of 22:41, 27 April 2023
Line 58:		Line 58:
	<syntaxhighlight lang="python" line>		<syntaxhighlight lang="python" line>
	#2427		#2427
	def has_valid_input(n, k):		def has_valid_input(n, nr_termeni):
	if not (3 <= n <= 20000):		if not (3 <= n <= 20000):
	print("Datele nu corespund restricțiilor impuse.")		print("Datele nu corespund restricțiilor impuse.")
	return False		return False
	if not (3 <= k <= n):		if not (3 <= nr_termeni <= n):
	print("Datele nu corespund restricțiilor impuse.")		print("Datele nu corespund restricțiilor impuse.")
	return False		return False
Line 70:		Line 70:
	if __name__ == '__main__':		if __name__ == '__main__':
	n = int(input("N este:"))		n = int(input("N este:"))
	k = 3		nr_termeni = 3
	nr_siruri = 0		nr_siruri = 0

	if not has_valid_input(n, k):		if not has_valid_input(n, nr_termeni):
	exit()		exit()

Line 87:		Line 87:
	def backtracking(sir, pozitie):		def backtracking(sir, pozitie):
	global nr_siruri		global nr_siruri
	if len(sir) >= k:		if len(sir) >= nr_termeni:
	if has_property(sir):		if has_property(sir):
	nr_siruri += 1		nr_siruri += 1

Sinn Erich: /* Restricţii şi precizări */

2023-04-27T22:40:51Z

Restricţii şi precizări

← Older revision		Revision as of 22:40, 27 April 2023
Line 26:		Line 26:
	3 ≤ '''n''' ≤ 20000		3 ≤ '''n''' ≤ 20000

	3 ≤ '''k''' ≤ n		3 ≤ '''nr_termeni''' ≤ n

	== Exemplul 1 ==		== Exemplul 1 ==

Sinn Erich: /* Exemplul 3 */

2023-04-27T07:07:56Z

Exemplul 3

← Older revision		Revision as of 07:07, 27 April 2023
Line 50:		Line 50:
	: N este:		: N este:
	: 5		: 5
			; Datele de ieșire
	: Datele sunt introduse corect.		: Datele sunt introduse corect.
	~~; Datele de ieșire~~
	: 7		: 7
	<br>		<br>

Sinn Erich: /* Exemplul 2 */

2023-04-27T07:07:47Z

Exemplul 2

← Older revision		Revision as of 07:07, 27 April 2023
Line 41:		Line 41:
	: N este:		: N este:
	: 4		: 4
			; Datele de ieșire
	: Datele sunt introduse corect.		: Datele sunt introduse corect.
	~~; Datele de ieșire~~
	: 3		: 3
	<br>		<br>

Sinn Erich: /* Exemplul 1 */

2023-04-27T07:07:39Z

Exemplul 1

← Older revision		Revision as of 07:07, 27 April 2023
Line 32:		Line 32:
	: N este:		: N este:
	: 3		: 3
			; Datele de ieșire
	: Datele sunt introduse corect.		: Datele sunt introduse corect.
	~~; Datele de ieșire~~
	: 1		: 1
	<br>		<br>

Sinn Erich: /* Exemplul 3 */

2023-04-26T20:40:33Z

Exemplul 3

← Older revision		Revision as of 20:40, 26 April 2023
Line 48:		Line 48:
	== Exemplul 3 ==		== Exemplul 3 ==
	; Datele de intrare		; Datele de intrare
			: N este:
	: 5		: 5
	: Datele sunt introduse corect.		: Datele sunt introduse corect.

Sinn Erich: /* Exemplul 2 */

2023-04-26T20:40:23Z

Exemplul 2

← Older revision		Revision as of 20:40, 26 April 2023
Line 39:		Line 39:
	== Exemplul 2 ==		== Exemplul 2 ==
	; Datele de intrare		; Datele de intrare
			: N este:
	: 4		: 4
	: Datele sunt introduse corect.		: Datele sunt introduse corect.