Exercice d’informatique sur les fonctions itératives

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

Votre adresse e-mail ne sera pas publiée.