1356 - N Sir: Diferență între versiuni
De la Universitas MediaWiki
Mraa (discuție | contribuții) (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...) |
Mraa (discuție | contribuții) Fără descriere a modificării |
||
Linia 27: | Linia 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): | |||
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): | |||
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 | |||
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 | python nsir.py | ||
</syntaxhighlight> |
Versiunea curentă din 11 ianuarie 2024 18:03
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