006A_Schémas d’analyse

Itérations


008_Schéma fonctionnel
Page Suivante

Propriétés de la répétition

VARIABLES
	coup EST_DU_TYPE NOMBRE
	proposition EST_DU_TYPE NOMBRE
	Fini EST_DU_TYPE NOMBRE
	code EST_DU_TYPE NOMBRE
DEBUT_ALGORITHME
	LIRE code
	Fini PREND_LA_VALEUR 0
	coup PREND_LA_VALEUR 0
	TANT_QUE (Fini==0) FAIRE
		DEBUT_TANT_QUE
		SI (coup==3) ALORS
			DEBUT_SI
			AFFICHER* "Pas trouvé"
			Fini PREND_LA_VALEUR 1
			FIN_SI
			SINON
				DEBUT_SINON
				AFFICHER* "votre proposition : "
				LIRE proposition
				AFFICHER* proposition
				SI (proposition==code) ALORS
					DEBUT_SI
					AFFICHER* "Ok"
					Fini PREND_LA_VALEUR 1
					FIN_SI
				FIN_SINON
		coup PREND_LA_VALEUR coup+1
		FIN_TANT_QUE
FIN_ALGORITHME
Cliquez ici pour l’essayer À la « sortie » d’une boucle tant que, la condition de boucle C est toujours fausse \overline{C}. Ceci correspond à l’utilisation naturelle de la boucle while : on veut obtenir, en un certain point du programme, la validité d’une affirmation \overline{C}. On connaît une action A (qui peut évidemment avoir une certaine complexité) dont on espère qu’elle rapproche l’état initial d’un état où \overline{C} est vraie. On répéte A tant que (C) est vraie.
Si l’action A ne modifie pas la relation « P », « P » est invariant pour la boucle while (C) { A ; }.Cette propriété est extrêmement importante. La notion d’invariant de boucle joue un rôle décisif dans la construction de programmes par des méthodes systématiques. En fait, on peut considérer qu’une boucle tant que est entièrement définie par sa condition d’arrêt et un invariant. Aussi souvent que possible, nous indiquerons en même temps qu’une boucle un invariant significatif associé. 
/* P et C */
while (C)
{
    Action_A ()  ; 
}
/* P et non C */
Un invariant est souvent de la forme : « telle variable a telle valeur ». À titre d’exemple, soit le programme ci-contre, qui localise dans une liste l’élément x : /* la variable "trouve" devient vrai si et seulement si L[p]=x et pour tout p compris entre Premier(L) et Acceder(p-1, L) L[p]\neq x */ 
Localiser (x, L)
{
    vrai = 1 ; NonTrouve = -1 ; trouve = faux ;
    p = Premier(L) ;
    /* TANT QUE p n'a pas parcouru toute la liste */
    while (p != Fin(L))
    {
        if (Identique ((Acceder(p, L), x)))
            trouve = vrai ; break ;
        else p = Suivant(p, L) ;
    }
/* Si trouve == vrai alors renvoie p sinon renvoie NonTrouve */
    return (trouve == vrai) ? p : NonTrouve ;
}
Cet invariant étant vrai initialement (puisque trouve = faux), il reste vrai au sortir de la boucle. Joint à la négation de la condition de bouclage, c’est-à-dire /* p = Fin(L) ou trouve */ il donne comme assertion finale : /* trouve == faux et aucun élément de L ne vaut x, ou bien trouve == vrai et x = L(p) */ ce qui est bien le but recherché.

Corriger un programme faux

Dans le numéro de janvier-février 1979 (page 52), de l’ordinateur individuel, est paru ce programme de calcul de x puissance n, que nous étudierons réécrit en langage Python : 
01 # Calcule x ** n
02 # jjd 2020 09 09 
03 x = int (input ("Nombre de base ? "))
04 n = int (input ("Exposant ? "))
05 i = 0 
06 a = x
07 while True:
08   a = a * x 
09   i = i + 1
10   t = n - 1
11  if (i >= t) :
12    break 
13 print ( x, "puissance ", n, " = ", a, "\n")
Examinons la boucle (7-11) : on arrive la 1^{\grave ere} fois en (7) en venant de (5) avec /* a = x \text { et } i = 0 */ Essayons l’assertion a = x^{i+1} \left\{\begin{matrix} (8) & \text{\tt /* } a=x^{i+1} \text{ \tt */} & a = a\times x & \text{ \tt /* } a=x^{i+2} \text{ \tt */} \\ (9)& \text{\tt/* } a=x^{i+2} \text{ \tt */} & i = i+1 & \text{\tt/* } a=x^{i+1} \text{ \tt */} \end{matrix}\right. Remarquons que l’assertion a=x^{i+1} est rétablie, avec une valeur de i plus grande. Mais la donnée introduite est i. Il faut donc comparer i et n. (10) /* a = x^{i+1} \text { et } i < n - 1 boucler (11) /* a = x^{i+1} \text { et } i \le n - 1 */ Si, en (11), i devient égal à n - 1 alors a = x^{n} et le programme est correct. Or par l’initialisation a = x et i = 0. Il faut donc avoir 0 < n - 1 ou n > 1. Nous constatons que le programme calcule a = x^{n} si et si seulement n > 1. Il n’est pas très facile de corriger le programme. Il paraît probable que l’auteur a mal choisi son test d’arrêt, et qu’il a cherché à le corriger en introduisant la variable t calculée ligne (10) dont la valeur est constante. Son calcul dans la boucle est inattendu Il est plus important de considérer les situations que les actions. Pour rédiger le programme, il faut d’abord proposer une situation générale.
Supposons que l’on ait fait une partie du travail, et calculé a=x^i pour i \le n. (7bis) /* on a calculé a=x^i et i < n */ Si i=n, c’est fini ; sinon il faut se rapprocher de la solution en faisant croître i (8-9) a=a\times x; i = i+1; boucler en (6). 
01 # Calcule x ** n
02 # jjd 2020 09 09 
03 x = int (input ("Nombre de base ? "))
04 n = int (input ("Exposant ? "))
05 i = 0 
06 a = 1
07 while (i < n) :
07 (bis)   # /* a == x**i et i < n */
08   a = a * x 
09   i = i + 1
10 # /* a == x**i et i == n */
11 print ( x, "puissance ", n, " = ", a, "\n")
Il reste à voir le démarrage, c'est-à-dire trouver des valeurs de a et i telles que l'assertion soit vérifiée pour tout n positif ou nul. Il faut prendre i=0 et donc a=x^0 = 1. D'où le nouveau programme correct ci-dessus.
006A_Schémas d’analyse
008_Schéma fonctionnel
Page Suivante