quelques algorithmes qui pourraient bien être au programme des CPGE l'an prochain

Programmation en python d'algorithmes simples et utiles.
(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?')

test(recherche_mot,'charline','ou est charlie dans cette phrase?')