Inscription / Connexion Nouveau Sujet
Invariant de boucle
Bonjour à tous :
Voila mon probleme, j'ai l'algorithme suivant
fonction somme(a,b):
Entree: deux entiers a et b, avec a ≤ b
Sortie : la somme de a, a+1, …, et b.
solution ← a
Nombre_suivant ← a
Tant que (Nombre_suivant < b):
Nombre_suivant ← Nombre_suivant + 1
solution ← solution + Nombre_suivant
rendre solution
Je doit d'abord exhiber et prouver "l'invariant de boucle".
Puis ensuite en me basant sur se resultat prouver, la correction de cet algorithme.
En faisant quelques iterations j'ai obtenu les resultas suivant :
Initialisation: i = 0 , Nombre_suivant = x, solution = x
Iteration 1i = 1 , Nombre_suivant = x+1, solution = x+(x+1)=2x+1
Iteration 2i = 2 , Nombre_suivant = x+2, solution = (x+1)+(2x+1)=2x+1
Iteration 3i = 3 , Nombre_suivant = x+3, solution = (2x+1)+(3x+3)=3x+3
etc
Mon problème débute ici je n'arrive pas à trouver l'invariant de boucle bien que j'aie essayé avec sigma 
i= x jusqu'a y mais je ne trouve pas la formule avec laquelle la remplir .
Merci d'avance pour votre aide
salut
pour ce que tu veux faire pourquoi ne pas utiliser une boucle toute simple du genre
z = 0 'variable cumulative
a = 2
b = 7
i = 0
While Val(a) + i <> Val(b)
z = z + (Val(a) + i)
i = i + 1
Wend
MsgBox z + (Val(a) + i) ' --> donne la valeur attendue
End Sub
Re bonjour
Un invariant de boucle est une proposition qui est vrai avant la boucle et qui demeure vrai apres chaque iteration.
En quoi mes iterations sont-elles surprenantes ? Vous semble t-elle fausses ?
Bonjour !
Je n'ai pas répondu parce qu'il y a deux hypothèses :
1. L'algorithme (incorrect) a été fourni par le professeur qui souhaite qu'on trouve la faute par examen d'invariant de boucle.
2. La faute est celle d'une recopie hâtive ce qui explique que les "essais" déraillent.
@samihormi
Tu as un invariant simple, en notant le nombre d'itérations, à savoir "Nombre_suivant-k".
Mais si l'énoncé n'est pas l'original je te signale qu'il ne fera pas la somme voulue faute d'une initialisation correcte.
Il est facile de voir que si on n'entrera pas dans la boucle.
@luzak
L'algorithme est correct, c'est une certitude.
En effet les "x" sont en réalité les "a", d'ou l'originalité de mes itérations 
, de plus ils existaient quelques erreurs de calculs.
Voici les véritables itérations que j'ai obtenu :
Iteration 1, i = 1 , Nombre_suivant = a+1, solution = a+(a+1)=2a+1
Iteration 2, i = 2 , Nombre_suivant = a+2, solution = (a+2)+(2a+1)=3a+3
Iteration 3, i = 3 , Nombre_suivant = a+3, solution = (a+3)+(3a+3)=4a+6
Iteration 4, i = 4 , Nombre_suivant = a+4, solution = (a+4)+(4a+6)=5a+10
Iteration 5, i = 5 , Nombre_suivant = a+5, solution = (a+5)+(5a+10)=6a+15
etc
En ce qui concerne l'avancement de la trouvaille de l'invariant de boucle :
J'estime que la partie de "solution" avec "a",
A savoir = (a,2a,3a,4a,5a,6a,...) peu être obtenu avec allant de i=a juqu'a y (lorsque la boucle s'arrête),
Par contre je n'arrive pas à introduire la partie entiere de "solution" à savoir = (0,1,3,6,10,15,...)
Merci d'avance pour vos pistes
Pourquoi appeler "somme(a,b)" un algorithme qui ne calcule PAS .
Parce que franchement trouver au bout de 5 itérations et persister à croire que tu as la somme
!
encore une fois, d'où vient l'algorithme ?
Est-il donné comme ça ? Est-ce celui que tu proposes pour résoudre un problème ? Et quel problème ? Il faudrait le détailler si tu veux qu'on t'aide.
En fait, tu as un algorithme qui calcule (au bout de itérations) le réel
.
Donc, au bout de itérations tu auras
Si c'est ton intention, parfait !
Mais pour appeler ça le calcul d'une somme il faut un certain nombre de contorsions !
son intention était annoncée là :
Bonjour à tous :
Voila mon probleme, j'ai l'algorithme suivant
fonction somme(a,b):
Entree: deux entiers a et b, avec a ≤ b
Sortie : la somme de a, a+1, …, et b.
si j'ai bien compris, la fonction somme(a,b) doit calculer si a est un entier inférieur ou égal à un entier b la somme
@lafol
Exactement !!
Mais il me faut la formule a l'intérieur de sigma pour ensuite prouver par récurrence que l'algorithme est vrai .
@luzak
L'algorithme nous est donné comme ça (je vous avoue que le manque d'indication est également problématique pour moi).
Je doit trouver une formule qui est vrai avant la boucle et après chaque itération de la boucle , c'est l'invariant de boucle.
Une fois trouvé je vais démontrer par récurrence (avec k comme en Terminale) que l'invariant de boucle demeure vrai pour toute valeur.
Puis enfin, je pourrais ainsi en conclure que l'algorithme est correcte.
Toutefois je ne comprend aucune de vos 2 formules j' ai essayé tant bien que mal mais toujours rien.
@alb12
Non, ta formule est valable pour la variable 'Nombre_suivant':
Mon invariant de boucle est la variable 'solution'
j'avoue que je n'ai toujours pas vraiment compris ce qu'est un invariant de boucle ... et à quoi ça sert ... mais d'après ta réponse à 09h19 alors je plussoie à la proposition de alb12
...
Bonjour alb12 !
Quelle différence entre ta relation et ce que j'avais indiqué le 02-10 à 16:10 ?
@samihormi
La formule donnée est bien la variable "solution".
"Toutefois je ne comprend aucune de vos 2 formules j' ai essayé tant bien que mal mais toujours rien." avait dit samihormi
c'est pourquoi j'ai reformule.
On pourrait meme dire que l'invariant de boucle est:
solution=somme de i=0 à i=k des a+i et k<b
luzak : ton invariant de boucle est le résultat final donc une constante !! ... c'est donc évidemment un invariant de boucle
mais d'après ce que je comprends on veut un invariant qui dépende du compteur utilisé dans la boucle (le compteur est nombre_suivant ... que j'ai noté i comme alb12)
et à chaque boucle on a bien la formule de alb12
enfin tu le dis bien dans ta deuxième ligne mais en utilisant la variable b ... qui a déjà un rôle ...
ce me semble-t-il ...
@samihormi
la formule que tu cherches est solution=a+(a+1)+ ... +(a+k)
mais c'est à toi de trouver cette formule ! suite arithmetique ?
Annuler
connectez vous