3994 - Partitii Numar 5

From Bitnami MediaWiki

Cerința[edit | edit source]

Se dă un număr natural n. Determinați, în ordine lexicografică, toate modalitățile de a-l scrie pe n ca sumă de numere naturale pare.

Date de intrare[edit | edit source]

Programul citește de la tastatură numărul natural n.

Date de ieșire[edit | edit source]

Programul va afișa pe câte linie a ecranului câte un șir de numere naturale pare ordonate crescător, separate prin câte un spațiu. Suma numerelor din fiecare șir este n. Șirurile vor fi afișate în ordine lexicografică.

Dacă nu există nicio modalitate de a-l scrie pe n ca sumă de numere naturale pare se va afișa mesajul imposibil.

Restricții și precizări[edit | edit source]

1 ≤ n ≤ 40 ==Exemplu==: Intrare

10 Ieșire 2 2 2 2 2 2 2 2 4 2 2 6 2 4 4 2 8 4 6 10

Rezolvare[edit | edit source]

<syntaxhighlight lang="python3" line="1"> def generare_siruri(n, suma_curenta, sir_parcial):

  # Verificăm dacă am atins suma dorită
  if suma_curenta == n:
      print(*sir_parcial)
      return
  elif suma_curenta > n:
      return
  # Generăm numere pare și continuăm recursiv
  for i in range(2, n + 1, 2):
      generare_siruri(n, suma_curenta + i, sir_parcial + [i])


if __name__ == "__main__":

  # Citim datele de intrare
  n = int(input())
  # Apelăm funcția pentru a afișa șirurile
  generare_siruri(n, 0, [])
  # Verificăm dacă nu există nicio modalitate de a-l scrie pe n ca sumă de numere naturale pare
  if n % 2 != 0:
      print("imposibil")

python sumaNNumerePare.py </syntaxhighlight>