Calcul d'un invariant de boucle

Salut! Est-ce que quelqu'un saurait donner l'invariant de boucle du programme suivant: (le programme teste si le mot est un palindrome)

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12

int i:=0; int j:=n-1; boolean ok := true; while i<=j ET ok, do if a[i]=a[j] then i=i+1 j=j-1 else ok:=false endif done

---

Merci beaucoup!!!!!!!

Dans de lointains souvenirs d'algo je penserai que l'invariant vaut a[i]=a[j] en notant que j=n-(i+1) ,histoire de symétrie. Donc la complexité dans le pire des cas est de O(n/2), le pire des cas étant que le mot sot un palindrome. Mais la preuve est à faire ...

Citation:

---

Envoyé par Malinaka

Dans de lointains souvenirs d'algo je penserai que l'invariant vaut a[i]=a[j] en notant que j=n-(i+1) ,histoire de symétrie. Donc la complexité dans le pire des cas est de O(n/2), le pire des cas étant que le mot sot un palindrome. Mais la preuve est à faire ...

---

Non, ce n'est pas ça.
L'invariant est quelque chose du genre "Les i premiers caractères de a sont les mêmes que les i derniers caractères de a". Je te laisse le soin de le formaliser :)

Je te crois sur parole, je me rapelle surtout de vagues formules mathématiques de mes cours d'algo... La seule chose qui m'ait marqué c'est la compléxité :lol:

Bonjour,
l'invariant de boucle n'est-il pas une propriété toujours vraie à chaque itération. ? Ici, pour une certaine fonction f, ce serait f(i,j)=0.

heu pourquoi f(i,j)=0 et qui est f ? je ne vois pas ce que tu veux dire mais peut-être est-ce parce que ma journée a été longue :aie:

Sinon, pourquoi l'invariant "Les i premiers caractères de a sont les mêmes que les i derniers caractères de a". ne serait-il pas vrai à chaque itération de la boucle ?

Oula ... ma journée a été longue aussi :oops:

Citation:

---

Envoyé par prgasp77

Ici, pour une certaine fonction f, ce serait f(i,j)=0.

---

J'utilisais une fonction non définie pour éviter de donner un résultat de but en blanc ; il s'agissait de l'addition tout simplement : i+j=n pour chaque itération.

Citation:

---

Envoyé par Franck Dernoncourt

pourquoi l'invariant "Les i premiers caractères de a sont les mêmes que les i derniers caractères de a". ne serait-il pas vrai à chaque itération de la boucle ?

---

C'est tout a fait vrai, et cet invariant a plus de porté que celui que je propose.

Si vous me cherchez, je serai dehors.

C'est que la distance entre i et le début du tableau est toujours égale à la distance entre j et la fin du tableau.

Par-contre tu es dans quel groupe ?