3348 - Suma Puteri 2

Cerință

Se dă un număr natural n. Descompuneți numărul n ca sumă de puteri ale lui 2.

Date de intrare

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

Date de ieșire

Dacă datele sunt introduse corect, pe ecran se va afișa: "Datele de intrare corespund restricțiilor impuse." și programul va afișa pe ecran, în ordine crescătoare, separate prin câte un spațiu, puterile lui 2 care au suma n. În caz contrar, se va afișa pe ecran: "Datele de intrare nu corespund restricțiilor impuse."

Restricții de precizări

• 1 ⩽ n ⩽ 2^31

Exemplul 1

Intrare

43

Ieșire

Datele introduse corespund restricțiilor impuse.

1

2

8

32

Rezolvare

Rezolvare ver. 1

<syntaxhighlight lang="python" line="1"> def validare(n):

   # Verifică dacă n este format doar din cifre și dacă este între 1 și 2^31 - 1
   return n.isdigit() and 1 <= int(n) < pow(2, 31)

def descompunere_in_puteri_de_2(n):

   puteri_de_2 = []  # Lista pentru a stoca puterile de 2
   k = 0  # Contorul puterilor de 2
   while 2 ** k <= n:  # Găsește cel mai mare exponent k pentru care 2^k este mai mic sau egal cu n
       k += 1
   k -= 1  # Scade 1 din k pentru a obține cel mai mare exponent valid
   while k >= 0:  # Descompune n în sumă de puteri de 2
       if 2 ** k <= n:
           puteri_de_2.append(2 ** k)  # Adaugă puterea de 2 la lista puteri_de_2
           n -= 2 ** k  # Scade puterea de 2 din n pentru a obține restul
       k -= 1  # Scade 1 din k pentru a trece la următorul exponent mai mic
   return puteri_de_2[::-1]  # Returnează lista puterilor de 2 în ordine descrescătoare

if __name__ == '__main__':

   n = input("Introduceți numărul n: ")
   if validare(n):
       n = int(n)
       print("Datele introduse corespund restricțiilor impuse.")
       puteri_de_2 = descompunere_in_puteri_de_2(n)
       print("{}".format("\n".join(
           str(p) for p in puteri_de_2)))  # Afișează puterile de 2 separate pe linii
   else:
       print("Datele introduse nu corespund restricțiilor impuse.")

</syntaxhighlight>