Exercice Conversion gloutonne

Pour convertir en base \(2\) un entier écrit en base \(10\), nous pouvons utiliser l'algorithme glouton de rendu de monnaie, en utilisant les puissances de \(2\) successives comme valeurs des pièces.

Par exemple, pour obtenir la représentation binaire de \(43\), on peut utiliser les valeurs \(32\), \(16\), \(8\), \(4\), \(2\) et \(1\). On se limite à \(32\) car la puissance suivante, \(64\), est strictement supérieure à \(43\).

On procède alors ainsi :

Pour \(43\) on doit prendre \(32\) , il reste \(11\),
Pour \(11\) on ne peut pas prendre \(16\) (en effet \(16>11\)),
Pour \(11\) on doit prendre \(8\), il reste \(3\),
Pour \(3\) on ne peut pas prendre \(4\),
Pour \(3\) on doit prendre \(2\), il reste \(1\),
Pour \(1\) on doit prendre \(1\), il reste \(0\).

On obtient la représentation binaire en observant les différentes étapes : s'il est possible de prendre une puissance, on note un 1, si c'est impossible, on note un 0.

Puissance de 2	Possible ?	Bit correspondant
\(32\)	Oui	`1`
\(16\)	Non	`0`
\(8\)	Oui	`1`
\(4\)	Non	`0`
\(2\)	Oui	`1`
\(1\)	Oui	`1`

Dans la pratique, pour convertir « à la main » \(43\) en binaire, cela revient réaliser le tableau suivant :

\(32\)	\(16\)	\(8\)	\(4\)	\(2\)	\(1\)
`1`	`0`	`1`	`0`	`1`	`1`

On en déduit que \(43\) en décimal s'écrit 101011 en binaire.

✏️ À vous de jouer ... sur papier

Utiliser la méthode précédente pour convertir 100 en binaire.

Solution

on peut utiliser les valeurs \(64\), \(32\), \(16\), \(8\), \(4\), \(2\) et \(1\). On se limite à \(64\) car la puissance suivante, \(128\), est strictement supérieure à \(100\).

On procède alors ainsi :

Pour \(100\) on doit prendre \(64\) , il reste \(36\),
Pour \(36\) on doit prendre \(32\), il reste \(4\)
Pour \(4\) on doit prendre \(4\), il reste \(0\)

On obtient la représentation binaire en observant les différentes étapes : s'il est possible de prendre une puissance, on note un 1, si c'est impossible, on note un 0.

Puissance de 2	Possible ?	Bit correspondant
\(64\)	Oui	`1`
\(32\)	Oui	`1`
\(16\)	Non	`0`
\(8\)	Non	`0`
\(4\)	Oui	`1`
\(2\)	Non	`0`
\(1\)	Non	`0`

Dans la pratique, pour convertir « à la main » \(100\) en binaire, cela revient réaliser le tableau suivant :

\(64\)	\(32\)	\(16\)	\(8\)	\(4\)	\(2\)	\(1\)
`1`	`1`	`0`	`0`	`1`	`0`	`0`

On en déduit que \(100\) en décimal s'écrit 1100100 en binaire.

Travail à faire

Vous devez écrire une fonction binaire qui prend en paramètre un entier écrit en base \(10\), et renvoie la chaîne de caractères la plus courte possible (sans zéros inutiles) représentant sa conversion en binaire.

Exemples

Python Console Session

>>> binaire(43)
'101011'
>>> binaire(32)
'100000'
>>> binaire(0)
'0'
>>> binaire(54321)
'1101010000110001'

Contraintes

Vous utiliserez obligatoirement un algorithme glouton qui met en oeuvre la méthode décrite dans cet exercice.
L'utilisation de la fonction bin et du modulo (%) est interdite.

Compléter le script ci-dessous

Évaluations restantes : 5/5

ENCRYPTION_TOKEN

Solution & Remarques

🐍 Proposition de correction
def binaire(nombre):
    if nombre == 0:
        return "0"

    puissances_utiles = []
    p = 1
    while p <= nombre :
        puissances_utiles.append(p)
        p = 2 * p
    puissance_max = len(puissances_utiles) - 1

    resultat = ""          
    for i in range(puissance_max, -1, -1):
        puissance = puissances_utiles[i]
        if nombre >= puissance:
            resultat = resultat + "1"
            nombre = nombre - puissance
        else:
            resultat = resultat + "0"
    return resultat

Remarques :

👉 Cet algorithme glouton nécessite de commencer par les plus grandes puissances de 2 utiles.
Dans la solution proposée, nous avons créé une liste des puissances de 2 triées par ordre croissant que nous avons parcourue à partir de la fin.

👉 Autre possibilité en utilisant pop

Python

def binaire(nombre):
    if nombre == 0:
        return "0"

    puissances_utiles = []
    p = 1
    while p <= nombre :
        puissances_utiles.append(p)
        p = 2 * p
    puissance_max = len(puissances_utiles) - 1

    resultat = ""
    while len(puissances_utiles) > 0:
        p = puissances_utiles.pop()
        if p <= nombre:
            resultat = resultat + "1"
            nombre = nombre - p
        else:
            resultat = resultat + "0"

    return resultat

👉 Contrairement à ce que nous avons fait dans l'algorithme glouton de rendu de monnaie, il n'est pas nécessaire de constituer la liste des puissances de 2 utiles équivalente à la liste des pièces du rendu de monnaie. En effet, on trouve la puissance de 2 suivante à utiliser, par simple division entière par 2.

Autre solution possible, qui économise la création d'une liste :

Python

def binaire(nombre):
    if nombre == 0:
        return "0"
    resultat = ""

    puissance = 1
    while puissance <= nombre :
        puissance_max = puissance
        puissance = 2*puissance

    while puissance_max > 0:
        if nombre >= puissance_max:
            resultat = resultat + "1"
            nombre = nombre - puissance_max
        else:
            resultat = resultat + "0"
        puissance_max = puissance_max // 2

    return resultat

Visualisation du principe du binaire : Cartes binaires

ENCRYPTION_TOKEN