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

De WikiMéca
Sauter à la navigation Sauter à la recherche
(Page créée avec « Réaliser une itération, ou encore une boucle, c’est répéter un certain nombre de fois des instructions semblables. ==La fonction <syntaxhighlight lang="Python" inli... »)
 
(Boucles while (boucles conditionnelles))
(7 révisions intermédiaires par le même utilisateur non affichées)
Ligne 43 : Ligne 43 :
 
'''Exemple :''' décompte
 
'''Exemple :''' décompte
 
<syntaxhighlight lang="Python" line='line'>
 
<syntaxhighlight lang="Python" line='line'>
 +
x = 10
 
while x > 0:
 
while x > 0:
 
     print(x, end=' ')
 
     print(x, end=' ')
     x = 1  
+
     x -= 1  
 
</syntaxhighlight>
 
</syntaxhighlight>
 
affichera :
 
affichera :
Ligne 51 : Ligne 52 :
 
10 9 8 7 6 5 4 3 2 1  
 
10 9 8 7 6 5 4 3 2 1  
 
</pre>
 
</pre>
== Invariant de boucle ==
+
 
 +
== Interruption du déroulement d'une boucle ==
 +
 
 +
Deux fonction permettent d'altérer le déroulement d'une boucle <syntaxhighlight lang="Python" inline>for</syntaxhighlight> ou <syntaxhighlight lang="Python" inline>while</syntaxhighlight>:
 +
* <syntaxhighlight lang="Python" inline>break</syntaxhighlight> provoque une sortie anticipée de la boucle et
 +
* <syntaxhighlight lang="Python" inline>continue</syntaxhighlight>procoque 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 :  
 
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;  
 
*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;
 
*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.
 
*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:
 +
<syntaxhighlight lang="Python" line='line'>
 +
def Div_Eucl (a,b) :
 +
  """ cette fonction calcule le quotient q et le reste r de la division euclidienne de
 +
  l’entier positif a par l’entier strictement positif b et elle renvoie q,r"""
 +
  assert (b >0)
 +
  q,r = 0,a
 +
  while r >= b :
 +
      q=q+1
 +
      r=r-b
 +
  return q,r
 +
</syntaxhighlight>
 +
 +
Dans cet exemple, la propriété <math>a=bq+r</math> est '''un invariant de boucle'''.
 +
 +
Dans ce qui suit, on notera  <math>q_k, r_k</math> les valeurs prises par les variables <math>q, r</math> après le <math>k</math><sup>ième</sup> passage dans la boucle.
 +
On remarque que :
 +
* à '''l'initialisation''' de l’algorithme, on a <math>q_0=0</math> et <math>r_0=a</math> donc <math>a=bq_0+r_0=r_0=a</math> est vérifié;
 +
* à l’itération <math>k</math>, <math>a=bq_k+r_k</math>. Or <math>q_{k+1}=q_k+1</math> et <math>r_{k+1}=r_k-b</math>. Donc à l'itération <math>k+1</math>, on a <math>a=b.q_{k+1}+r_{k+1}=b.(q_k+1)+r_k-b=b.q_k+r_k</math>, ce qui prouve '''la conservation de l'invariant''';
 +
* avant la dernière itération, <math>r_{n-1} \geq b</math> et <math>r_{n}=r_{n-1}-b \Rightarrow 0\leq r_{n} \leq b</math>. Ce qui prouve qu''''à la sortie de la boucle, <math>q</math> est le quotient et <math>r</math> le reste'''. 
 +
 +
 +
<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'''.

Version du 14 juillet 2019 à 10:14

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.