Mraa at 18:03, 11 January 2024

2024-01-11T18:03:07Z

← Older revision		Revision as of 18:03, 11 January 2024
Line 27:		Line 27:
	2) 1 = 1/3+1/5+1/5+1/5+1/15 și 33 = 3+5+5+5+15		2) 1 = 1/3+1/5+1/5+1/5+1/15 și 33 = 3+5+5+5+15
	==Rezolvare==		==Rezolvare==
			<syntaxhighlight lang="python3" line="1">
	def backtracking(n, k, target_sum, current_sum, current_sequence, result):		def backtracking(n, k, target_sum, current_sum, current_sequence, result):
	~~if k == 0:~~
	~~if current_sum == target_sum:~~
	~~result.append(list(current_sequence))~~
	~~return~~

	for i in range(1, min(n, target_sum - current_sum) + 1):		if k == 0:
	current_sequence.append(i)		if current_sum == target_sum:
	backtracking(n, k - 1, target_sum, current_sum + i, current_sequence, result)		result.append(list(current_sequence))
	current_sequence.pop()		return
			for i in range(1, min(n, target_sum - current_sum) + 1):
			current_sequence.append(i)
			backtracking(n, k - 1, target_sum, current_sum + i, current_sequence, result)
			current_sequence.pop()


	def find_sequences(n):		def find_sequences(n):
	result = []
	for k in range(2, n + 1):		result = []
	backtracking(n, k, n, 0, [], result)		for k in range(2, n + 1):
	return result		backtracking(n, k, n, 0, [], result)
			return result


	if __name__ == "__main__":		if __name__ == "__main__":
	~~# Citim numărul n din fișierul de intrare~~
	~~with open("nsir.in", "r") as f:~~
	~~n = int(f.readline().strip())~~

	# Găsim și afișăm șirurile în fișierul de ieșire		# Citim numărul n din fișierul de intrare
	sequences = find_sequences(n)		with open("nsir.in", "r") as f:
	with open("nsir.out", "w") as g:		n = int(f.readline().strip())
	if not sequences:		# Găsim și afișăm șirurile în fișierul de ieșire
	g.write("0\n")		sequences = find_sequences(n)
	else:		with open("nsir.out", "w") as g:
	for sequence in sequences:		if not sequences:
	g.write(" ".join(map(str, sequence)) + "\n")		g.write("0\n")
			else:
			for sequence in sequences:
			g.write(" ".join(map(str, sequence)) + "\n")

	python nsir.py		python nsir.py
			</syntaxhighlight>

Mraa: Pagină nouă: ==Cerința== Fie n un număr natural. Să se determine toate șirurile a de k numere naturale nu neapărat distincte: 1 ≤ a1, a2,...,ak ≤ n, astfel încât: 1) 1 = 1/a1+ 1/a2+...+ 1/ak 2) n = a1 + a2 +...+ ak ==Date de intrare== Fișierul de intrare nsir.in conține pe prima linie numărul n. ==Date de ieșire== Fișierul de ieșire nsir.out va conține pe fiecare linie câte un șir determinat, în ordine lexicografică. Dacă nu poate fi generat un astfel de șir, at...

2023-12-21T21:51:36Z

Pagină nouă: ==Cerința== Fie n un număr natural. Să se determine toate șirurile a de k numere naturale nu neapărat distincte: 1 ≤ a1, a2,...,ak ≤ n, astfel încât: 1) 1 = 1/a1+ 1/a2+...+ 1/ak 2) n = a1 + a2 +...+ ak ==Date de intrare== Fișierul de intrare nsir.in conține pe prima linie numărul n. ==Date de ieșire== Fișierul de ieșire nsir.out va conține pe fiecare linie câte un șir determinat, în ordine lexicografică. Dacă nu poate fi generat un astfel de șir, at...

New page

==Cerința==
Fie n un număr natural.
Să se determine toate șirurile a de k numere naturale nu neapărat distincte: 1 ≤ a1, a2,...,ak ≤ n, astfel încât:
1) 1 = 1/a1+ 1/a2+...+ 1/ak
2) n = a1 + a2 +...+ ak

==Date de intrare==
Fișierul de intrare nsir.in conține pe prima linie numărul n.

==Date de ieșire==
Fișierul de ieșire nsir.out va conține pe fiecare linie câte un șir determinat, în ordine lexicografică. Dacă nu poate fi generat un astfel de șir, atunci se va scrie valoarea 0 pe prima linie a fișierului de ieșire.

==Restricții și precizări==
5 ≤ n ≤ 75
se admite că cerința 1) este satisfăcută dacă: | 1/a1 + 1/a2 + … + 1/ak – 1 |<10-5
==Exemplu==:
nsir.in

33
nsir.out

3 3 9 9 9
3 5 5 5 15
==Explicație==
Se observă că
1) 1 = 1/3+1/3+1/9+1/9+1/9 și 33 = 3+3+9+9+9
2) 1 = 1/3+1/5+1/5+1/5+1/15 și 33 = 3+5+5+5+15
==Rezolvare==
def backtracking(n, k, target_sum, current_sum, current_sequence, result):
if k == 0:
if current_sum == target_sum:
result.append(list(current_sequence))
return

for i in range(1, min(n, target_sum - current_sum) + 1):
current_sequence.append(i)
backtracking(n, k - 1, target_sum, current_sum + i, current_sequence, result)
current_sequence.pop()

def find_sequences(n):
result = []
for k in range(2, n + 1):
backtracking(n, k, n, 0, [], result)
return result

if __name__ == "__main__":
# Citim numărul n din fișierul de intrare
with open("nsir.in", "r") as f:
n = int(f.readline().strip())

# Găsim și afișăm șirurile în fișierul de ieșire
sequences = find_sequences(n)
with open("nsir.out", "w") as g:
if not sequences:
g.write("0\n")
else:
for sequence in sequences:
g.write(" ".join(map(str, sequence)) + "\n")
python nsir.py

1356 - N Sir - Revision history

Mraa at 18:03, 11 January 2024