Il s’agit d’écrire ici l’algorithme en pseudo-code de la conversion en binaire par suite de divisions. On dit aussi qu’il s’agit de la méthode euclidienne (car on fait des divisions euclidiennes). Vous avez déjà déroulé cet algorithme sur des exemples et vous êtes rendus compte que pour obtenir l’écriture binaire il fallait concaténer les restes des divisions euclidiennes.
✍️ Question 1 : Quel type de données de base permet de concaténer des éléments ?
✍️ Question 2 : L’algorithme consiste à répéter plusieurs fois les mêmes instructions et s’arrête lorsqu’on obtient un quotient nul. Quel type de structure vous paraît adapter pour écrire cet algorithme ? Pourquoi ?
✍️ Question 3 : Écriture de l'algorithme.
Complétez l'algorithme suivant de manière à ce qu'il corresponde à la spécification suivante
Spécification :
nDn en base 2D représente l’écriture en base 2 de nAlgorithme :
D ← ...... # valeur de D avant la première division
tant que n ...... faire
r ← ...... # reste de la division euclidienne
D ← concaténation( ... , ... )
... ← n div 2 # quotient de la division
fin tant que💻 Question 4 : Programmez cet algorithme en Python et testez-le sur des exemples, en comparant avec la fonction bin() de Python..
💻 Question 5 : Transformez ce script Python en une fonction, appelée entier_en_binaire qui prend en paramètre l’entier n et qui renvoie la chaîne D. Vous pourrez ainsi, réutiliser cette fonction !
Exemples :
>>> entier_en_binaire(5)
'101'
>>> binaire_en_entier(255)
'11111111'Le but est désormais d’écrire l’algorithme de la conversion inverse. Cet algorithme répond à la spécification suivante :
Spécification :
D nD en base 10D est formé uniquement de caractères 0 et 1n est l’écriture en base 10 de D✍️ Question 6 : Quel type de structure permet de parcourir une chaîne de caractères très rapidement ?
✍️ Question 7 : Écriture de l'algorithme
Compléter l’algorithme suivant de manière à ce qu’il corresponde à la spécification précédente.
Attention : lorsque l’on parcoure la chaîne
Davec une bouclefor, on commence par le chiffre de gauche et donc par la plus grande puissance de 2. Il faut aussi penser à convertir les caractères en des entiers pour faire les calculs.
n ← ...... # valeur de n avant les calculs
i ← ......... # plus grande puissance de 2 au départ
pour carac dans D faire
n ← n + ...... # ajout du chiffre multiplié par sa puissance de 2
... ← ...... # la puissance diminue de 1
fin pour💻 Question 8 : Codez une fonction Python, appelée binaire_en_entier qui prend en paramètre une chaîne de caractères D (constituée de 0 et de 1) et qui renvoie l’entier n. Vous pourrez ainsi, réutiliser cette fonction.
Exemples :
>>> binaire_en_entier('101')
5
>>> binaire_en_entier('11111111')
255💻 Question 9 (optionnelle) : Programmez des fonctions Python permettant de coder les conversions "décimal vers hexadécimal" et "hexadécimal vers décimal". La difficulté réside dans les conversions entre les caractères 'A', 'B', ..., 'F' et leurs valeurs entières.
On peut poser les additions et multiplications comme en base 10 !
Exemple 1 : Calcul de $(101)_2 + (1101)_2$
On pose l'addition :
Vérification : $(101)_2+(1101)_2=5+13=18=(10010)_2$.
Exemple 2 : Calcul de $(1110)_2 \times (101)_2$
On pose la multiplication :
Vérification : $(1110)_2×(101)_2=14×5=70=(100110)_2$.
✍️ Question : Calculer la somme $(1011)_2+(11)_2$ et le produit $(110)_2×(100)_2$.
Vous vérifierez vos résultats en repassant par la base décimale.
Cas de la somme : Ajouter deux entiers naturels ayant respectivement $k$ et $\ell$ bits significatifs en nécessite au plus $\max(k, \ell) + 1$.
Par exemple, si on additionne un entier de 3 bits avec un autre de 5 bits, alors la somme s'écrit au plus sur 6 bits.
Si $n$ et $m$ sont deux entiers naturels ayant respectivement $k$ et $\ell$ bits significatifs alors :
$n \lt 2^k$ et $m \lt 2^\ell$ et donc $n+m \lt 2^k + 2^\ell \lt 2 \times 2^{\max(k, \ell)} = 2^{\max(k, \ell)+1}$.
Cas du produit : Multiplier deux entiers naturels $n$ et $m$ ayant respectivement $k$ et $\ell$ bits significatifs en nécessite au plus $k+\ell$.
Par exemple, si on mutliplie un entier de 3 bits par un autre de 5 bits, alors le produit s'écrit au plus sur 8 bits.
On a : $n \lt 2^k$ et $m \lt 2^\ell$ alors $n \times m \lt 2^k \times 2^\ell=2^{k+\ell}$.
Dans tout l’exercice, les nombres $n$ et $m$ désignent des entiers naturels ayant respectivement 4 et 5 bits significatifs.
Déterminez dans chaque cas le nombre de bits nécessaires à l’écriture en base 2 de le somme $n+m$ puis du produit $n×m$.
Références :
Germain Becker & Sébastien Point, Lycée Emmanuel Mounier, Angers
Voir en ligne : info-mounier.fr/premiere_nsi/types_base/entiers-positifs-exercices