Bonjour à tous
Je suis en prépa maths option informatique et on nous apprend à prouver qu'un algorithme termine et est correct, en utilisant notamment des invariants de boucle. J'ai quelques questions concernant ceux-ci. Soit l'algorithme suivant :
On me demande ce qu'il affichera et de proposer un invariant de boucle. Naturellement, j'ai donné "après n passages, 2^n <= 1 + 10n". Est ce que c'est ce qu'on attend e moi ? Ca peut paraître bête comme question mais je vois pas vraiment quoi mettre d'autre, et non plus en quoi ça peut nous donner ce que l'algorithme affichera (en faisant une résolution sur WolframAlpha, je trouve que le dernier n sera 5, donc ça affichera 1, 2, 4, 8, 16, 32).
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7 x ← 1 y ← 1 tant que x ≤ y faire afficher (x) x → x ∗ 2 y → y+10 fin tant que
Ensuite, pour un programme aussi simple que
Que donner comme invariant de boucle ? "2^n*b ≤ a" ?
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3 tant que 2^n*b ≤ a faire n → n+1 fin tant que
Merci d'avance
Partager