Page 67 - Activités algorithmiques avec Python en spécialité Mathématiques

Thème : combinatoire & probabilités
TI-83 Premium CE Edition Python TI-82 Advanced Edition Python
Niveau : spécialité maths Terminale
La combinatoire des parties
L. DIDIER & R. CABANE
Pour aller plus loin
Et la représentation binaire ? (objectif 4)
Il s’agit de ce qui est évoqué au programme par le « lien avec les n-uplets de {0,1} ». L’idée est la
suivante. Tout nombre entier m peut se décomposer en une somme de puissances de 2, de manière
analogue à la représentation décimale avec les puissances de 10. Les exposants de ces puissances
sont appelés les « bits23 » de m ; ainsi, on a 11=23+2+1 . En choisissant certains des n bits de rangs n
0,1,⋯,n−1, on peut représenter tous les entiers de 0 à 2−1 ; c’est ainsi que le choix d’un sous- n
ensemble de {0,1,...,n−1} revient à choisir un entier inférieur ou égal à 2−1 et à déterminer ses « bits », c’est-à-dire à trouver sa représentation binaire.
Un nouvel objectif apparaît alors : il s’agit d’écrire une fonction Python non récursive renvoyant une liste de toutes les parties (sous-listes) de {0,1,...,n−1}, en s’appuyant sur la représentation binaire de l’entier n .
Objectif 4 : codage en Python
Commençons par la recherche des bits d’un nombre entier m. Le bit le plus aisé à trouver est le bit « de poids faible » c’est-à-dire associé à 1=20 dans l’écriture binaire de m : ce bit vaut 1 si m est impair et 0 sinon. Pour accéder aux autres bits, il suffit de diviser m par 2 : cela fait perdre le bit de poids faible et décale tous les autres bits. La fonction ci-contre réalise ce principe.
C’est ainsi que le choix du nombre 13, dont les bits ont pour rangs 0,
2 et 3, est associé au choix de la partie {0,2,3}⊂{0,1,2,3} . En récu-
pérant les ensembles de bits de tous les entiers compris entre 0 et
n
Les parties apparaissent dans un ordre peu intuitif, mais ce n’est qu’une question de tri.
2 −1 on aura la liste de toutes les parties possibles, ce que la fonction partbin réalise.
23 Abréviation anglaise pour « binary digits », c’est-à-dire chiffres binaires.
Ce document est mis à disposition sous licence Creative Commons 65 © Texas Instruments 2021 / Photocopie autorisée