Division

La fonction python suivante a pour objectif de calculer quotient et reste de la division euclidienne de a par b (où a et b sont des entiers naturels, b non nul).

def divisionEuclide(a, b):
    """
    a -- entier naturel
    b -- entier naturel non nul

    renvoie le couple (q, r)
    = (quotient, reste) de la division entière de a par b
    """

    q = 0
    r = a

    while r >= b:
        q = q+1
        r = r-b

    return q, r

Démontrer que la boucle termine toujours en explicitant un variant.

Note

On suppose, bien entendu, que les entrées respectent les préconditions données. Si on ne respecte pas les préconditions, la boucle peut-être sans fin. Par exemple, si a>0 et b<0, r augmente à chaque tour de boucle et la boucle ne s'arrête pas.

Rappelons que l'on peut ajouter des assertions dans le code pour contrôler le respect des préconditions. Testez par exemple la version suivante avec b négatif:

def divisionEuclide(a, b):
    """
    a -- entier naturel
    b -- entier naturel non nul

    renvoi -- le couple (q, r) = (quotient, reste) 
              de la division entière de a par b
    """
    assert a >= 0, "erreur: a doit être positif ou nul"
    assert b > 0, "erreur: b doit être strictement positif"
    q = 0
    r = a

    while r >= b:
        q = q+1
        r = r-b

    return q, r

Indication

Montrez que r est un variant de la boucle.

Une résolution

r est un variant de boucle.

En effet:

• r est entier puisque r vaut a au départ et que les seules opérations faites sur r sont ensuite de lui soustraire l'entier b.
• r reste positif dans la boucle car on n'entre dans la boucle que si r ≥ b or b est positif.
• r décroît strictement à chaque passage dans la boucle puisqu'à chaque passage, on effectue r ← r - b (où b est strictement positif).

On a explicité un variant de boucle: cette boucle termine donc.