Environnement : Python
Objectif de l’exercice
Soit un ensemble E d’entiers tel que : 1 appartient à E, si n appartient à E, 3n + 2 et 2n + 3 appartiennent à E.
Nous devons définir fonction qui admet pour argument un entier N et qui retourne True si N appartient à E, puis False si N n’appartient pas à E.
Contrainte : la fonction doit être une fonction itérative.
Ma proposition commentée et expliquée pour cet exercice
def exerciceIteratif(n) :
'''Soit un ensemble contenant 1. Soit N dans cet ensemble, 2N + 3 et 3N + 2 sont dans cet ensemble. Cette fonction admet un paramètre n entier supérieur ou égal à 1 et renvoie True si n est dans cet esemble, et False s'il ne l'est pas.'''
# Test des conditions pour n
assert(isinstance(n,int) and n > 0)
# 1 appartient à l'ensemble, et 2*1 + 3 = 3*1 + 2 = 5 appartient à cet ensemble.
if n == 1 or n == 5 :
return True
# Si n != 1 et n != 5, on veut établir la liste des entiers qui appartiennent à cet ensemble.
# On testera la présence de n dans cette liste.
# Partons d'un seul élément dans cette liste "5", qui appartient à l'ensemble.
list = [5]
# Notre liste "list" ne gardera que les entiers qui peuvent potentiellement être égaux à notre entier n à tester.
# Notre liste "list" sera modifiée telle que son premier élément soit toujours le plus petit, et le dernier le plus grand. (*)
# Conséquence de (*) : lorsque le premier élément de la liste est supérieur à n, tous les éléments le sont.
# On arrête de tester la présence de n dans la liste lorsqu'elle ne peut plus contenir n, soit quand son premier élément est supérieur à n.
while list[0] < n :
# Utilisons une liste de transition "list_transit" pour recréer la liste "list" en respectant notre condition (*).
list_transit = [[],[]]
# On parcourt chaque élément "elem" de la liste
for elem in list :
# On ajoute à notre liste de transition 2*elem + 3 et 3*elem + 2.
# Notons que 2*A + 3 < 3*A + 2 pour A >= 5 (premier élément de la liste "list"). (**)
# Conséquence de (**) : ici, le premier élément de la première liste de "list_transit" sera forcément plus petit que celui de la seconde liste de "list_transit". (C**1)
list_transit[0].append(2 * elem + 3)
# Conséquence de (**) : ici, le dernier élément de la première liste de "list_transit" sera forcément plus petit que celui de la seconde liste de "list_transit". (C**2)
list_transit[1].append(3 * elem + 2)
# Notons (***) : "Un = 3*Un + 2 et Vn = 2 * Vn + 3 sont deux listes strictement croissante".
# Grâce à (*) et (***) : Les deux listes de "list_transit" respectent toujours la condition (*). Notons cette remarque (****).
# Ici, on remplace notre liste "list" par la concaténation des deux listes de "list_transit" en respectant leur ordre. Grâce à (****), (C**1) et (C**2), list respecte bien la propriété (*).
list = list_transit[0] + list_transit[1]
# On veut que le programme soit le plus rapide possible !
# Alors, ne testons la présence de n que si n est susceptible d'être présent !
# Or, d'après (*) si le dernier élément de la liste "list" (list[len(list)-1]) est strictement plus petit que n, tous les éléments de la liste le sont.
# On ne teste donc la présence de n dans la liste "list" que si le dernier élément de la liste est supérieur ou égal à n.
if list[len(list)-1] >= n :
# Si n est dans la liste "list", n appartient bien à l'ensemble dont il est question, puisque la liste list est construite par succession de 3*A + 2 et 2*B + 3 avec A et B dans l'ensemble.
if n in list :
# On retourne True
return True
# Si n n'a jamais appartenu à la liste "list", et que celle-ci ne contient que des éléments supérieurs (strictement) à n, on retourne False car tous les entiers de la l'ensemble susceptibles d'être n ne sont pas n. n n'appartient pas à l'ensemble.
return False
Laisser un commentaire