0548 - Hamilton - Revision history

Ramona Dragoș: /* Rezolvare */

2024-01-08T16:52:37Z

Rezolvare

← Older revision		Revision as of 16:52, 8 January 2024
Line 45:		Line 45:
	# Check constraints 1 ≤ n ≤ 10		# Check constraints 1 ≤ n ≤ 10
	if not (1 <= n <= 10):		if not (1 <= n <= 10):
	with open("~~hamilton~~.~~out~~", "w") as g:		with open("hamiltonout.txt", "w") as g:
	g.write("~~Datele nu corespund restrictiilor~~ impuse\n")		g.write("Nu au fost respectate cerintele impuse\n")
	return False		return False

Line 53:		Line 53:
	for j in range(1, n + 1):		for j in range(1, n + 1):
	if not (0 <= a[i][j] <= 1): # Corrected condition here		if not (0 <= a[i][j] <= 1): # Corrected condition here
	with open("~~hamilton~~.~~out~~", "w") as g:		with open("hamiltonout.txt", "w") as g:
	g.write("~~Datele nu corespund restrictiilor~~ impuse\n")		g.write("Nu au fost respectate cerintele impuse\n")
	return False		return False

Line 90:		Line 90:
	def afisare():		def afisare():
	global k, ns		global k, ns
	with open("~~hamilton~~.~~out~~", "a") as g:		with open("hamiltonout.txt", "a") as g:
	g.write("1\n")		g.write("1\n")
	g.write(" ".join(map(str, st[1:n + 1])) + " " + str(st[1]) + "\n")		g.write(" ".join(map(str, st[1:n + 1])) + " " + str(st[1]) + "\n")
Line 96:		Line 96:
	ns += 1		ns += 1

	with open("~~hamilton~~.in", "r") as f:		with open("hamiltonin.txt", "r") as f:
	n = int(f.readline().strip())		n = int(f.readline().strip())
	a = [[0] * (n + 1) for _ in range(n + 1)]		a = [[0] * (n + 1) for _ in range(n + 1)]
Line 110:		Line 110:
	st = [0] * 100		st = [0] * 100

	with open("~~hamilton~~.~~out~~", "w") as g:		with open("hamiltonout.txt", "w") as g:
	backtracking()		backtracking()
	if ns == 0:		if ns == 0:

Ramona Dragoș: /* Rezolvare */

2024-01-08T16:50:41Z

Rezolvare

← Older revision		Revision as of 16:50, 8 January 2024
Line 45:		Line 45:
	# Check constraints 1 ≤ n ≤ 10		# Check constraints 1 ≤ n ≤ 10
	if not (1 <= n <= 10):		if not (1 <= n <= 10):
	with open("~~hamiltonout~~.~~txt~~", "w") as g:		with open("hamilton.out", "w") as g:
	g.write("~~Nu au fost respectate cerintele~~ impuse\n")		g.write("Datele nu corespund restrictiilor impuse\n")
	return False		return False

Line 53:		Line 53:
	for j in range(1, n + 1):		for j in range(1, n + 1):
	if not (0 <= a[i][j] <= 1): # Corrected condition here		if not (0 <= a[i][j] <= 1): # Corrected condition here
	with open("~~hamiltonout~~.~~txt~~", "w") as g:		with open("hamilton.out", "w") as g:
	g.write("~~Nu au fost respectate cerintele~~ impuse\n")		g.write("Datele nu corespund restrictiilor impuse\n")
	return False		return False

Line 90:		Line 90:
	def afisare():		def afisare():
	global k, ns		global k, ns
	with open("~~hamiltonout~~.~~txt~~", "a") as g:		with open("hamilton.out", "a") as g:
	g.write("1\n")		g.write("1\n")
	g.write(" ".join(map(str, st[1:n + 1])) + " " + str(st[1]) + "\n")		g.write(" ".join(map(str, st[1:n + 1])) + " " + str(st[1]) + "\n")
Line 96:		Line 96:
	ns += 1		ns += 1

	with open("~~hamiltonin~~.~~txt~~", "r") as f:		with open("hamilton.in", "r") as f:
	n = int(f.readline().strip())		n = int(f.readline().strip())
	a = [[0] * (n + 1) for _ in range(n + 1)]		a = [[0] * (n + 1) for _ in range(n + 1)]
Line 110:		Line 110:
	st = [0] * 100		st = [0] * 100

	with open("~~hamiltonout~~.~~txt~~", "w") as g:		with open("hamilton.out", "w") as g:
	backtracking()		backtracking()
	if ns == 0:		if ns == 0:
	g.write("0\n")		g.write("0\n")

	</syntaxhighlight>		</syntaxhighlight>

Ramona Dragoș at 20:44, 7 January 2024

2024-01-07T20:44:52Z

Show changes

Ramona Dragoș: /* Restricții și precizări */

2023-12-31T13:14:01Z

Restricții și precizări

← Older revision		Revision as of 13:14, 31 December 2023
Line 7:		Line 7:
	== Restricții și precizări ==		== Restricții și precizări ==
	*1 &les; n &les; 10		*1 &les; n &les; 10
	1 &les; i, j &les; n		*1 &les; i, j &les; n
	*în ciclul afișat, primul și ultimul vârf sunt egale		*în ciclul afișat, primul și ultimul vârf sunt egale
	*orice ciclu hamiltonian afișat va fi acceptat		*orice ciclu hamiltonian afișat va fi acceptat

	== Exemplu 1 ==		== Exemplu 1 ==
	;hamiltonin.txt		;hamiltonin.txt

Ramona Dragoș: Pagină nouă: == Cerința == Se dă un graf neorientat cu n vârfuri. Determinați, dacă există, un ciclu hamiltonian. == Date de intrare == Fișierul de intrare hamiltonin.txt conține pe prima linie numărul n, iar pe a următoarele linii perechi de numere i j, cu semnificația că există muchie de la i la j. == Date de ieșire == Fișierul de ieșire hamiltonout.txt va conține pe prima linie numărul 1, dacă s-a determinat un ciclu hamiltonian, respectiv 0, în caz contrar. Dacă s...

2023-12-31T13:13:34Z

Pagină nouă: == Cerința == Se dă un graf neorientat cu n vârfuri. Determinați, dacă există, un ciclu hamiltonian. == Date de intrare == Fișierul de intrare hamiltonin.txt conține pe prima linie numărul n, iar pe a următoarele linii perechi de numere i j, cu semnificația că există muchie de la i la j. == Date de ieșire == Fișierul de ieșire hamiltonout.txt va conține pe prima linie numărul 1, dacă s-a determinat un ciclu hamiltonian, respectiv 0, în caz contrar. Dacă s...

New page

== Cerința ==
Se dă un graf neorientat cu n vârfuri. Determinați, dacă există, un ciclu hamiltonian.
== Date de intrare ==
Fișierul de intrare hamiltonin.txt conține pe prima linie numărul n, iar pe a următoarele linii perechi de numere i j, cu semnificația că există muchie de la i la j.
== Date de ieșire ==
Fișierul de ieșire hamiltonout.txt va conține pe prima linie numărul 1, dacă s-a determinat un ciclu hamiltonian, respectiv 0, în caz contrar. Dacă s-a determinat un ciclu hamiltonian, pe linia următoare se vor afișa vârfurile acestui ciclu, separate prin exact un spațiu.
== Restricții și precizări ==
*1 &les; n &les; 10
1 &les; i, j &les; n
*în ciclul afișat, primul și ultimul vârf sunt egale
*orice ciclu hamiltonian afișat va fi acceptat
== Exemplu 1 ==
;hamiltonin.txt
:9
:1 2
;1 4
:2 3
:2 4
:2 5
:3 4
:3 8
:3 9
:4 6
:5 6
:5 7
:5 8
:7 8
:8 9
;hamiltonout.txt
:1
:1 2 3 9 8 7 5 6 4 1
<br>
== Exemplu 2 ==
;hamiltonin.txt
:0
: 0 0
;hamiltonout.txt
: Nu au fost respectate cerintele impuse
<br>
== Rezolvare ==
<syntaxhighlight lang="python" line>
#0548 - Hamilton
def is_valid(v, pos, path, graph):
if not graph[path[pos - 1]][v]:
return False

if v in path:
return False

return True

def hamiltonian_cycle_util(graph, path, pos):
n = len(graph)

if pos == n:
return graph[path[pos - 1]][path[0]] == 1

for v in range(n):
if is_valid(v, pos, path, graph):
path[pos] = v

if hamiltonian_cycle_util(graph, path, pos + 1):
return True

path[pos] = -1

return False

def hamiltonian_cycle(graph):
n = len(graph)
path = [-1] * n

path[0] = 0

if not hamiltonian_cycle_util(graph, path, 1):
return 0, []

return 1, [v + 1 for v in path] + [path[0] + 1]

def check_restrictions(n, edges):
if not (1 <= n <= 10):
return False
for i, j in edges:
if not (1 <= i <= n) or not (1 <= j <= n):
return False
return True

def write_output_with_restrictions(file_path, result, n, edges):
with open(file_path, 'w') as file:
if not check_restrictions(n, edges):
file.write("Nu au fost respectate cerintele impuse\n")
return

file.write(str(result[0]) + '\n')

if result[0] == 1:
file.write(' '.join(map(str, result[1])) + '\n')

def read_input(file_path):
with open(file_path, 'r') as file:
n = int(file.readline().strip())
graph = [[0] * n for _ in range(n)]

for line in file:
i, j = map(int, line.strip().split())
graph[i - 1][j - 1] = 1
graph[j - 1][i - 1] = 1

return n, graph

if __name__ == "_main_":
input_file = "hamiltonin.txt"
output_file = "hamiltonout.txt"

n, graph = read_input(input_file)
result = hamiltonian_cycle(graph)
write_output_with_restrictions(output_file, result, n, [(i + 1, j + 1) for i in range(n) for j in range(n) if graph[i][j] == 1])
</syntaxhighlight>