Invariant de boucle

[Rockleader]

Bonjour, connaissez vous une méthode permettant de trouver facilement l'invariant d'une boucle

Par exemple le programme suivant

[CODE]a=0;
while((a+1)*(a+1)0

L'invariant de cette boucle est a>=0 (ça on le trouve avec l'initialisation ok) et a²<N pourtant ce n'est pas ce que dit la condition de la boucle qui elle nous dit (a+1)²<=N

[Faraziel]

Dans ton code, je ne vois pas d'invariant, et pour être franc, je ne savais pas ce que c'était avant d'aller sur wikipédia donc je me trompe peut-être. Mais on peut empêcher le (a+1)² a chaque itération. Si tu te sert pas de ton N dans le while, l'utilisation d'une variable temporaire type :

tmp = sqrt(N)

et ensuite tu compare simplement a+1 a tmp

Code: Tout sélectionner

a=0;
tmp = sqrt(N);

while (a+1 <= N)
a++


le désavantage et l'utilisation d'un registre mémoire supplémentaire pour tmp.
Et ici on peut voir que tu es obligé de comparer le suivant si jamais tu veux récupérer la dernière valeur de a²<N

Une autre solution possible

Code: Tout sélectionner

a=1;
tmp = sqrt(N);

while (a <= N)
{
a++;
}

a--;


auquel cas on réduit encore le coup en calcul.

[Rockleader]

Je pense que l'on ne parle pas de la même chose^^

Qu plus ets il y a bien un invariant puisque c'est un des exemples de mon cours^^

• Exemple

Correction partielle
/*N IN*/
a=0;
/*a=0 */
Invariant : /* a²;)N a;)0 */
while ( (a+1)*(a+1) N )
/* a²;)N a;)0 (a+1)
2 N */
a=a+1
/* a²;)N a;)0 */
;
/* a²;)N a;)0 (a+1)² >N */
/* a²;)N < (a+1)²
*/

[Faraziel]

Effectivement on doit pas parler de la même chose je pense... Désolé de pas pouvoir t'aider, mon niveau de DUT 2eme année INFO IN suffit pas...