Comment trouver une boucle invariante de la condition la plus faible?
-
03-11-2019 - |
Question
Considérez ce code:
Condition préalable:
Postcondition: rv == i <==> ∃i, 0 ≤ i ≤ a.length-1, a[i] == key
function Find(Array<int> a, int key) returns (int i) {
i = a.length -1;
while i ≥ 0 {
if a[i] == key {return;}
i = i - 1
}
return -1;
}
En regardant ce code, il recherche essentiellement une clé à partir de la fin du tableau. Ce que j'essaie de trouver, c'est une boucle invariante en utilisant la condition la plus faible, et le prouver. Cependant, je ne sais pas si ma condition la plus faible est correcte. Je pense que la condition la plus faible (et la condition préalable) n'est rien parce que rien ne semble devoir être vrai a!=null
. Donc, si je n'ai pas de condition préalable la plus faible ou a != null
(en supposant que c'est le WP) Comment puis-je obtenir une boucle invariante? Je ne vois pas comment vous pouvez en tirer une boucle invariante. Mis à part tout cela, je pense que l'invariant de la boucle est ∀i,j, j > i ∧ a[j] ≠ key
Mais je n'ai pas utilisé la condition la plus faible pour trouver cette boucle invariante. Des idées sur ce que je fais mal ici?
Pas de solution correcte