Terminaison d’un algorithme

Boucle finie/infinie

Tester le programme suivant dans les deux cas n = 12  et n = 10  :

n = int(input("n : "))
q = 0
while n != 0:
   n -= 3
   q += 1
print(q)

À quelle condition la boucle s’arrête-elle ?

En présence d’une boucle while ... qui ne se termine jamais, on parle de divergence, ou boucle infinie.

Il faut donc impérativement vérifier, par un raisonnement plus ou moins simple, que tôt ou tard, la condition derrière l’instruction while deviendra FAUSSE afin que la boucle se termine.

Une des techniques possibles est celle qui consiste à trouver un variant de boucle.

 

Variant de boucle

Définition : variant de boucle

Un variant de boucle est une expression :

  • entière
  • positive
  • qui décroît strictement à chaque itération

 

Variants usuels

  • i pour une boucle du type for i in range(deb, fin, -1)
  • n−i pour une boucle du type for i in range(n)
  • j−i pour deux variables i croissante et j décroissante
  • . . .

Il n’y a pas de technique « systématique » …

Activité : variant de boucle
Justifier la terminaison de ces deux algorithmes de multiplication de deux entiers en identifiant pour chacun d’entre eux un variant de boucle.

Algo A :

a = int(input("a : "))
b = int(input("b : "))
m = 0
while b > 0:
   m += a
   b -= 1
print("a*b = ", m)

Algo B :

a = int(input("a : "))
b = int(input("b : "))
i = 0
m = 0
while i < b:
   m += a
   i += 1
print("a*b = ", m)

 

Exercices

Liste sans doublon

Compléter la fonction suivante :

from random import randint

def liste_uniques(N, d, f):
    """ Renvoie une liste de N nombres aléatoires
        (entiers entre d et f)
        sans aucun doublons
    """
    l = []
    i = 0
    while ...... :
        ......
    return l

Que se passe-t-il si on exécute liste_uniques(20, 1, 10) ?

Ajouter au début de la fonction une assertion qui doit permettre d’éviter ce comportement.

Définition : assertion
Assertion

Affirmation catégorique de quelque chose qu’il n’est pas possible de vérifier. (Larousse)

En informatique, une assertion est un moyen de s’assurer qu’une condition est respectée avant de commencer (ou continuer) l’exécution d’un algorithme.

L’objectif est d’éviter des erreurs qui ne devraient pas se produire, ou bien des comportement non désirés, en arrêtant prématurément le programme. Si une telle erreur survient, c’est que le programme doit être modifié pour qu’elle n’arrive plus.

En Python, on utilise l’instruction assert :

exemple : assert x*a >= 0 (cette assertion peut éviter par exemple de provoquer une erreur lors de l’appel de la fonction sqrt() )

 

Séparation de liste

Réaliser une fonction separe(lst, v) qui sépare les éléments de la liste lst en plaçant les éléments inférieurs à v au début et les éléments supérieurs à v à la fin. La liste doit être modifiée en place (la fonction ne retourne rien).

 

 

Vous aimerez aussi...

Laisser un commentaire

Votre adresse e-mail ne sera pas publiée. Les champs obligatoires sont indiqués avec *