Formation I.S.N.

Les puissances de 2

Exercice : reconnaître une puissance de deux

Écrire une fonction python récursive :

Entrée Un entier naturel n non nul.
Sortie True si n est une puissance de 2, False sinon.
  • définition récursive
  • un code

Si n = 1, n est une puissance de 2.

Si n > 1 :

  • Si n est impair, ce n'est pas une puissance de 2.
  • Sinon (c'est à dire lorsque n est multiple de 2 ), n est une puissance de 2 si et seulement si le quotient de n par 2 est une puissance de 2. 

def estPuissanceDeDeux(n) :
	if n == 1 : return True  
	if (n%2 == 1) : return False
	else : return estPuissanceDeDeux(n//2)
			
			
print(estPuissanceDeDeux(16))
print(estPuissanceDeDeux(17))

Complément Python

Pour répondre à la question de la reconnaissance d'une puissance de 2, on peut utiliser le fait que l'écriture en base deux est un 1 suivi de 0 : 


def estPuissanceDe2(n) :
	if (n == 1) or (n == 2) : return True
	return (int(bin(n)[3:]) == 0)
	
print( estPuissanceDe2( 2**0 ) )
print( estPuissanceDe2( 2**1 ) )
print( estPuissanceDe2( 2**2 ) ) 
print( estPuissanceDe2( 2**8 ) ) 
print( estPuissanceDe2( 2**8 + 1 ) )