Benzar Ioan at 23:52, 2 June 2024

2024-06-02T23:52:39Z

← Older revision		Revision as of 23:52, 2 June 2024
Line 1:		Line 1:
	== Cerința ==		== Cerința ==
	~~Să se genereze toate permutările circulare ale unui șir~~ de ~~numere naturale~~, ~~unde permutările circulare sunt permutări în care primul și ultimul element sunt considerate consecutive~~.		Se dă numărul natural n. Determinati o modalitate de așezare a numerelor din mulțimea 1,2,…,n
			pe un cerc astfel încât suma a oricare două nume învecinate să nu fie pătrat perfect.
	== Date de intrare ==		== Date de intrare ==
	Programul citește de la tastatură ~~un șir de~~ n ~~numere naturale~~.		Programul citește de la tastatură numărul n.
	== Date de ieșire ==		== Date de ieșire ==
	Pe ecran ~~se vor afișa toate permutările circulare ale șirului~~, câte ~~una pe linie~~.		Programul va afișa pe ecran cele n numere cerute, separate prin câte un spațiu.
	== Restricții și precizări ==		== Restricții și precizări ==
	*1 ~~&les; '''~~n~~''' &les~~; 10		*1 ≤ n ≤ 35
	* ~~Numerele din șir sunt naturale și distincte~~		*dacă există mai multe modalități de aranjare a numerelor astfel încât să fie îndeplinită condiția, se poate afișa oricare;
			*dacă nu există nicio modalitate de aranjare se va afișa mesajul nu exista

	== Exemplu 1 ==		== Exemplu 1 ==
	;Intrare		;Intrare
	~~1 2 3~~		32

	;Iesire		;Iesire
	1 2 3~~<br>~~		1 8 28 21 4 32 17 19 30 6 3 13 12 24 25 11 5 31 18 7 29 20 16 9 27 22 14 2 23 26 10 15
	2 ~~3 1<br>~~
	~~3 1 2~~


	== Rezolvare ==		== Rezolvare ==
	<syntaxhighlight lang="python" line>		<syntaxhighlight lang="python" line>
	def ~~citeste_date~~():		import math
	~~try:~~
	~~sir = list(map(~~int~~, input~~(~~"Introduceți șirul de numere naturale, separate prin spațiu: ")~~.~~split~~()))
	~~return sir~~		# Verifică dacă un număr este pătrat perfect
	~~except ValueError:~~		def este_patrat_perfect(x):
	~~return None~~		return int(math.isqrt(x)) ** 2 == x

	~~def valideaza_date(sir):~~
	~~if not (1 <= len(sir) <= 10):~~
	~~return False~~
	~~if not all(isinstance(num, int) and num >= 0 for num in sir):~~
	~~return False~~
	~~if len(sir) != len(set(sir)):~~
	~~return False~~
	~~return True~~

	def ~~permutari_circulare~~(~~sir~~):		# Funcție de backtracking pentru a găsi o soluție validă
	~~n =~~ len(~~sir~~)		def backtrack(cerc, vizitat, n):
	~~permutari =~~ []		if len(cerc) == n:
			# Verifică dacă primul și ultimul element formează un pătrat perfect
			return este_patrat_perfect(cerc[-1] + cerc[0])

	~~def backtrack~~(~~current_perm~~, ~~used~~):		for i in range(1, n + 1):
	if ~~len(current_perm) == n~~:		if not vizitat[i]:
	if (~~current_perm~~[0] ~~== sir~~[0]):		if not cerc or este_patrat_perfect(cerc[-1] + i):
	~~permutari~~.~~append~~(~~current_perm~~[:])		cerc.append(i)
	return		vizitat[i] = True
			if backtrack(cerc, vizitat, n):
			return True
			cerc.pop()
			vizitat[i] = False
			return False

	~~for i in range(n):~~
	~~if not used[i]:~~
	~~used[i] = True~~
	~~current_perm.append(sir[i])~~
	~~backtrack(current_perm, used)~~
	~~current_perm.pop()~~
	~~used[i] = False~~

	~~used~~ = [False] * n		# Funcție pentru a găsi aranjarea corectă
	backtrack([], ~~used~~)		def gaseste_aranjare(n):
			cerc = []
			vizitat = [False] * (n + 1)
			if backtrack(cerc, vizitat, n):
			return cerc
			else:
			return "nu exista"

	~~return permutari~~

			# Funcția principală
	def main():		def main():
	~~sir~~ = ~~citeste_date~~()		n = int(input().strip())
			rezultat = gaseste_aranjare(n)
	if ~~sir is None or not valideaza_date~~(~~sir~~):		if isinstance(rezultat, list):
	print("~~Datele de intrare nu corespund restricțiilor impuse~~.")		print(" ".join(map(str, rezultat)))
	~~return~~		else:
			print(rezultat)
	print(~~"Datele de intrare corespund restricțiilor impuse."~~)
	~~permutari = permutari_circulare(sir)~~
			if __name__ == "__main__":
	~~for perm in permutari~~:		main()
	~~print~~(~~" ".join(map(str, perm))~~)

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

Benzar Ioan: Pagină nouă: == Cerința == Să se genereze toate permutările circulare ale unui șir de numere naturale, unde permutările circulare sunt permutări în care primul și ultimul element sunt considerate consecutive. == Date de intrare == Programul citește de la tastatură un șir de n numere naturale. == Date de ieșire == Pe ecran se vor afișa toate permutările circulare ale șirului, câte una pe linie. == Restricții și precizări == 1 ⩽ '''n''' ⩽ 10 Numerele din șir s...

2024-06-02T18:36:02Z

Pagină nouă: == Cerința == Să se genereze toate permutările circulare ale unui șir de numere naturale, unde permutările circulare sunt permutări în care primul și ultimul element sunt considerate consecutive. == Date de intrare == Programul citește de la tastatură un șir de n numere naturale. == Date de ieșire == Pe ecran se vor afișa toate permutările circulare ale șirului, câte una pe linie. == Restricții și precizări == *1 ⩽ '''n''' ⩽ 10 * Numerele din șir s...

New page

== Cerința ==
Să se genereze toate permutările circulare ale unui șir de numere naturale, unde permutările circulare sunt permutări în care primul și ultimul element sunt considerate consecutive.
== Date de intrare ==
Programul citește de la tastatură un șir de n numere naturale.
== Date de ieșire ==
Pe ecran se vor afișa toate permutările circulare ale șirului, câte una pe linie.
== Restricții și precizări ==
*1 &les; '''n''' &les; 10
* Numerele din șir sunt naturale și distincte

== Exemplu 1 ==
;Intrare
1 2 3

;Iesire
1 2 3<br>
2 3 1<br>
3 1 2

== Rezolvare ==
<syntaxhighlight lang="python" line>
def citeste_date():
try:
sir = list(map(int, input("Introduceți șirul de numere naturale, separate prin spațiu: ").split()))
return sir
except ValueError:
return None

def valideaza_date(sir):
if not (1 <= len(sir) <= 10):
return False
if not all(isinstance(num, int) and num >= 0 for num in sir):
return False
if len(sir) != len(set(sir)):
return False
return True

def permutari_circulare(sir):
n = len(sir)
permutari = []

def backtrack(current_perm, used):
if len(current_perm) == n:
if (current_perm[0] == sir[0]):
permutari.append(current_perm[:])
return

for i in range(n):
if not used[i]:
used[i] = True
current_perm.append(sir[i])
backtrack(current_perm, used)
current_perm.pop()
used[i] = False

used = [False] * n
backtrack([], used)

return permutari

def main():
sir = citeste_date()

if sir is None or not valideaza_date(sir):
print("Datele de intrare nu corespund restricțiilor impuse.")
return

print("Datele de intrare corespund restricțiilor impuse.")
permutari = permutari_circulare(sir)

for perm in permutari:
print(" ".join(map(str, perm)))

if __name__ == "__main__":
main()

</syntaxhighlight>

3943 - Cerc5 - Revision history

Benzar Ioan at 23:52, 2 June 2024