Algorithmique en seconde et Python
Cette page reprend des énoncés et des algorithmes en pseudo-code de documents ressources pour la classe de seconde
faits par Éduscol. J'y ai rajouté des propositions de codes en Python.
Les images du chocolat
En achetant une tablette de chocolat, on obtient de façon aléatoire une image d'une collection de 6.
On s'intéresse au nombre de tablettes à acheter pour les obtenir toutes.
Une autre formulation:
On souhaite estimer le nombre de lancers nécessaires pour sortir toutes les faces d'un dé cubique
Algorithme chocolat
Variables
L liste
S,n,x entiers
Initialisations
Vider la liste L
S et n prennent la valeur 0
Traitement
Tant que n est inférieur à 6
S prend la valeur S+1
x prend la valeur d'un nombre aléatoire entre 1 et 6
si x ne figure pas dans la liste L alors
n prend la valeur n+1
L(n) prend la valeur x
Fin du Tant que
Sorties
Afficher S
from random import *
from math import *
L=[]
S=0
n=0
while n<6:
S=S+1
x=1+int(floor(random()*6))
if x not in L:
n=n+1
L.append(x)
print S
complément : évaluer avec 100 000 simulations le nombre moyen de tablettes à acheter, faire un diagramme en boîte
résumant les 100 000 simulations.
Les sauts de puce
Une puce se déplace sur un axe gradué, elle part de l'origine et se déplace de manière aléatoire et équiprobable vers la droite ou vers la gauche. Quelle est sa position après 30 sauts.
Algorithme puce
Variables
x,i entiers
Initialisations
x prend la valeur 0
Traitement
Pour i variant de 1 à 30
Si alea<0,5
alors x prend la valeur x+1
sinon x prend la valeur x-1
Fin du Si
Fin du Pour
Sorties
Afficher x
from random import *
x=0
for i in range(30):
if random()<0.5:
x=x+1
else :
x=x-1
print x
complément : évaluer avec 1 000 simulations la probabilité de se retrouver à l'origine au bout de 30 sauts
complément : évaluer avec 1 000 simulations la probabilité de ne jamais repasser par l'origine en 30 sauts.
from random import *
def repasse():
d=0
x=0
for i in range(30):
if random()<0.5:
x=x+1
else:
x=x-1
if x==0:
d=1
return d
nbrep=0
for j in range(1000):
nbrep+=repasse()
proba=(1000.0-nbrep)/1000
print proba
Les coïncidences de dates d'anniversaire dans une classe
Quelle est la probabilité que dans une classe de 30 élèves, il y ait au moins deux élèves qui partagent la même date d'anniversaire?
Algorithme anniversaire
Variables
dates: tableau des trentes jours d'anniversaire
trouvé; un booléen qui indique si deux dates coïncident
k,p:deux compteurs de boucles
Initialisations
Pour k de 0 à 29
dates[k] prend une valeur entière aléatoire comprise entre 1 et 365 inclus
trouvé prend la valeur faux
Traitement
Pour k de 0 à 28
Pour p de k+1 à 29
si date[k]=date[p] alors
trouvé prend la valeur vrai
Sorties
Afficher trouvé
from random import *
from math import *
dates=[int(1+floor(365*random())) for i in range(30)]
trouve=False
for k in range(29):
for p in range(k+1,30):
if dates[k]==dates[p]:
trouve=True
print trouve
On peut essayer d'améliorer l'algorithme et le faire s'arrêter dès qu'une coincidence est trouvée
from random import *
c=[]
d=0
i=0
while d==0 and i<30:
a=randint(1,365)
if (a in c):
d=1
print "coincidence"
else:
c.append(a)
i=i+1
if (d==0):
print "pas de coincidence"
complément : créer la liste des élèves ayant un anniversaire le même jour qu'un de ses camarades de classe;
(le premier élément de la liste est l'élève 1, etc.
Parité
Deux entreprises A et B recrutent dans un bassin d'emploi où il y a autant d'hommes que de femmes, avec la contrainte du respect de la parité.
Dans l'entreprise A, il y a 43 femmes sur 100 employé et dans l'entreprise B, il y a 1150 femmes sur 2500.
Faire l'hypothèse que deux entreprises C et D ayant respectivement 100 et 2500 employés respectent à chaque embauche la parité
et faire l'expérience de 10000 simulations pour chaque entreprise; chercher le nombre de simulations sur 1000 donnant pour l'entreprise A
un nombre de femmes inférieur ou égal à 43 et pour l'entreprise B un nombre de femmes inférieur ou égal à 1150.
from random import *
from math import *
def sima():
A=[int(floor(2*random())) for k in range(100)]
femmeA=sum(A)
return femmeA
def simb():
B=[int(floor(2*random())) for k in range(2500)]
femmeB=sum(B)
return femmeB
simA=[sima() for i in range(10000) ]
simA=[x for x in simA if x<=43]
print len(simA)
simB=[simb() for i in range(10000) ]
simB=[x for x in simB if x<=1150]
print len(simB)
On trouve qu'environ 9% des simulations donnent un nombre de femmes inférieur ou égal à 43 pour l'entreprise A
et environ 0,01% des simulations donnent un nombre de femmes inférieur ou égal à 1150 pour l'entreprise B.
Il paraît raisonnable de rejeter l'hypothèse que l'entreprise B pratique la parité.
fait le 18 janvier 2010