Vizualizare sursă pentru „1356 - N Sir”

==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==
<syntaxhighlight lang="python3" line="1">
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
</syntaxhighlight>