Binaire - Exercices de programmation

Cherchez à résoudre chaque exercice, ne regardez la solution proposée que lorsque votre programme fonctionne.

Travaillez la solution proposée même lorsque vous avez su résoudre l'exercice.

Aide sur les listes

Du binaire au décimal.

On décide ici de coder l'écriture binaire d'un entier par la liste de ses chiffres.

Par exemple, l'entier 1101_deux sera codé par la liste [1, 1, 0, 1].

Écrire une fonction python qui :

présente un paramètre : un entier codé en binaire comme on vient de le définir (type list),
retourne en sortie l'écriture décimale de cet entier (sortie de type int).

On s'interdit ici l'usage de int(), eval()... Il s'agit de procéder 'mathématiquement'.


def binToDec(n) :
	f = len(n)-1
	s = 0 
	for k in n :
		s += k*pow(2,f)
		f -= 1
	return s
	
	
print( binToDec([1,1,0,1]) )
		
print( binToDec([1]) )

print( binToDec([1,0]) )

Réponse Python :

13
1
2

Une autre version :


def binToDec(n) :
	f = len(n)-1
	s = 0  # contiendra b_0 puis b_0+2b_1 puis b_0+2b_1+4b_2 ...
	p = 1  # contient 2^0, puis 2^1, puis 2^2 ...
	for k in reversed(n) : # on parcourt la liste n en partant de la fin
		s += k*p
		p *= 2
	return s
	
	
print( binToDec([1,1,0,1]) )
		
print( binToDec([1]) )

print( binToDec([1,0]) )

Si l'on se permettait de faire usage des fonctions python comme eval(), on pourrait procéder comme suit (par exemple) :


def binToDec(n) :
	# on transforme la liste en chaîne
	# par exemple  [1,1,0,1] en '1101'  
	ch = ''
	for x in n :
		ch += str(x)
	ch = '0b' + ch # ajout du préfixe 0b
	return eval(ch)
	
	
print( binToDec([1,1,0,1]) )
		
print( binToDec([1]) )

print( binToDec([1,0]) )

Du décimal au binaire.

Programmer l'algorithme des divisions en cascade. Les chiffres de l'écriture binaire seront stockés dans une liste puis afficher dans l'ordre usuel d'écriture.

L'écriture binaire par les divisions en cascade.

 
def cascade(n) :
   """ n est un entier > 0.
   La fonction retourne la liste de ses chiffres en 
   binaire."""
	listchiffres=[]
	while n!=0 :
		listchiffres.append(n%2)
		n//=2
	listchiffres.reverse() # la liste est renversée pour avoir les chiffres 
	                       # dans l'ordre décroissant des poids
	                       #  de la gauche vers la droite
	return listchiffres
	
def affichebinaire(n) :
	L=cascade(n)
	for x in L :
		print(x,end='')
	print()
		
		
affichebinaire(2)	
affichebinaire(4)
affichebinaire(13)

Avec une base b quelconque

b désignant un entier ≥ 2, on peut écrire tout entier en base b suivant le même principe.


def cascade(n, b) :
	""" n est un entier naturel non nul, b est la base dans 
	laquelle on veut l'écriture de n."""
	listchiffres=[]
	while n!=0 :
		listchiffres.append(n%b)
		n//=b
	listchiffres.reverse()
	return listchiffres
	
def affichebaseb(n, b) :
	L=cascade(n, b)
	for x in L :
		print(x,end='')
	print()
		
		
affichebaseb(2 , 2)	
affichebaseb(4, 2)
affichebaseb(13, 2)

Du décimal au binaire, bis.

Une autre façon de déterminer l'écriture binaire d'un entier n est de déterminer la plus grande puissance de 2 inférieure ou égale à n puis de recommencer sur le reste...

Exemple. n=25. On a 2⁴ ≤ 25 < 2⁵. 25 = 2⁴ + 9.
On a 2³ ≤ 9 < 2⁴. On a 25 = 2⁴ + 2³ + 1.
25 = 2⁴ + 2³ + 2⁰. D'où 25 = 11001_deux.

Écrire une fonction python donnant l'écriture binaire de l'entier n donné en entrée à l'aide de cette technique.

 
def plusGdPuiss(n) :
	""" n est un entier naturel non nul.
	La fonction retourne l' entier i
	tel que 2^i <= n <2^(i+1)."""
	i=0
	p=1 # contiendra les puissances de 2 successives
	while p<= n:
		i+=1
		p*=2
	return i-1
		
	
def binairePlusgdPuiss(n) :
	""" n est un entier naturel non nul.
	La fonction retourne la liste des chiffres 
	de l'écriture binaire de n."""
	pp = plusGdPuiss(n)
	n -= 2**pp
	listchiffres=[1]+[0]*pp
	while n!=0 :
		p = plusGdPuiss(n)
		listchiffres[pp-p]=1
		n -= 2**p
	return listchiffres
		
	
		
def affichebin(n) :
	L=binairePlusgdPuiss(n)
	for x in L :
		print(x,end='')
	print()
	

affichebin(13)

Et bit à bit.

On définit une fonction f (nommée et bit à bit) prenant deux arguments entiers et retournant un entier.

Exemple.
f(12,6)=4.
Explication : 12 = 0b 1100, 6 = 0b 110. On aligne les bits et on applique un "et bit à bit" :

et bit à bit - exemple
12 =	0b	1	1	0
6 =	0b	0	1	1
f(12,6) =	0b	0	1	0

Écrire une version python de la fonction f utilisant le principe des divisions en cascade.

 
def f(a,b) :
	""" a et b sont deux entiers naturels.
	La fonction retourne Et bit à bit de a et b."""
	if a>b : a,b=b,a # a est le plus petit des deux après éventuel échange
	p = 1 # puissances de 2 successives
	r = 0 # contiendra le et bit à bit
	while a!=0 :
		r += (a%2)*(b%2)*p 
		a//=2
		b//=2
		p*=2
	return r
	
	
a = 12
b = 6
print(f(a,b))

# vérification avec le et bit à bit du langage :
print( a & b )