Programmer en python le changement de base

Attention

Dans cette page, les exercices 1, 2 et 3 sont à connaître.

Les autres exercices peuvent être considérés comme des exercices d'entraînement: traitez les si vous en avez le temps, mais ce n'est pas une priorité.

Exercices à maîtriser

Exercice 1.

Ecrire un corps possible pour la fonction python spécifiée comme suit:

def deStringBinaireVersDecimal(n):
    """
    n -- type string. 
    n est un mot constitué uniquement de '0' et de '1' 
    et correspond à l'écriture binaire d'un entier.

    renvoie l'entier (type int) correspondant.
    >>> deStringBinaireVersDecimal('0')
    0
    >>> deStringBinaireVersDecimal('1')
    1
    >>> deStringBinaireVersDecimal('10')
    2
    >>> deStringBinaireVersDecimal('1001')
    9
    """

Note

Le programme donné dans la première page répond à la question.

Ce programme commençait la lecture de la chaîne par la gauche, c'est à dire par le coefficient de la plus grande puissance de la base.

Essayez d'imaginer un autre programme qui commencerait la lecture de la chaîne par la droite, c'est à dire par les unités.

Indication 1: encore le principe d'accumulateur

Lorsqu'on dispose d'une écriture binaire, par exemple '101101', on cherche à accumuler les chiffres et la puissance de deux associée dans une variable.

On commence par mettre à 0 une variable "d'accumulation":
S ← 0
On commence ensuite par la droite (les unités), ici 1:
S ← S + 1 × 2⁰
Puis le bit des "deuzaines", ici 0:
S ← S + 0 × 2¹
Puis le chiffre suivant (toujours en lecture de droite à gauche):
S ← S + 1 × 2²
Et on poursuit ainsi:
S ← S + 1 × 2³
S ← S + 0 × 2⁴
S ← S + 1 × 2⁵

Vous n'avez plus quà traduire cela par une boucle.

Indication 2: miroir

Pour faciliter la lecture de la chaîne en commençant par la droite, on peut utiliser un exercice vu dans le cours sur les chaînes de caractère.

def miroir(mot):
    """
    mot -- chaine de caractères

    renvoie la chaîne renversée.
    >>> miroir('python')
    'nohtyp'
    """

Indication 3

Lorsqu'on lit un '1' ou un '0', on aimerait ici l'utiliser comme un chiffre pour calculer S.

Il suffit pour cela d'utiliser int. En effet:

• int('1') donne l'entier 1.
• int('0') donne l'entier 0.

un code pour miroir

def miroir(mot):
    """
    mot -- chaine de caractères

    renvoie la chaîne renversée.
    >>> miroir('python')
    'nohtyp'
    """
    ch = ''
    for lettre in mot:
        ch = lettre + ch
    return ch

une solution

def deStringBinaireVersDecimal(n):
    """
    n -- type string. 
    n est un mot constitué uniquement de '0' et de '1' 
    et correspond à l'écriture binaire d'un entier.

    renvoie l'entier (type int) correspondant.
    >>> deStringBinaireVersDecimal('0')
    0
    >>> deStringBinaireVersDecimal('1')
    1
    >>> deStringBinaireVersDecimal('10')
    2
    >>> deStringBinaireVersDecimal('1001')
    9
    >>> deStringBinaireVersDecimal('110')
    6
    """

    S = 0 # contiendra l'entier 
    for indice, bit in enumerate(miroir(n)): 
        S = S + int(bit) * 2**indice
    return S

Exercice 2.

Ecrire un corps possible pour la fonction python ci-dessous:

def ecritureBinaire(n):
    """"
    n -- entier naturel (type int).

    renvoie une chaîne de caractères. 
    Cette chaîne de caractères
    est constituée de '0' et de '1' 
    et elle correspond à l'écriture binaire 
    de l'entier n.
    L'algorithme utilisé est celui de la division en cascade.
    >>> ecritureBinaire(4)
    '100'
    >>> ecritureBinaire(18)
    '10010'
    """

Démarche

Rappelons qu'avant d'écrire du code, il faut toujours tenter d'expliciter les opérations en jeu.

Ici, vous devez essayer d'expliciter ce que vous faîtes dans une division en cascade.
Il doit être clair que cette cascade consiste à répéter une même action: identifiez cette action, tentez de la traduire en pseudo-code... Il vous restera à encapsuler cela dans une boucle.

Indication: explicitons une étape

Si vous n'êtes pas parvenu à expliciter l'action répétée, la voici un peu explicitée:

• on obtient un bit comme reste de n dans la division entière par 2 (en python, le reste est n%2 et l'on devra transformer ce reste en chaîne, on utilisera donc str(n%2)).
• Puis on remplace n par le quotient de n par 2 (soit n = n//2 en python)
• et on recommence.

Essayez maintenant d'utiliser tout cela dans une boucle python.
Cette boucle stoppe quand n devient 0.

Un code possible

def ecritureBinaire(n):
    """"
    n -- entier naturel (type int).

    renvoie une chaîne de caractères. 
    Cette chaîne de caractères
    est constituée de '0' et de '1' 
    et elle correspond à l'écriture binaire 
    de l'entier n.
    L'algorithme utilisé est celui de la division en cascade.
    >>> ecritureBinaire(4)
    '100'
    >>> ecritureBinaire(18)
    '10010'
    """
    # on traite le cas particulier de 0 à part:
    if n == 0: return '0'

    # les autres cas:
    ch = ''
    while n != 0:
        ch = str(n%2) + ch # écriture du nouveau chiffre à gauche des précédents
        n = n//2 # n devient le quotient suivant
    return ch


### TESTS ###

for i in range(10):
    print(f"Ecriture binaire de {i}: {ecritureBinaire(i)}.")

Exercice 3

Que pouvez-vous dire des valeurs renvoyées par la fonction suivante:

def mystere(n):
    """"
    n -- entier naturel (type int).
    """

    if n == 0: return 1
    compteur = 0
    while n != 0:
        n = n//2  
        compteur = compteur + 1
    return compteur

Réponse

La fonction renvoie le nombre de bits dans l'écriture binaire de l'entier n.

Explication

Nous avons vu que remplacer n par son quotient dans la division par 2 (instruction n = n//2) revient à supprimer le dernier bit (bit de droite) de l'écriture binaire de n.

Pour n ≠ 0, la condition n != 0 ne sera plus satisfaite lorsqu'on aura épuisé tous les bits de n. En d'autres termes, lorsqu'on aura fait un nombre de passages dans la boucle égal au nombre de bits de l'écriture binaire de n.

La fonction renvoie donc le nombre de bits de l'écriture binaire de n.

Lien avec la cascade

Retravailler l'algorithme des divisions en cascade pour constater que l'algorithme utilisé pour programmer la fonction ci-dessus est essentiellement celui des divisions en cascade mais sans inscrire les chiffres obtenus au fur et à mesure. On se contente de compter le nombre de divisions par 2 nécessaire.

Et en base dix?

Réécrire la même fonction mais dans la base dont vous avez l'habitude (base 10). Vous devriez au moins dans ce cas vous convaincre facilement que la fonction (code ci-dessous) renvoie le nombre de chiffres de l'écriture décimale (sinon, il vous faudra sans doute réviser le programme de l'école élémentaire!).

def nombre_de_chiffres(entier, base):
    """"
    entier -- entier naturel (type int).
    base -- entier > 1
    """

    if entier == 0: return 1
    compteur = 0
    while entier != 0:
        entier = entier//base  
        compteur = compteur + 1
    return compteur

Exemple:

>>> nombre_de_chiffres(345, base = 10)
3

Exercices facultatifs

Exercice 4

Dans cette partie, on cherche à écrire une nouvelle fonction prenant en entrée un entier naturel et donnant en sortie l'écriture binaire de cet entier. Mais cette fois, cette fonction devra s'appuyer sur la fonction blog (voir les pages suivantes concernant log, dlog, blog).

le principe avec des exemples

• Cherchons à écrire 37 en binaire avec la fonction blog.
  blog(37) = 5. On peut écrire: $37 = 2^5 + 5$.
  blog(5) = 2. On peut écrire: $37 = 2^5 + 2^2 + 1$. Et finalement: $37 = 2^5 + 2^2 +2^0$, ou encore: $37 = 1\times 2^5 + 0\times 2^4 + 0\times 2^3 + 1\times 2^2 + 0\times 2^1 + 1\times 2^0$, soit $37 = 100101_{\text{deux}}$.

• Cherchons de même à écrire 42 en binaire avec la fonction blog.
  blog(42) = 5 et $42 = 2^5 + 10$.
  blog(10) = 3 et $42 = 2^5 + 2^3 + 2$. D'où: $42 = 101010_{\text{deux}}$.

Écrire une fonction python spécifiée comme ci-dessous et s'appuyant sur l'utilisation de la fonction blog.

def ecritureBinaire(n):
    """
    n -- entier naturel.

    renvoie une chaîne de '0' et de '1' donnant
    l'écriture binaire de l'entier n.
    """

Un code possible pour ecritureBinaire

def blog(n):
    """
    n -- entier naturel non nul.

    renvoie le plus grand entier naturel p
    tel que 2**p <= n.
    """
    p = 0
    produit = 1
    while produit <= n:
        p += 1
        produit *= 2
    return p-1


def ecritureBinaire(n):
    """
    n -- entier naturel

    renvoie la chaîne de caractères écriture binaire de n.
    """
    if n == 0: return '0'
    p = blog(n) 
    ch = ''
    n = n - 2**p
    while n >= 0:
        q = blog(n)
        ch = ch + '1'
        for _ in range(q,p-1): ch = ch + '0'  
        p = q
        n = n - 2**p
    return ch


### TESTS ###

for i in range(20):
    print(f"Ecriture binaire de {i}: {ecritureBinaire(i)}.")

Exercice 5

Note

Cet exercice est en lien avec le principe de dichotomie vu plus tard dans l'année.
Vous pourrez y revenir lorsque nous étudierons ce principe de dichotomie.

On considère les fonctions python suivantes:

def milieu(a,b):
    """
    a, b -- entiers

    renvoie le "milieu entier" de [a;b], 
    c'est à dire le quotient entier de la division de a+b par 2.
    """
    return (a+b)//2



def mystere(gauche, droite):
    """
    gauche -- entier
    droite -- entier
    Précondition: gauche < droite
    """
    compteur = 0
    while gauche <= droite:
        centre =  milieu(gauche, droite)
        if  (droite-gauche)%2 == 1:
            gauche  = centre+1
        else:
            droite = centre-1
        compteur = compteur + 1

    return compteur

Quel lien y a-t-il entre le résultat mystere(gauche, droite) et les entrées gauche et droite ?

Solution

A chaque étape, on remplace soit gauche par le milieu de [gauche, droite], soit droite par le milieu de [gauche, droite].

A chaque étape, la différence droite-gauche est donc (à peu près) remplacée par sa moitié, c'est à dire par (droite-gauche)//2.

On s'attend donc en fin de compte à obtenir une valeur qui est à peu près le nombre de bits de l'écriture binaire du nombre droite-gauche intial.

Vous vérifierez sur une série d'exemples que l'on obtient effectivement à peu près le nombre blog(droite-gauche)+1.

Important

Cet exercice n'est pas anecdotique: il présente ce qui sera l'essentiel du raisonnement lorsqu'on cherchera à établir plus tard dans l'année la complexité d'une recherche dichotomique.

Le résultat que l'on obtiendra alors, basé sur le raisonnement ci-dessus, est qu'une recherche dichotomique dans une liste de nombres demande un nombre d'opérations élémentaires (au pire) à peu près proportionnel au nombre de bits de l'écriture binaire de la longueur de la liste...(revenir là-dessus plus tard dans l'année: si cela vous semble incompréhensible pour le moment, cela n'a rien d'étonnant!)

Recherche dichotomique (nous verrons cela plus tard)

Avec des dictionnaires (facultatif)

Pour la base 16, il est utile d'utiliser des dictionnaires. Nous présentons ci-dessous rapidement les dictionnaires mais nous ne les étudierons que plus tard dans l'année. Vous pourrez revenir sur ces exercices lorsque les dictionnaires auront été vus en classe.

Qu'est ce qu'un dictionnaire?

Le type dictionnaire sera vu un peu plus en détail plus tard.
Pour les exercices, il suffit de voir un dictionnaire comme un tableau dans lequel on remplace les indices par des noms explicites.

Par exemple:

Exercice 6

Ecrire un corps possible pour la fonction python ci-dessous:

def ecritureHexa(n):
    """"
    n -- entier naturel (type int).

    renvoie une chaîne de caractères. 
    Cette chaîne de caractères
    est constituée de "chiffres" hexadécimaux (chiffres  de 0 à 9 et de a à f)
    et elle correspond à l'écriture hexadécimale  de l'entier n.
    L'algorithme utilisé est celui de la division en cascade.
    """

Un code possible

def ecritureHexa(n):
    """"
    n -- entier naturel (type int).

    renvoie une chaîne de caractères. 
    Cette chaîne de caractères
    est constituée de "chiffres" hexadécimaux (chiffres  de 0 à 9 et de a à f)
    et elle correspond à l'écriture hexadécimale  de l'entier n.
    L'algorithme utilisé est celui de la division en cascade.
    """
    # traitement du cas  n = 0:
    if n == 0: return '0'

    # définition d'un dictionnaire pour les chiffres hexa:
    chiffres = {10:'a', 11:'b', 12:'c', 13:'d', 14:'e', 15:'f'}
    for i in range(0,10):
        chiffres[i] = str(i)

    # construction de la chaîne écriture hexa:
    ch = ''
    while n != 0:
        ch = chiffres[n % 16] + ch # écriture du nouveau chiffre à gauche des précédents
        n = n//16 # n devient le quotient suivant
    return ch


### TESTS ###

for i in range(100):
    print(f"Ecriture hexadécimale de {i}: {ecritureHexa(i)}.")

Exercice 7

binaire	hexadécimal
0000	0
0001	1
0010	2
0011	3
0100	4
0101	5
0110	6
0111	7
1000	8
1001	9
1010	a
1011	b
1100	c
1101	d
1110	e
1111	f

Écrire un code python générant un dictionnaire correspondance tel que correspondance['0000'] = '0', correspondance['0001'] = '1', ..., correspondance['1111'] = 'f'.

Une aide: la fonction chr

Pour la construction de ce dictionnaire, il est possible (mais pas obligatoire) d'utiliser la fonction python chr. Le résultat du petit script ci-dessous vous permettra de comprendre son rôle:

for k in range(97, 120):
    print(f"chr({k}) = {chr(k)}.")

L'affichage obtenu:

chr(97) = a.
chr(98) = b.
chr(99) = c.
chr(100) = d.
chr(101) = e.
chr(102) = f.
chr(103) = g.
chr(104) = h.
chr(105) = i.
chr(106) = j.
chr(107) = k.
chr(108) = l.
chr(109) = m.
chr(110) = n.
chr(111) = o.
chr(112) = p.
chr(113) = q.
chr(114) = r.
chr(115) = s.
chr(116) = t.
chr(117) = u.
chr(118) = v.
chr(119) = w.

Solution: un code possible

correspondance = {}
for c0 in ('0','1'):
    for c1 in ('0','1'):
        for c2 in ('0','1'):
            for c3 in ('0','1'):
                mot = c3 + c2 + c1 + c0
                hexa = int(c0) + 2 * int(c1) + 2**2 * int(c2) + 2**3 * int(c3)
                if hexa < 10:
                    correspondance[mot] = str(hexa)
                else:
                    correspondance[mot] = chr(hexa + 97 -10)

L'instruction print(correspondance) donne:

{'0000': '0', '1000': '8', '0100': '4', '1100': 'c', 
'0010': '2', '1010': 'a', 
'0110': '6', '1110': 'e', '0001': '1', '1001': '9', 
'0101': '5', '1101': 'd', 
'0011': '3', '1011': 'b', '0111': '7', '1111': 'f'}

Exercice 8.

Écrire un corps possible pour la fonction python suivante:

def bin2hexa(n):
    """
    n -- type str, composé de '0' et de '1', 
    c'est l'écriture binaire d'un entier naturel.

    renvoie une chaîne correspondant 
    à l'écriture hexadécimale de n
    en procèdant comme ci-dessus.
    """

Un code solution possible

On utilise le dictionnaire correspondance défini plus haut.

bits = ('0', '1')
binaires = [c3+c2+c1+c0 for c0 in bits for c1 in bits for c2 in bits for c3 in bits]



correspondance = {}
for m in binaires:
    hexa = int(m[3]) + 2 * int(m[2]) + 2**2 * int(m[1]) + 2**3 * int(m[0])
    if hexa < 10:
        correspondance[m] = str(hexa)
    else:
        correspondance[m] = chr(hexa + 97 -10)




def complete(n):
    """
    n -- chaîne de '0' et de '1'.

    renvoie la chaîne avec des '0' à gauche supplémentaires 
    éventuels pour que la 
    chaîne soit de longueur multiple de 4.
    """
    lg = len(n)
    lg = lg%4
    if lg == 0:
        return n
    else:
        return '0' * (4 - lg%4) + n




def bin2hexa(n):
    """
    n -- type str, composé de '0' et de '1', 
    c'est l'écriture binaire d'un entier naturel.

    renvoie une chaîne correspondant 
    à l'écriture hexadécimale de n.
    """
    n = complete(n)
    ch = ''
    for k in range(0, len(n), 4):
        ch = ch + correspondance[n[k:k+4]]
    return ch


# essai:
print(bin2hexa('1000010'))