3348 - Suma Puteri 2

From Bitnami MediaWiki

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> def validare(n):

   return n.isdigit() and 1 <= int(n) < pow(2, 31)

def descompunere_in_puteri_de_2(n):

   puteri_de_2 = []
   k = 0
   while 2 ** k <= n:
       k += 1
   k -= 1
   while k >= 0:
       if 2 ** k <= n:
           puteri_de_2.append(2 ** k)
           n -= 2 ** k
       k -= 1
   return puteri_de_2[::-1]


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)))
   else:
       print("Datele introduse nu corespund restricțiilor impuse.")

</syntaxhighlight>