Course list Sign in

Information

Author(s) Vincent Branders, Pierre Dupont
Deadline 07/09/2024 16:33:29
Submission limit No limitation

Sign in

Sign in

[TP.04] Savez-vous compter jusqu'à 31 sur les doigts d'une seule main ?

Votre ordinateur, oui ! Parce qu’il représente les nombres sous la forme de 0 et de 1. Il utilise un encodage binaire. Nous somme habitués à compter dans le système décimal. C’est-à-dire que la position de chaque chiffre dans un nombre est multiplié par une puissance de 10.

\({123}_{10} = 1 \times 10^2 + 2 \times 10^1 + 3 \times 10^0\)

Il en est de même en notation binaire à la différence que la base n'est pas 10 mais 2 !

\({101010}_{2} = 1 \times 2^5 + 0 \times 2^4 + 1 \times 2^3 + 0 \times 2^2 + 1 \times 2^1 + 0 \times 2^0\)

\({101010}_{2} = {42}_{10}\)

Un chiffre binaire est appelé bit (contraction de binary digit). C’est l’unité de base des systèmes informatiques. En pratique, il est stocké par un dispositif physique qui possède deux états. Par exemple, deux intensités différentes dans un circuit électrique ou deux directions de polarisation magnétique.

Dans beaucoup de cas, la transmission des bits d’un système à un autre se fait en série : un bit est envoyé à la fois. C’est le cas par exemple pour les données envoyées via les câbles USB, SATA, FireWire, etc.

Votre mission consiste à implémenter un algorithme qui transforme un entier positif de sa représentation décimale à sa représentation binaire. Nous allons simuler la communication en série en modélisant un nombre binaire par une file dont le premier élément est le bit de poids fort, c'est-à-dire le bit qui est multiplié par la plus grande puissance de 2 (dans le cas de \({42}_{10}\), les bits envoyés seront donc 1, puis 0, puis 1, puis 0, puis 1, puis 0).

Pour ce faire, utilisez le fait que \(n \% 2\) vous donne le bit de poids faible de n. Vous pouvez utiliser les TAD file et de pile. Pour tester votre implémentation, vous devrez vous-même implémenter les TAD pile et file. Pour votre soumission, les module Queue et Stack sont importés.

Question 1: [Validation] Un exemple simple

Indiquez la valeur de x à la fin des instructions suivantes :

file = dec_to_bin(42)
x = []
while not file.is_empty():
    x.append(file.dequeue())
Question 2: Conversion d'un nombre décimal

Vous êtes chargés d'implémenter la fonction suivante en Python. Pour préparer votre code, vous pouvez télécharger le fichier dec_to_bin.py qui contient la signature de la fonction et quelques exemples de tests.

Note: Lorsqu'il vous est demandé d'implémenter une fonction, vous êtes invités à ne remplir que le corps de la fonction à implémenter.

Note: Vous pouvez, dans le corps de la fonction, faire appel aux fonctions et modules importés dans le template fourni.

def dec_to_bin(n):
    """
    pre: `n` > 0
    post: renvoie la représentation binaire de `n`.
        Le premier élément de la file renvoyée est le bit de poids fort.
        Le nombre de bits renvoyé est le plus petit possible.
    """