Listes

1) Ecrire une liste à l'envers

On veut calculer écrire à l'envers une  liste s d'entiers. Par exemple [1, 2, 4, 2] → [2, 4, 2, 1] .

a) On propose la fonction suivante:

def liste_envers_essai(s):
    n = len(s)
    for i in range(n):
        s[i] = s[n - 1 - i]
    return s

Calculer liste_envers_essai([1, 2, 3, 4, 5]). Expliquer pourquoi  la fonction ne résout pas le problème.

b) Ecrire une fonction liste_envers_1(s) (avec s liste de nombres) calculant la liste s à l'envers (bien sûr sans disposer d'outils comme ceux que propose Python, comme la méthode reverse() ou la fonction reversed()), en utilisant une liste annexe.

c)  Ecrire une fonction liste_envers_2(s) (avec s liste de nombres) calculant la liste s à l'envers, sans utiliser une autre liste que s.

2) Fabriquer une liste

Ecrire une fonction montee_descente(n) (n ∈ N) calculant la liste [1, 2, 3,..., n, n-1, n-2,.., 1].

3) Somme d'une liste

Ecrire une fonction somme_liste(s) (avec s liste de nombres) calculant la somme des termes de s, sans utliliser sum() .

4) Minimum :

Ecrire une fonction minimum(s) (avec s liste de nombres) calculant le plus petit terme de s.

On ne doit pas utiliser la fonction min() ni trier la liste.

5) Médiane d'une liste de nombre triée (par ordre croissant ou décroissant)

Ecrire une fonction mediane(s) (avec s liste de nombres triée) calculant la médiane de s.

Rappel : la médiane d'une liste triée comprenant un nombre impair de termes est le terme au milieu de la liste .
La  médiane d'une liste triée comprenant un nombre pair de termes est la moyenne des deux termes au milieu de la liste .

6) Moyenne :

Ecrire une fonction moyenne(s) (avec s liste de nombres) calculant la moyenne arithmétique des termes de s. On ne doit pas utiliser la fonction sum() .

7) Ecart type

  Ecrire une fonction ecart_type(s) (avec s liste de nombres) calculant l'écart type des termes de s. On doit faire un unique parcours de la liste.

Rappel : Pour une liste   s = [ s 1 , ... s n ] de nombres de moyenne m l'écart type est   e = s 1 2 + s 2 2 + ... + s n 2 n - m 2 .
Par exemple, ecart_type([1, 2, 5, 8]) = 2.7386127875258306

8)  Le plus grand écart entre deux termes successifs

  Ecrire une fonction plus_grand_ecart(s) (avec s liste de nombres)  calculant le plus grand écart entre deux termes successifs de la liste s. Par exemple: avec s = [1 ,3, 0, 2, 4], on trouve 3 .

9) Sommes partielles d'une série

  On veut écrire une fonction serie(u) (avec u liste de nombres) calculant la liste S des sommes partielles de la liste u de nombres. On note n = len(u).

Rappel: si u = [ u 0 , u 1 , ... , u n - 1 ] , alors S = [ S 0 , S 1 , ... , S n - 1 ] avec   S k = Σ i = 0 k u i pour k ≤ n - 1.

Par exemple, avec u = [1, 2, 5, 8] alors S = [1, 3, 8, 16]

On propose la fonction suivante:

def serie_1(u):
    n = len(u)
    S = [0]*n
    for i in range(n):
        for j in range(i + 1):
            S[i] = S[i] + u[j]
    return S

a) Compter le nombre A(n) d'additions de cette fonction et trouver le réel k tel que   A ( n ) + k n 2
b) Proposer une fonction serie_2(u) calculant le même résultat avec A ( n ) + k 1 n .

10) Coefficients du binôme

  On veut écrire une fonction coeff_binome(n) avec n ∈ N, calculant la liste d'entiers [ ( n 0 ) , ( n 1 ) , ..., ( n n ) ] en utilisant la méthode permettant le calcul du triangle de Pascal, basée sur des additions en exploitant la formule   ( m k ) = ( m - 1 k - 1 ) + ( m - 1 k ) .
On propose l'algorithme suivant:

def coeff_binome_1(n):
    res = [0] * (n + 1)
    res[0] = 1
    for m in range(1, n + 1):
        for k in range(1, m + 1):
            res[k] = res[k-1] + res[k]
    return res

a) Exécuter la fonction pour n = 5. Vérifier que la réponse (vous devez trouvez [1, 5, 14, 28, 42, 42]) n'est pas correcte (on devrait avoir comme réponse [1, 5, 10, 10, 5, 1]).

b) Quel est la cause du dysfonctionnement ?

c) Proposer une petite modification (sans introduire de liste supplémentaire) de cette fonction  de manière à résoudre correctement le problème.

d) Modifier la fonction pour qu'elle affiche le triangle de Pascal d'ordre n complet .

11) Plus longue sous liste croissante

Ecrire une fonction pgslc(s) avec s liste de nombres calculant la plus longue sous liste croissante de la liste s.
En cas d'égalités, on doit renvoyer la première sous liste trouvée.

Par exemple:

s = [1, 3, 1, 5] →  [1, 3]
s = [1, 3, 7, 2, 5, 6, 6, 6, 8, 8, 7] → [2, 5, 6, 6, 6, 8, 8]

12) Extremums

Ecrire une fonction extremum(s) avec s liste de nombres calculant la liste E des extremums successifs de la liste s.

Par exemple:

s = [1, 1, 1] → E = [1]
s = [1, 3, 3, 1] → E = [1, 3, 1]
s = [1, 3, 7, 2, 5, 6, 6, 6, 8, 8] → E = [1, 7, 2, 8]

© 2014 - Eric Obermeyer      Powered by      Corrigé