Chapitre 1 : Numérotations | Table des matières |
Voici le code de fonctions de numérotation pour les couples et les triplets
struct couple { int x, y; }; struct triplet { int x, y, z; }; typedef struct couple couple; typedef struct triplet triplet; /* Numérotation des couples */ int numeroCouple (couple c) { int d = c.x + c.y; return d * (d + 1) / 2 + c.y; } couple coupleNumero (int n) { int d, t = 0; couple c; for (d = 1; ; d++) { t = t + d; if (t > n) break; } /* reculer */ t = t - d; d--; c.y = n - t; c.x = d - c.y; return c; } /* conversions entre couples et triplets */ couple t2c (triplet t) { couple c = {t.x, t.y}; int n = numeroCouple (c); c.x = n; c.y = t.z; return c; } triplet c2t (couple c) { triplet t; t.z = c.y; c = coupleNumero (c.x); t.x = c.x; t.y = c.y; return t; } int numeroTriplet (triplet t) { return numeroCouple (t2c (t)); } triplet tripletNumero (int n) { return c2t (coupleNumero (n)); }
Voici le début de la numérotation des couples et triplets :
0 -> (0, 0) -> (0, 0, 0) -> 0 1 -> (1, 0) -> (1, 0, 0) -> 1 2 -> (0, 1) -> (0, 0, 1) -> 2 3 -> (2, 0) -> (0, 1, 0) -> 3 4 -> (1, 1) -> (1, 0, 1) -> 4 5 -> (0, 2) -> (0, 0, 2) -> 5 6 -> (3, 0) -> (2, 0, 0) -> 6 7 -> (2, 1) -> (0, 1, 1) -> 7 8 -> (1, 2) -> (1, 0, 2) -> 8 9 -> (0, 3) -> (0, 0, 3) -> 9 10 -> (4, 0) -> (1, 1, 0) -> 10 11 -> (3, 1) -> (2, 0, 1) -> 11 12 -> (2, 2) -> (0, 1, 2) -> 12 13 -> (1, 3) -> (1, 0, 3) -> 13 14 -> (0, 4) -> (0, 0, 4) -> 14 15 -> (5, 0) -> (0, 2, 0) -> 15 16 -> (4, 1) -> (1, 1, 1) -> 16 17 -> (3, 2) -> (2, 0, 2) -> 17 18 -> (2, 3) -> (0, 1, 3) -> 18 19 -> (1, 4) -> (1, 0, 4) -> 19 20 -> (0, 5) -> (0, 0, 5) -> 20 21 -> (6, 0) -> (3, 0, 0) -> 21 22 -> (5, 1) -> (0, 2, 1) -> 22 23 -> (4, 2) -> (1, 1, 2) -> 23 24 -> (3, 3) -> (2, 0, 3) -> 24
Voici le code de fonctions de numérotation pour les listes. Celles-ci, dans le code ci-dessous, ont une taille fixe, choisie en accord avec la taille des entiers C (type int) sur les machines courantes (32 bits), taille qui limite sévèrement les numérotations de listes ; noter que par exemple x + y + 2 bits sont nécessaires, avec l'algorithme ci-dessous, pour le numéro de la liste à deux éléments x et y. Maple, qui possède un type standard liste, et manipule des entiers de taille quelconque, serait un langage préférable pour réaliser la numérotation des listes, ce qui n'empêcherait pas d'atteindre rapidement les limites pratiques de l'algorithme (comme souvent en calculabilité), puisque le nombre de bits du numéro est déterminé essentiellement par la somme des entiers qui composent la liste.
struct liste { int taille; int element [32]; }; typedef struct liste liste; int numeroListe (liste u) { int i, j, n = 0; for (i = u.taille - 1; i >= 0; i--) { n = 2 * n + 1; for (j = 0; j < u.element [i]; j++) n = 2 * n; } return n; } liste listeNumero (int n) { int t = 0, x = 0; liste u; while (n > 0) { if (n % 2 == 0) x++; else { u.element [t++] = x; x = 0; } n = n / 2; } u.taille = t; return u; }
Voici le début de la numérotation des listes ; on a ajouté l'opération miroir, qui renverse une liste ; la fonction composée, qui associe, sur chaque ligne ci-dessous, l'entier le plus à droite à l'entier le plus à gauche, est la traduction "arithmétique" du miroir ; ceci illustre le principe selon lequel toute procédure informatique peut être vue comme calculant une fonction N → N.
0 -> [] -> [] -> 0 1 -> [0] -> [0] -> 1 2 -> [1] -> [1] -> 2 3 -> [0, 0] -> [0, 0] -> 3 4 -> [2] -> [2] -> 4 5 -> [1, 0] -> [0, 1] -> 6 6 -> [0, 1] -> [1, 0] -> 5 7 -> [0, 0, 0] -> [0, 0, 0] -> 7 8 -> [3] -> [3] -> 8 9 -> [2, 0] -> [0, 2] -> 12 10 -> [1, 1] -> [1, 1] -> 10 11 -> [1, 0, 0] -> [0, 0, 1] -> 14 12 -> [0, 2] -> [2, 0] -> 9 13 -> [0, 1, 0] -> [0, 1, 0] -> 13 14 -> [0, 0, 1] -> [1, 0, 0] -> 11 15 -> [0, 0, 0, 0] -> [0, 0, 0, 0] -> 15 16 -> [4] -> [4] -> 16 17 -> [3, 0] -> [0, 3] -> 24 18 -> [2, 1] -> [1, 2] -> 20 19 -> [2, 0, 0] -> [0, 0, 2] -> 28 20 -> [1, 2] -> [2, 1] -> 18 21 -> [1, 1, 0] -> [0, 1, 1] -> 26 22 -> [1, 0, 1] -> [1, 0, 1] -> 22 23 -> [1, 0, 0, 0] -> [0, 0, 0, 1] -> 30 24 -> [0, 3] -> [3, 0] -> 17
Voici des exemples de listes avec de "grands" numéros (on pourra méditer sur les codes hexadécimaux de 1000000 et 528919, à savoir f4240 et 81217) :
1000000 -> [0, 0, 0, 1, 4, 2, 6] -> [6, 2, 4, 1, 0, 0, 0] -> 528919 1000001 -> [0, 0, 0, 1, 4, 2, 5, 0] -> [0, 5, 2, 4, 1, 0, 0, 0] -> 791063 1000002 -> [0, 0, 0, 1, 4, 2, 4, 1] -> [1, 4, 2, 4, 1, 0, 0, 0] -> 659991 1000003 -> [0, 0, 0, 1, 4, 2, 4, 0, 0] -> [0, 0, 4, 2, 4, 1, 0, 0, 0] -> 922135 1000004 -> [0, 0, 0, 1, 4, 2, 3, 2] -> [2, 3, 2, 4, 1, 0, 0, 0] -> 594455 1000005 -> [0, 0, 0, 1, 4, 2, 3, 1, 0] -> [0, 1, 3, 2, 4, 1, 0, 0, 0] -> 856599 1000006 -> [0, 0, 0, 1, 4, 2, 3, 0, 1] -> [1, 0, 3, 2, 4, 1, 0, 0, 0] -> 725527 1000007 -> [0, 0, 0, 1, 4, 2, 3, 0, 0, 0] -> [0, 0, 0, 3, 2, 4, 1, 0, 0, 0] -> 987671 1000008 -> [0, 0, 0, 1, 4, 2, 2, 3] -> [3, 2, 2, 4, 1, 0, 0, 0] -> 561687 1000009 -> [0, 0, 0, 1, 4, 2, 2, 2, 0] -> [0, 2, 2, 2, 4, 1, 0, 0, 0] -> 823831 1000010 -> [0, 0, 0, 1, 4, 2, 2, 1, 1] -> [1, 1, 2, 2, 4, 1, 0, 0, 0] -> 692759 1000011 -> [0, 0, 0, 1, 4, 2, 2, 1, 0, 0] -> [0, 0, 1, 2, 2, 4, 1, 0, 0, 0] -> 954903 1000012 -> [0, 0, 0, 1, 4, 2, 2, 0, 2] -> [2, 0, 2, 2, 4, 1, 0, 0, 0] -> 627223 1000013 -> [0, 0, 0, 1, 4, 2, 2, 0, 1, 0] -> [0, 1, 0, 2, 2, 4, 1, 0, 0, 0] -> 889367 1000014 -> [0, 0, 0, 1, 4, 2, 2, 0, 0, 1] -> [1, 0, 0, 2, 2, 4, 1, 0, 0, 0] -> 758295 1000015 -> [0, 0, 0, 1, 4, 2, 2, 0, 0, 0, 0] -> [0, 0, 0, 0, 2, 2, 4, 1, 0, 0, 0] -> 1020439 1000016 -> [0, 0, 0, 1, 4, 2, 1, 4] -> [4, 1, 2, 4, 1, 0, 0, 0] -> 545303
Le type liste est aussi utilisé pour représenter un ensemble.
int numeroEnsemble (liste u) { int i, j, k, n = 0; for (i = u.taille - 1; i >= 0; i--) { n = 2 * n + 1; if (i > 0) k = u.element [i-1] + 1; else k = 0; for (j = k; j < u.element [i]; j++) n = 2 * n; } return n; } liste ensembleNumero (int n) { int i, t = 0; liste u; for (i = 0; n > 0; i++) { if (n % 2) u.element [t++] = i; n = n / 2; } u.taille = t; return u; }
Voici le début de la numérotation des ensembles :
0 -> [] 1 -> [0] 2 -> [1] 3 -> [1, 0] 4 -> [2] 5 -> [2, 0] 6 -> [2, 1] 7 -> [2, 1, 0] 8 -> [3] 9 -> [3, 0] 10 -> [3, 1] 11 -> [3, 1, 0] 12 -> [3, 2] 13 -> [3, 2, 0] 14 -> [3, 2, 1] 15 -> [3, 2, 1, 0] 16 -> [4] 17 -> [4, 0] 18 -> [4, 1] 19 -> [4, 1, 0] 20 -> [4, 2] 21 -> [4, 2, 0] 22 -> [4, 2, 1] 23 -> [4, 2, 1, 0] 24 -> [4, 3]
Voici les ensembles de numéro voisin de un million (comparer avec les listes correspondantes ci-dessus) :
1000000 -> [19, 18, 17, 16, 14, 9, 6] 1000001 -> [19, 18, 17, 16, 14, 9, 6, 0] 1000002 -> [19, 18, 17, 16, 14, 9, 6, 1] 1000003 -> [19, 18, 17, 16, 14, 9, 6, 1, 0] 1000004 -> [19, 18, 17, 16, 14, 9, 6, 2] 1000005 -> [19, 18, 17, 16, 14, 9, 6, 2, 0] 1000006 -> [19, 18, 17, 16, 14, 9, 6, 2, 1] 1000007 -> [19, 18, 17, 16, 14, 9, 6, 2, 1, 0] 1000008 -> [19, 18, 17, 16, 14, 9, 6, 3] 1000009 -> [19, 18, 17, 16, 14, 9, 6, 3, 0] 1000010 -> [19, 18, 17, 16, 14, 9, 6, 3, 1] 1000011 -> [19, 18, 17, 16, 14, 9, 6, 3, 1, 0] 1000012 -> [19, 18, 17, 16, 14, 9, 6, 3, 2] 1000013 -> [19, 18, 17, 16, 14, 9, 6, 3, 2, 0] 1000014 -> [19, 18, 17, 16, 14, 9, 6, 3, 2, 1] 1000015 -> [19, 18, 17, 16, 14, 9, 6, 3, 2, 1, 0] 1000016 -> [19, 18, 17, 16, 14, 9, 6, 4]
Note. Un lecteur attentif remarquera que, dans tous les exemples ci-dessus, les listes (qui servent aussi à représenter des ensembles) sont affichées dans l'ordre inverse de leur implantation en mémoire (autrement dit l'élément d'indice 0 est affiché en dernier) ; ainsi, les entiers affichés en tête de liste sont ceux "de poids fort", qui varient le moins vite lors d'une énumération ; c'est la même convention que pour l'écriture des chiffres d'un nombre (on écrit en premier, c'est à dire à gauche, les chiffres de poids fort d'un nombre).