pythonListSelfTest1
Je teste mes connaissances :
Terminaison algorithmes

Question n°1

Etablir la terminaison de l’algorithme suivant : 

# Entrée : un entier n ≥ 0
# Sortie : la racine carrée de n (arrondie à l’entier inférieur)
def rac(n):
    c := 0
    s := 1
    while s ≤ n do
        c := c + 1
        s := s + 2 * c + 1
        return c
>>> Proposition de solution - Proposition de solution - Proposition de solution <<<

Pour démontrer la terminaison, il suffit de mettre en évidence un variant de boucle : La quantité n − s

cette quantité :

On fera remarquer que la dernière affirmation demande cependant de vérifier que la valeur de c est toujours positive (invariant facile à démontrer). On peut aussi, de façon équivalente, démontrer que la valeur de s augmente strictement à chaque itération et qu’elle est bornée par n, qui lui est constant.


Question n°2

Etablir la terminaison de l’algorithme suivant : 

Entrée : a,b : entiers strictements positifs
Sortie : q, r : entiers
def mystere(a,b):
    r = a ;
    q = 0 ;
    while r > b:
        r = r − b ;
        q = q + 1 ;
    return (q,r)
>>> Proposition de solution - Proposition de solution - Proposition de solution <<<

variant de boucle v : r-b

v ne prend que des valeurs entières; v (en entrée de boucle) est positive; v décroit strictement.

Contribution : Ne pas hésiter à proposer des énoncés d'exercices ... Avec corrections ;)