(le fichier est ici: algos_au_programme.py)
1. recherche dans une liste
def recherche_dans_liste(x,l):
for k in range(len(l)):
if x == l[k]: return(True)
return(False)
(aparté pour les informaticiens:
# pour tester agréablement les fonctions lorsqu'on
# exécute le fichier dans python(x,y) par exemple
# test(f,a1,...,an) affiche le résultat de f(a1_,...,an)
# précédé du nom de f et de ses arguments
import re
def test(f,*args):
s = str(f)
nomf = re.split(' ',s)[1]
print(nomf, args)
print('donne: '+ str(f(*args)))
fin de l'aparté)
# testons la fonction recherche_dans_liste
test(recherche_dans_liste,'charlie',[4,2,'charlie',6])
# on note au passage que les listes de python ne sont pas homogènes
test(recherche_dans_liste,0,[2,1,2,3])
2. recherche du maximum dans une liste de nombres
def maximum_liste(l):
m = None # j'avais mis -sys.maxint, Marc a mieux
for x in l: m = max(m,x)
return(m)
test(maximum_liste,[3,5,0,4])
test(maximum_liste,[])
3. calcul de la moyenne et de la variance.
def moyenne_liste(l):
return(sum(l)/len(l))
Si $l=[x_1,\ldots,x_n]$, la variance de $l$ est $\sigma^2=\cfrac 1 n \sum_{i=1}^n (x_i - x)^2$, avec $x=\cfrac 1 n \sum_{i=1}^n x_i$ la moyenne de $l$ (révisons pour l'année prochaine...:)).
def variance_liste(l):
m = moyenne_liste(l)
return(sum([(x-m)**2 for x in l])/len(l))
test(moyenne_liste,[1,2,3,4,5])
test(variance_liste,[1,2,3,4,5])
3. recherche par dichotomie dans un tableau trié.
On va dire que tableau = liste
Rend i tel que t[i] = x
def recherche_dans_tableau_trie(x,t):
if len(t) == 0: return(None)
a = 0
b = len(t)-1
while a <= b:
c = int((a+b)/2)
if x == t[c]: return(c)
elif x < t[c]: b = c - 1
else: a = c + 1
return None
test(recherche_dans_tableau_trie,2,[0,1,2,3,4])
test(recherche_dans_tableau_trie,2,[0,1,3,4])
test(recherche_dans_tableau_trie,2,[])
4. recherche par dichotomie du zéro d’une fonction continue et monotone.
f est la fonction, [a,b] est l'intervalle de recherche
et p est la précision: on s'arrête quand b-a < 10^(-p)
def recherche_zero_dichotomie(f,a,b,p):
precision = 10**(-p)
if f(a)*f(b) > 0: return(None)
while b-a > precision:
c = (a+b)/2.
if f(a)*f(c) > 0: a = c
else: b = c
return(a)
# en python, la fonction x |---> 1-x s'écrit lambda(x): 1-x
test(recherche_zero_dichotomie,lambda(x): 1-x,0,2,5)
test(recherche_zero_dichotomie,lambda(x): log(x)-1,1,3,10)
5. méthodes des rectangles et des trapèzes pour le calcul approché d’une intégrale sur un segment.
La précision est la largeur maximale des rectangles: 10^(-p)
def integrale_approchee_rectangle(f,a,b,p):
dx = 10.**(-p)
n = int((b-a)/dx)
aire = 0.
k = 0
while k < n: # on aurait pu utiliser un for mais le range aurait pu
# être trop gros et faire planter le système ...
aire = aire + f(a+k*dx)*dx
k = k+1
return(aire)
test(integrale_approchee_rectangle,lambda x: x,0,1,5)
# calcul de Pi
test(integrale_approchee_rectangle,lambda x: 4/(1+x**2),0,1,6)
def integrale_approchee_trapeze(f,a,b,p):
dx = 10.**(-p)
n = int((b-a)/dx)
aire = 0.
k = 0
while k < n:
ak = a+k*dx
aire = aire + (f(ak)+f(ak+dx))/2*dx
k = k+1
return(aire)
test(integrale_approchee_trapeze,lambda x: x,0,1,5)
# calcul de Pi, bien meilleur qu'avec les rectangles
test(integrale_approchee_trapeze,lambda x: 4/(1+x**2),0,1,6)
6. recherche d’un mot dans une chaîne de caractères.
Rend le rang dans la chaîne où commence le mot m s'il existe, sinon rend None
def recherche_mot(m,s):
p = len(m)
n = len(s)
for k in range(n-p+1):
i = 0
while i < p:
if m[i] != s[k+i]: i = p
elif i == p-1: return(k)
else: i = i+1
return(None)
test(recherche_mot,'ab',' ab')
test(recherche_mot,'charlie','ou est charlie dans cette phrase?')
