Instructions itératives : range, for, while : Différence entre versions

De WikiMéca
Sauter à la navigation Sauter à la recherche
(Invariant et variant de boucle)
 
Ligne 87 : Ligne 87 :
  
 
<math>r</math> est par ailleurs un '''variant de boucle''' et permet de prouver '''la terminaison''' de la boucle. En effet, <math>b</math> est positif et <math>r_{k+1}=r_k-b</math>. <math>r</math> est donc linéairement décroissant et la condition <syntaxhighlight lang="Python" inline>r >= b </syntaxhighlight> sera donc forcement invalidée après un certain nombre d'itérations. '''La boucle est donc finie'''.
 
<math>r</math> est par ailleurs un '''variant de boucle''' et permet de prouver '''la terminaison''' de la boucle. En effet, <math>b</math> est positif et <math>r_{k+1}=r_k-b</math>. <math>r</math> est donc linéairement décroissant et la condition <syntaxhighlight lang="Python" inline>r >= b </syntaxhighlight> sera donc forcement invalidée après un certain nombre d'itérations. '''La boucle est donc finie'''.
 
+
{{DLMC|Informatique}}
 
[[Catégorie : Bases du langage Python ]]
 
[[Catégorie : Bases du langage Python ]]

Version actuelle datée du 16 août 2019 à 02:52

Réaliser une itération, ou encore une boucle, c’est répéter un certain nombre de fois des instructions semblables.

La fonction range

La fonction range énumère une plage de nombres et peut prendre entre 1 et 3 arguments entiers :

  • range(b) énumère les entiers ;
  • range(a, b) énumère les entiers ;
  • range(a, b, c) énumère les entiers où n est le plus grand entier vérifiant .
>>> list(range(10)) 
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
>>> list(range(5, 15))
[5, 6, 7, 8, 9, 10, 11, 12, 13, 14]
>>> list(range(1, 20, 3)) 
[1, 4, 7, 10, 13, 16, 19]

Boucles for (boucles énumérées)

On définit une boucle à l’aide de la fonction for, en suivant la structure suivante :

1 for ... in range(...): 
2     bloc ........................... 
3     d instructions .................

Immédiatement après le mot-clé for doit figurer le nom d’une variable, qui va prendre les différentes valeurs de l’énumération produite par l’instruction range. Pour chacune de ces valeurs, le bloc d’instructions qui suit sera exécuté.

Exemple : fonction somme(n) qui calcule et renvoie la somme des entiers de 1 à n :

1 def somme(n) :
2     s=0
3     for k in range (n+1) :
4         s+=k # ou s=s+k
5     return (s)

Boucles while (boucles conditionnelles)

Une boucle conditionnelle exécute une suite d’instructions tant qu’une certaine condition est réalisée; elle peut donc ne jamais réaliser cette suite d’instructions (lorsque la condition n’est pas réalisée au départ) que les réaliser un nombre infini de fois (lorsque la condition reste éternellement vérifiée). La syntaxe d’une boucle conditionnelle est la suivante :

1 while condition: 
2     bloc ........................... 
3     ................................ 
4     dinstructions .................

Exemple : décompte

1 x = 10
2 while x > 0:
3     print(x, end=' ')
4     x -= 1

affichera :

10 9 8 7 6 5 4 3 2 1 

Interruption du déroulement d'une boucle

Deux fonction permettent d'altérer le déroulement d'une boucle for ou while:

  • break provoque une sortie anticipée de la boucle et
  • continueprocoque le passage immédiat à l'itération suivante.

Invariant et variant de boucle

On appelle invariant de boucle toute assertion vérifiant les conditions suivantes :

  • Initialisation : cette assertion est vraie avant la première itération de la boucle;
  • Conservation : si cette assertion est vraie avant une itération de la boucle, elle le reste avant l’itération suivante;
  • Terminaison : une fois la boucle terminée, l’invariant fournit une propriété utile qui aide à établir/prouver/analyser l’algorithme.

Exemple : algorithme de division euclidienne:

1 def Div_Eucl (a,b) :
2    """ cette fonction calcule le quotient q et le reste r de la division euclidienne de
3    l’entier positif a par l’entier strictement positif b et elle renvoie q,r"""
4    assert (b >0)
5    q,r = 0,a
6    while r >= b :
7        q=q+1
8        r=r-b
9    return q,r

Dans cet exemple, la propriété est un invariant de boucle.

Dans ce qui suit, on notera les valeurs prises par les variables après le ième passage dans la boucle. On remarque que :

  • à l'initialisation de l’algorithme, on a et donc est vérifié;
  • à l’itération , . Or et . Donc à l'itération , on a , ce qui prouve la conservation de l'invariant;
  • avant la dernière itération, et . Ce qui prouve qu'à la sortie de la boucle, est le quotient et le reste.


est par ailleurs un variant de boucle et permet de prouver la terminaison de la boucle. En effet, est positif et . est donc linéairement décroissant et la condition r >= b sera donc forcement invalidée après un certain nombre d'itérations. La boucle est donc finie.

Autres pages de la catégorie "Informatique"

Pages relatives à l'informatique en CPGE scientifiques.

Bases du langage Python

Algorithmes et méthodes numériques‎