Ce billet était initialement paru sur le blog Pydéfis.

Manipuler l’écriture d’un nombre dans une certaine base, c’est à dire les symboles ou les valeurs associés à chacun des chiffres qui le composent dans cette base est une tâche courante. On la retrouve dans les problèmes relatifs aux nombres palindromes par exemple.

Manipuler l’écriture d’un nombre dans une certaine base, c’est-à-dire les symboles ou les valeurs associés à chacun des chiffres qui le composent dans cette base est une tâche courante. On la retrouve dans les problèmes relatifs aux nombres palindromes par exemple.

Méthode standard

La méthode la plus standard, pour obtenir les valeurs de l’écriture des chiffres en base 10 consiste à réaliser des divisions par 10 successives et à relever les restes. À peu près tous les langages permettent de faire ça.

Vous pouvez facilement tester dans un shell Python :

>>> a = 567
>>> a % 10
7
>>> a = a // 10
>>> a
56
>>> a % 10
6
>>> a = a // 10
>>> a % 10
5

Pour obtenir les valeurs de chiffres dans une autre base, il suffit de changer 10 en la base souhaitée. Voici un exemple de fonction qui renvoie une liste contenant les valeurs des chiffres de l’écriture de n dans n’importe quelle base:

def chiffres_base(n, b):
    """ Renvoie le tuple des valeurs des chiffres de n en base b, le
        chiffre le plus significatif en début de liste
    """
    chiffres = []
    while n > 0:
        chiffres.append(n % b)
        n = n // b
    return tuple(reversed(chiffres))

La même chose en C :

int chiffres_base(int n, int b, int chiffres[]) {
    /* Attention, le tableau chiffre doit
       avoir une taille suffisante
    */
    int i = 0;
    while(n>0) {
        chiffres[i++] = n % b;
        n /= b;
    }
    return i;
}

Méthode basée sur les chaînes

Voici une autre façon de procéder, plus spécifique à Python, avec lequel nous disposons en standard d’une méthode pour transformer les nombres en chaînes de caractères (bases 2 et 16 uniquement).

Les méthodes hex(n) et bin(n) permettent d’obtenir sous forme d’une chaîne de caractères les écritures hexadécimales et binaires d’un nombre :

>>> hex(245)
'0xf5'
>>> bin(56)
'0b111000'

La fonction int(x,base) permet, de son côté, de convertir la représentation d’un nombre x depuis n’importe quelle base (raisonnable, ça fonctionne de la base 2 à la base 36), en sa valeur. Les chiffres utilisés sont les lettres de l’alphabet (minuscules ou majuscules) pour les bases strictement supérieurs à 10 (comme il y a 26 lettres, ça permet d’aller jusqu’à la base 36).

>>> int('f5', 16)
245

On peut donc facilement récupérer uniquement les valeurs des chiffres en utilisant tout ça (on enlève ici les 0x et 0b, bien que pour les bases 2 et 16, int puisse s’en accommoder) :

>>> [int(c, 16) for c in hex(245)[2:]]
[15,5]

Les conversions de la base 10 vers les bases autres que 2 ou 16 ne sont pas disponibles dans la librairie standard. Voici une fonction qui réalise ce travail. Elle est inspirée des commentaires du snippet 65212 :

def baseN(n, b) :
    chiffres = "0123456789abcdefghijklmnopqrstuvwxyz"
    if n == 0: 
        return chiffres[0] 
    else :
        return baseN(n // b, b).lstrip(0) + chiffres[n % b]

Notez l’utilisation de lstrip() pour enlever le 0 initial du nombre. Cette fonction fait presque double emploi avec la fonction chiffres_base écrite plus haut. On pourra utiliser l’une ou l’autre selon l’objectif.

On peut maintenant savoir, si un nombre donné n est un palindrome en base 7 (par exemple). Voici les 10 premiers palindromes (de plus de 2 chiffres) de ce type (qui n’étaient par ailleurs pas difficiles à trouver… mais c’est un simple exercice) :

k = int('100', 7)
l = []
while len(l) < 10:
     k7 = baseN(k, 7)
     if k7 == k7[::-1]:
         l.append((k, k7))
     k += 1
print(l)

[(50, '101'),
 (57, '111'),
 (64, '121'),
 (71, '131'),
 (78, '141'),
 (85, '151'),
 (92, '161'),
 (100, '202'),
 (107, '212'),
 (114, '222')]

N’oublions pas … magie de Python… que s’il s’agit uniquement d’obtenir la liste des chiffres de l’écriture en base 10 d’un nombre, c’est immédiat :

>>> [int(c) for c in str(37852)]
[3, 7, 8, 5, 2]

Ces différentes techniques peuvent être utilisées dans les challenges Pydéfis suivants :