0830 - Generare2

Cerinţa

Se dau patru numere naturale n a x y. Să se afișeze elementele mulțimii M, cu următoarele proprietăți:

toate elementele lui M sunt numere naturale mai mici sau egale cu n; a se află în M; dacă b se află în M, atunci b+x și b+y se află în M.

Date de intrare

Programul citește de la tastatură numerele n a x y.

Date de ieșire

Dacă datele de intrare corespund restrictiilor impuse se va afișa mesajul "Datele de intrare corespund restricțiilor" și pe un rând nou se afișează ceea ce se cere. Altfel, dacă datele de intrare nu corespund cerinței se va afișa mesajul: "Datele de intrare nu corespund cerinței".

Restricţii şi precizări

1 ≤ n ≤ 10000 1 ≤ x , y ≤ 10000 0 ≤ a ≤ 10000

Exemplu

Exemplu 1

<syntaxhighlight lang="python" line> n = 25 a = 3 x = 4 y = 11 Datele de intrare corespund restricțiilor M = {3, 7, 11, 14, 15, 18, 19, 22, 23, 25} </syntaxhighlight>

Exemplu 2

<syntaxhighlight lang="python" line> n = 1 a = 2 x = 3 y = 4 Datele de intrare nu corespund cerinței </syntaxhighlight>

Rezolvare

<syntaxhighlight lang="python" line>

def suma(v, n):

   if n == 1:
       return v[0]
   else:
       return v[n-1] + suma(v, n-1)

try:

   n = int(input("Introduceți numărul de elemente ale tabloului: "))
   if n < 1 or n > 100:
       print("Datele de intrare nu corespund restrictiilor impuse.")
   else:
       v = []
       for i in range(n):
           elem = int(input(f"v[{i}] = "))
           v.append(elem)
       print("Datele de intrare corespund restricțiilor impuse.")
       print("Suma elementelor din tablou este:", suma(v, n))

except ValueError:

   print("Datele de intrare nu corespund restrictiilor impuse.")

</syntaxhighlight>

Explicații

Funcția validare primește ca parametri numerele n, a, x și y și verifică dacă acestea respectă restricțiile cerute de problema. Dacă datele de intrare sunt valide, funcția returnează True, altfel returnează False.

Funcția rezolvare primește ca parametri numerele n, a, x și y și construiește mulțimea M cu ajutorul unui algoritm de tip backtracking. Mai întâi se adaugă elementul a în mulțimea M. Apoi, se parcurge mulțimea M și pentru fiecare element i din mulțime, se calculează elementele i + x și i + y. Dacă acestea sunt mai mici sau egale cu n, atunci sunt adăugate în mulțimea M. Se continuă până când nu se mai pot adăuga elemente în mulțime.

Funcția main este funcția principală a programului. În ea se citesc datele de intrare de la utilizator și se verifică dacă sunt valide apelând funcția validare. Dacă datele de intrare sunt valide, se apelează funcția rezolvare și se afișează mulțimea M. Altfel, se afișează un mesaj corespunzător.