Boucle for et accumulateur☘
Le principe d'accumulation exposé dans les exercices ci-dessous est un principe important à connaître parfaitement.
Traitez
ces exercices jusqu'à être certain d'être capable de les programmer vous-même.
Exercice☘
Écrire une fonction prenant en paramètre un entier naturel n et renvoyant en sortie la somme des entiers de 0 à n: S = 0 + 1 + 2 + ... + n.
Aide: le principe
On crée une variable S initialisée à 0 dans laquelle on va ajouter (accumuler) un à un tous les termes.
Si je dois ajouter tous les entiers de 1 à 5 dans la variable S, je peux bien sûr procéder ainsi:
S ← 1 + 2 + 3 + 4 + 5
Le principe que l'on peut généraliser est exposé ci-dessous.
Attention
N'oubliez pas qu'une affectation se lit toujours de la droite vers la gauche: on effectue d'abord l'opération qui se trouve à droite de la flèche ← puis on donne un nom au résultat. C'est cette exécution de droite à gauche qui permet de réutiliser le même nom.
S ← 0
S ← S + 1 # S désigne maintenant la valeur 1
S ← S + 2 # S désigne maintenant la valeur 1+2
S ← S + 3 # S désigne maintenant la valeur 1+2+3
S ← S + 4 # S désigne maintenant la valeur 1+2+3+4
S ← S + 5 # S désigne maintenant la valeur 1+2+3+4+5
Comment généraliser cela? Avec une boucle for bien sûr!
pseudo-code
fonction somme(n):
S ← 0
Pour chaque entier k entre 0 et n:
S ← S + k
renvoyer S
A vous de traduire cela en langage python.
un code python
def somme(n):
"""
n -- entier naturel
renvoie la somme S = 0 + 1 + 2 + ... + n.
"""
S = 0
for i in range(0, n+1):
S += i
return S
On rappelle que l'instruction S += i est un raccourci pour S = S + i
(ce que l'on notera S ← S + i en pseudocode).
Rappelons aussi qu'avec le pseudocode, on écrira que i prend les valeurs de 1 à n, et
que cela se traduit en python par un range(1,n+1)
car la dernière valeur du range n'est pas prise.
Tests:
>>> somme(1)
1
>>> somme(2)
3
>>> somme(3)
6
Décortiquer, comprendre
Pour vérifier le fonctionnement d'un programme, une des solutions consiste à provisoirement glisser des affichages à des endroits clefs du déroulement.
Dans le code ci-dessus, on peut par exemple afficher à chaque fin de passage dans la boucle la valeur de i et la valeur de S et ainsi vérifier que le déroulement est bien celui du principe exposé au départ avant le code.
def somme(n):
"""
n -- entier naturel
renvoie la somme S = 0 + 1 + 2 + ... + n.
"""
S = 0
for i in range(1, n+1):
S += i
print(f"Valeur de S: {S} en fin de passage dans la boucle pour la valeur de i = {i}.")
return S
Et un appel:
>>> somme(4)
Valeur de S: 1 en fin de passage dans la boucle pour la valeur de i = 1.
Valeur de S: 3 en fin de passage dans la boucle pour la valeur de i = 2.
Valeur de S: 6 en fin de passage dans la boucle pour la valeur de i = 3.
Valeur de S: 10 en fin de passage dans la boucle pour la valeur de i = 4.
10
Ce travail d'affichages intermédiaires vous incombe: c'est un travail qui se réalise au fur et à mesure de votre avancée
dans la programmation et qui vous permet de vérifier votre code, de le corriger, de comprendre vos erreurs.
Ce travail d'affichage peut aussi être utile lorsque l'on vous donne un code et que vous avez besoin de le "décomposer"
pour le comprendre.
Attention, après les phases d'écriture du code, à bien penser à supprimer tous les print.
Vérifier son code☘
Lorsqu'un code a été écrit, il faut le vérifier.
Il est nécessaire de commencer par quelques tests.
Pour l'exercice précédent:
- est-ce que S(1) renvoie bien 1 ?
- est-ce que S(2) renvoie bien 3 ?
- est-ce que S(3) renvoie bien 6 ?
- ...
Nous avons exposé précédemment l'idée d'insérer des affichages lors de l'écriture d'une fonction python pour mieux comprendre les intermédiaires mais, attention, il faut être capable de tester "à la main" son code:
- c'est la seule façon de vraiment comprendre le déroulement, comprendre où peut se nicher un bug.
- et c'est, par conséquent, une compétence que l'on vous demande d'acquérir, elle sera évaluée au cours de l'année.
Pour "tester à la main", on déroule le code instruction après instruction et on note l'état de chacune des variables après chaque instruction.
Ci-dessous un tableau que l'on pourrait créer pour détailler le déroulement de l'appel à la fonction somme avec
l'argument 4:
| Appel Somme(4) | |
|---|---|
| Instruction S = 0 |
S ← 0 |
| Boucle for | |
| i = 1 |
|
| Instruction S += i |
S ← S + i soit S ← 0+1 |
| i = 2 | |
| Instruction S += i | S ← S + i soit S ← 0+1+2 |
| i = 3 |
|
| Instruction S += i | S ← S + i soit S ← 0+1+2+3 |
| i = 4 | |
| Instruction S += i | S ← S + i soit S ← 0+1+2+3+4 |
| Fin de la boucle for | |
| Instruction return S | La valeur renvoyée est 0+1+2+3+4 |
Exercice☘
Écrire une fonction prenant en paramètre un entier naturel n > 1 et renvoyant en sortie le produit des entiers de 2 à n: P = 2 × ... × n.
Vous utiliserez pour cela le principe d'accumulateur.
Aide: une question à se poser
Pour une somme, on part avec 0. Pour un produit, quelle sera la valeur initiale ?
Aide: le principe
On crée une variable P initialisée à 1 dans laquelle on va multiplier (accumuler) un à un tous les facteurs.
P ← 1
P ← P * 2 # soit P ← 1*2
P ← P * 3 # soit P ← 1*2*3
P ← P * 4 # soit P ← 1*2*3*4
P ← P * 5 # soit P ← 1*2*3*4*5
...
pseudo-code
fonction factorielle(n):
P ← 1
Pour chaque entier k entre 2 et n:
P ← P * k
renvoyer P
Il vous reste à traduire cela en langage Python.
un code Python
def produit(n):
"""
n -- entier naturel > 1
renvoie le produit 2*3*4*...*n
"""
p = 1
for k in range(2, n+1):
p = p*k
return p
Tests:
>>> produit(2)
2
>>> produit(3)
6
>>> produit(4)
24