Changement de base

I) Présentation

1) Objectif

On étudie l'algorithme de changement de base par des divisions euclidiennes successives.

2) Rappels

  Soient N , b N avec b 2 . Alors N   s'écrit de façon unique N = a n b n + a n - 1 b n - 1 + ... + a 2 b 2 + a 1 b + a 0 avec a i { 0 , ... , b - 1 } .

  Les entiers a n , a n - 1 , ... , a 0 sont alors les chiffres (ou les digits) de N en base b et on note N = ( a n a n - 1 ... a 0 ) b ou N = a n a n - 1 ... a 0 .

En base b >10, on utilise les lettres A,B, C,... pour désigner les chiffres 10, 11, 12,...

3) Exemples

- En base 10, N = 237 s'écrit N = 237 car 237 = 2 10 2 + 3 10 + 7 . Les chiffres de N en base 10 sont 2, 3, 7.
- En base 2, N = 13 s'écrit N =1101 car 13 = 1 2 3 + 1 2 2 + 0 2 + 1 . Les chiffres de N en base 2 sont 1, 1, 0, 1.
- En base 16, N = 100 s'écrit N = 64 car 100 = 6×16 + 4. Les chiffres de N en base 16 sont 6, 4 .
- En base 16, N = 200 s'écrit N = C8 car 200 = 12×16 + 8 . Les chiffres de N en base 16 sont C, 8 .
- En base 36, N = 10 6 s'écrit N = LFLS car 10 6 = 21 36 3 + 15 36 2 + 21 36 + 28 . Les chiffres de N en base 36 sont L, F, L, S.

4) Conversion d'un nombre entier vers une base b par des divisions euclidiennes successives

Les chiffres (de droite à gauche) de l'écriture de N en base b sont les restes successifs r 0 , r 1 , r 2 , ... des divisions par b suivantes jusqu'à avoir un quotient q n nul:
    (1) on divise N par b    : N = q 1 b + r 0
    (2) on divise q 1 par b : q 1 = q 2 b + r 1
    (3) on divise q 2 par b : q 2 = q 3 b + r 2
    Etc...    
    (x) On divise q n - 1 par b : q n - 1 = 0 b + r n
Alors N = ( r n r n - 1 ... r 0 ) b

  En effet:  La suite ( q n ) des quotients successifs est une suite strictement décroissante d'entiers.  Donc il existe un plus petit entier n ∈ N * tel que q n = 0 . Alors l'écriture de N en base b est N = r n r n - 1 ... r 1 .
  Car N = q 1 b + r 0 = ( q 2 b + r 1 ) b + r 0 = q 2 b 2 + r 1 b + r 0 = ( q 3 b + r 2 ) b 2 + r 1 b + r 0 = q 3 b 3 + q 2 b 2 + r 1 b + r 0 = ...= r n b n + r n - 1 b n - 1 + ... + r 2 b 2 + r 1 b + r 0 avec r i { 0 , ... , b - 1 } . Par définition, N = ( r n r n - 1 ... r 0 ) b

Par exemple, voilà le calcul de 46 en base 3 :

46 = 15x3 + 1
15 = 5x3 + 0
5 = 1x3 + 2
1 = 0x3 + 1

Donc 46 =15x3 + 1 = (5x3 + 0)x3 + 1 =  ((1x3 + 2)x3 + 0)x3 + 1 =   1 x3 3 + 2 x3 2 + 0 x3 1 + 1 x3 0   = ( 1201 ) 3 en base 3 .

Q1) Convertir 100 en base 4 et 7777 en base 16

II) Algorithmes de conversion de la base 10 vers la base b

  On donne la fonction base_b(n, b) (avec n , b N et b 2 ) calculant la liste des chiffres en base b de l'entier n par la méthode des divisions euclidiennes successives.

def base_b(n,b):
    """ Calcul itératif de l'écriture de l'entier n en base b"""
    digits = []
    while n > 0:
        digits.append(n % b)        # On ajoute le chiffre en fin de liste
        n = n // b
    digits.reverse()                    # La liste est à l'envers, on la remet à l'endroit
    return digits

Par exemple:

base_b(46,3) = [1, 2, 0, 1]
base_b(1000000,36) = [21, 15, 21, 28]

  On justifie maintenant la terminaison, la correction et on calcule la complexité de cette fonction.

Q2) Démontrer la terminaison de base_b(n, b) pour tous les entiers n et b avec b 2.

Q3) On note digits = digits k = [ c k - 1 , c k - 2 , ... , c 0 ] et n = n k après k itérations de la boucle while. Donc digits 0 = [] et   n 0 = n .
  On note   P = P ( k ) la propriété: Σ i = 0 k - 1 c i b i + n k b k = n . Démontrer que cette propriété P est un invariant de boucle et en déduire la correction de l'algorithme.

Q4) Prouver qu'il y a au plus [ ln ( n ) ln ( b ) ] + 1 itérations de la boucle while”.
On admet que le coût de l'ajout d'un élément à la fin d'une liste est O(1). Démontrer que la complexité de l'algorithme est O ( ln ( n ) )

  Il reste à convertir la liste des chiffres en base b en une chaîne de caractères corrects
  Par exemple, [1, 2, 0, 1] → 1201 en base 3 et [21, 15, 21, 28] → LFLS en base 36 .
  Il faut écrire une fonction caractere(d) (avec d ∈ {0,...,35}), à valeurs dans l'ensemble des chaînes de caractères  telle que caractere(d) = ‘d' pour d ∈ {0,...,9} , caractere(10) = ‘A',..., caractere(35) = ‘Z'.
  On utilise la fonction chr(k) (avec k ∈ N) qui renvoie le caractère de code k dans le standard Unicode (Voir document “Encodage”).
On a: chr(65) = ‘A',  chr(66) = ‘B' ,...,  chr(90) = ‘Z'  et aussi chr(48) = ‘0' , .., chr(57) = ‘9'.

Q5) Ecrire la fonction caractere(d) (avec d ∈ {0,...,35}) ci-dessus.

Q6) Ecrire une fonction ecriture_base_b(n,b) calculant sous forme d'une chaîne de caractères l'écriture de l'entier n en base b avec b ≥ 2.
Par exemple, ecriture_base_b(10**6, 36) = ‘LFLS'

III) Algorithmes de conversion de la base b vers la base 10

  On veut écrire la fonction base_10(s, b) (avec s chaîne de caractères et b ∈ {2,3,...,36}) calculant l'entier n dont l'écriture en base b est la chaîne s.
  On a besoin pour commencer d'une fonction chiffre(c) qui calcule l'entier de {0,...,35} correspondant à c. On peut utiliser pour cela la fonction ord() (avec c caractère) réciproque de la fonction chr().
  Par exemple, ord(‘8') = 56 et ord(‘Y') = 89 .

Q7)  Ecrire une fonction chiffre(c) (avec c ∈ {‘0',..., ‘9', ‘A',..., ‘Z'} ) calcule l'entier n ∈{0,...,35} correspondant à c.
On doit avoir chiffre(‘0') = 0,..., chiffre(‘9') = 9, chiffre(‘A') = 10,..., chiffre(‘Z') = 35.

Q8) Ecrire une fonction Horner(s, b) (avec s liste d'entiers et b entier) calculant l'entier n = Σ k = 0 p - 1 s [ k ] * b p - 1 - k , avec p = len(s) par l'algorithme de Horner très simple à coder qui exploite la remarque n=(...((s[0]*b+s[1])*b+s[2])*b+...+s[p-2])*b+s[p-1].
  Par exemple, si s = [4, 2, 3, 5] et b = 6, n = ( ( 4 * 6 + 2 ) * 6 + 3 ) * 6 + 5 = 959.

Q9) Ecrire une fonction base_10(s, b) calculant l'entier n dont l'écriture en base b ∈ {2,...,36} est la chaîne de caractères s avec les consignes suivantes:

     (1)  Vous devez déjà vérifier que la chaîne s est compatible avec la base b: aucun "chiffre" de s ne doit être supérieur ou égal à b. En cas d'incompatibilité, affichez un message d'erreur.

     (2) Le calcul final de n doit être fait avec l'algorithme de Horner

Par exemple, base_10(‘4235', 6) = 959  et base_10(“ACB”, 12) n'est pas possible.

Q10) En base 36, trouver l'entier N qui s'écrit comme votre nom en majuscules et sans ponctuation.  Par exemple   35784952468373 = ( CONDORCET ) 36

© 2014 - Eric Obermeyer      Powered by      Corrigé