Page 66 - 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
Objectif 3 : une combinaison au hasard
Pour tirer une partie de k éléments d’un ensemble donné (ici décrit par une liste L), nous pouvons aussi procéder de manière récursive. S’il s’agit de tirer une partie vide (k=0), c’est immédiatement réglé.
Sinon, on tire au hasard un
élément de L. Ce choix est
effectué par l’instruction randint(0,len(L)-1) ;
puis on le retire de L (grâce à l’appel L.pop).
Si L est une liste comme [2,3,5],
L.pop(1) fait deux choses :
– retirer le deuxième élément de L
Si L est une liste, l’appel sorted(L) renvoie une liste triée ayant les mêmes éléments que L.
– renvoyer cet élément (ici, 3).
Il ne reste plus qu’à tirer k-1 éléments de la liste restante, ce que est réalisé par l’appel récursif combalea(k-1,L).
Pour fournir la réponse, on met l’élément tiré au hasard en tête (ce que fait l’instruction [ch]+K) puis on trie le tout (appel de la fonction sorted) pour éviter de présenter comme différentes des réponses ne se distinguant que par l’ordre.
Une fois que l’idée est formulée, il n’y a aucune difficulté à reprendre l’algorithme et à le programmer de manière itérative (non récursive) : on accumule de proche en proche les éléments tirés (au hasard) de L dans une liste C initialement vide ; il ne reste plus qu’à renvoyer cette liste, triée.
64
Ce document est mis à disposition sous licence Creative Commons
© Texas Instruments 2021 / Photocopie autorisée