Algorithme programmation et suites

Merci !

Fiches
Classe(s) : Tle ST2S - Tle STI2D - Tle STL - Tle STMG | Thème(s) : Suites numériques

A Notion de liste en informatique

DÉFINITION

Une liste en informatique est une collection ordonnée d’éléments (entiers, flottants, chaînes de caractères, booléens…) séparés par des virgules et mis entre crochets.

EXEMPLE

L = [2, 3, 5, 8, 13] est une liste de 5 entiers, distincte de la liste [3, 2, 5, 8, 13].

notes = [1e3, 12, 9.5, 18] est une liste de 4 éléments :

une chaîne de caractère (1e3), deux entiers (12 et 18) et un flottant (9.5).

Remarques

Une liste d’entiers ou de flottants peut représenter une suite numérique comme la liste L.

On peut visualiser une liste comme une série de « boîtes » dans lesquelles chaque élément de la liste est rangé. Les boîtes sont numérotées par un indice.

Attention : la numérotation commence à 0.

notes = ['1e3', 12, 9.5, 18]

15400_C01_15

EXEMPLE

L’élément d’indice 0 de L, noté L[0], a pour valeur 2 ; L[1] a pour valeur 3 ; L[4] a pour valeur 13.

notes[0] a pour valeur 1e3, notes[1] a pour valeur 12, notes[3] a pour valeur 18.

Générer une liste

Voyons d’abord le cas particulier de la fonction range. L’instruction range(6) permet de générer la liste [0, 1, 2, 3, 4, 5] (faire list(range(6)) pour afficher la liste) et range(1, 6) permet de générer la liste [1, 2, 3, 4, 5].

Attention : range(n) correspond à la liste des entiers de 0 à n 1 et range(n, m) à celle des entiers de n à m 1.

Une liste peut être générée « en extension », c’est-à-dire en écrivant l’ensemble de ses éléments.

EXEMPLE

jours = [lundi, mardi, mercredi, jeudi, vendredi]

On peut également générer une liste par ajouts successifs d’un élément. L’instruction L.append(x) ajoute x à la fin de la liste L (append signifie « ajouter » en anglais).

EXEMPLES

L’instruction jours.append(samedi) crée la liste :

[lundi, mardi, mercredi, jeudi, vendredi, samedi].

Le programme suivant crée la liste [2, 4, 6, 8, 10].

Image dont le contenu est L = []for	k in range(1, 6):	L.append(2 * k); Fin de l'image

On peut aussi générer une liste « en compréhension », notamment par une formule définissant ses éléments.

EXEMPLES

L’instruction L = [2 * n for n in range(1,6)] crée la liste [2, 4, 6, 8, 10].

On peut ajouter une condition dans laquelle != signifie ≠.

L’instruction L = [2 * n for n in range(1,6) if n !=3] crée la liste [2, 4, 8, 10].

Manipuler des éléments d’une liste et leur indice

Le tableau suivant résume les principales manipulations sur les éléments d’une liste.

On considère la liste L = [2, 4, 6, 8, 10].

Tableau de 6 lignes, 3 colonnes ;Corps du tableau de 6 lignes ;Ligne 1 : Objectif; Instruction; Résultat; Ligne 2 : Obtenir le 3e élément de la liste, d’indice 2.; L[2]; 6; Ligne 3 : Donner le nombre d’éléments de la liste.; len(L); 5; Ligne 4 : Rechercher l’indice d’un élément de la liste.; L.index(8); 3; Ligne 5 : Ajouter le nombre 12 à la liste.; L.append(12); [2, 4, 6, 8, 10, 12]; Ligne 6 : Supprimer l’élément d’indice 2.; del L[2]; [2, 4, 8, 10, 12];

Parcourir les éléments d’une liste

Pour parcourir un à un les éléments x d’une liste L, on utilise for x in L:.

EXEMPLE

Le programme suivant calcule la somme des nombres de la liste pairs.

Image dont le contenu est pairs = [2, 4, 6, 8, 10]somme = 0for	i in pairs:	somme = somme + i; Fin de l'image

La valeur de la variable somme en fin d’exécution est 30.

B Suites et situations algorithmiques

Calculer un terme de rang donné d’une suite définie par récurrence

On considère la suite (un) définie par u0 = 1 et, pour tout entier naturel n, un+1 = 2un + 3. On souhaite calculer u20.

Avec un tableur

Comme ci-dessous, on entre en B2 la valeur de u0 et en B3 la formule =2*B2+3 correspondant à la relation de récurrence.

On recopie la cellule B3 vers le bas jusqu’en B22.

La cellule B22 affiche la valeur de u20 = 4 194 301.

15400_C01_16

Avec Python

Tableau de 2 lignes, 2 colonnes ;Corps du tableau de 2 lignes ;Ligne 1 : Langage naturel; Python; Ligne 2 : u ← 1Pour k de 1 à 20u ← 2u + 3Fin Pour; u = 1for k in range(1, 21): u = 2 * u + 3;

En fin d’algorithme, la variable u contient la valeur de u20. Le programme Python fournit la valeur 4 194 301.

Attention, en Python range(1, 21) correspond à la liste des entiers consécutifs de 1 à 20. Pour que la boucle for s’exécute 20 fois, il faut donc indiquer range(1, 21).

Déterminer et représenter une liste de termes

 Cas d’une suite définie par son terme général

On considère la suite (un) définie, pour tout entier naturel n, par un = n2. On souhaite calculer et représenter en Python les termes de u0 à u10.

On peut exécuter l’un des deux programmes suivants qui utilisent le module matplotlib.pyplot de représentation graphique.

Tableau de 1 lignes, 1 colonnes ;Corps du tableau de 1 lignes ;Ligne 1 : Programme 1import matplotlib.pyplot as pltfor n in range(11):    u = n**2    plt.scatter(n,u)plt.show()Programme 2import matplotlib.pyplot as pltL = [n**2 for n in range(11)]plt.scatter(range(11), L)plt.show();

 Dans le programme 1, comme lorsque la représentation graphique est réalisée à la main, la boucle for calcule l’ordonnée d’un point et le représente avant de passer au point suivant.

L’instruction plt.scatter(n,u) représente le point de coordonnées (n,u).

REMARQUE

Ce programme est présenté ici pour introduire de façon progressive l’utilisation du langage Python dans l’étude des suites.

 Le programme 2 commence par dresser la liste de toutes les ordonnées des points à ­tracer.

La liste L est : [0, 1, 4, 9, 16, 25, 36, 49, 64, 81, 100].

Les points sont ensuite représentés. L’instruction plt.scatter(range(11), L) représente le « nuage de points » dont les abscisses sont données par la liste range(11) et les ordonnées par la liste L. Le mot « scatter » signifie disperser en anglais.

REMARQUE

C’est ce programme que nous utiliserons désormais pour faciliter l’appropriation de la notion de liste en informatique.

Voir la figure 1 page suivante.

 Cas d’une suite définie par récurrence

EXEMPLE

On considère la suite (un) définie par u0=34 et, pour tout entier naturel n, un+1 = un2.

On souhaite calculer et représenter avec Python les termes de u0 à u5.

On exécute le programme suivant.

Tableau de 1 lignes, 1 colonnes ;Corps du tableau de 1 lignes ;Ligne 1 : Programmeimport matplotlib.pyplot as pltu = 3/4L = [u]for k in range(1, 6): u = u ** 2 L.append(u)plt.scatter(range(6), L)plt.show()La liste L est : [0.75, 0.5625, 0.31640625, 0.1001129150390625,0.010022595757618546, 0.00010045242572063329].;

Remarque

On rappelle que l’instruction 'L.append(u)' ajoute u à la fin de la liste L.

Voir la figure 2 ci-dessous.

Image dont le contenu est 	Figure 1	Figure 2  ; Fin de l'image

Algorithme de seuil

EXEMPLE

On considère la suite (un) définie pour tout entier naturel n par un = 0,9n.

On admet que (un) est décroissante et on recherche le plus petit entier n pour lequel un ≤ 0,5.

On ne sait pas combien d’itérations seront nécessaires, on utilise donc une boucle while avec un compteur qui s’incrémente tant que un est supérieur à 0,5.

Tableau de 2 lignes, 2 colonnes ;Corps du tableau de 2 lignes ;Ligne 1 : Langage naturel; Python; Ligne 2 : n ← 0Tant que 0,9n > 0,5n ← n + 1Fin Tant que; n = 0while 0.9 ** n > 0.5: n = n + 1;

La valeur de la variable n en fin de programme est 7. On en déduit que 0,97 est la plus petite puissance de 0,9 inférieure ou égale à 0,5.

Calculer une somme écrite à l’aide du symbole Σ

On considère la suite des carrés définie pour tout entier naturel k par uk = k2. Pour un entier naturel n non nul, on souhaite calculer la somme sn des n premiers carrés :

sn = k=1nuk = k=1nk2 = 12 + 22 + … + n2.

 Avec un tableur

Comme ci-contre, on calcule en colonne B les valeurs de uk en entrant en B2, dans cet exemple, la formule =A2^2 que l’on recopie vers le bas.

En colonne C, on calcule les valeurs de sk. En C2, on entre la formule =B2. Puis en C3, pour cumuler les valeurs de la colonne B, on entre la formule =C2+B3 que l’on recopie vers le bas.

Il faut recopier vers le bas jusqu’à la valeur n désirée. Par exemple, pour n = 7, on lit s7 = 140.

15789_capture_1

 Avec une fonction en Python utilisant une boucle

La fonction en Python suivante a pour argument un entier n et renvoie la valeur de sn = k=1nk2.

Tableau de 2 lignes, 2 colonnes ;Corps du tableau de 2 lignes ;Ligne 1 : Langage naturel; Python; Ligne 2 : s ← 0Pour k de 1 à n    s ← s + k2Fin PourRenvoyer s; def somme(n):    s = 0    for k in range(1, n + 1):        s = s + k ** 2    return s;

REMARQUE

La variable k est le « compteur » de la boucle. Ses valeurs de début et de fin correspondent à ce qui est indiqué en bas et en haut du symbole Σ. Attention, en Python, k=1ncorrespond à range(1, n + 1).

La variable s est l’« accumulateur » dans lequel on ajoute la valeur de uk à chaque tour de la boucle. L’accumulateur est initialisé à 0.

 Avec une fonction en Python utilisant une liste en compréhension

La fonction sum, qui fait la somme des termes d’une liste, permet d’éviter le recours à une boucle et à un accumulateur. On utilise alors une liste définie en compréhension comme ci-dessous.

Image dont le contenu est     def somme(n):        return sum([k ** 2 for k in range(1, n + 1)]); Fin de l'image

#doc

Memento Python

foucherconnect.fr/pbst2s65