Documents Groupés

01_01.py

def taille(arbre, lettre):
    if lettre == '':
        return 0
    return 1 + taille(arbre, arbre[lettre][0]) + taille(arbre, arbre[lettre][1])
    
a = {'F':['B','G'], 'B':['A','D'], 'A':['',''], 'D':['C','E'], \
'C':['',''], 'E':['',''], 'G':['','I'], 'I':['','H'], \
'H':['','']}

assert taille(a, 'F') == 9
assert taille(a, 'B') == 5
assert taille(a, 'I') == 2

01_02.py

def echange(tab, i, j):
    temp = tab[i]
    tab[i] = tab[j]
    tab[j] = temp

def tri_selection(tab):
    N = len(tab)
    for k in range(N-1):
        imin = k
        for i in range(k+1, N):
            if tab[i] < tab[imin]:
                imin = i
        echange(tab, imin, k)

tab = [41, 55, 21, 18, 12, 6, 25]
tri_selection(tab)
assert tab == [6, 12, 18, 21, 25, 41, 55]

02_01.py

def correspond(mot, mot_a_trous):
    n1 = len(mot)
    n2 = len(mot_a_trous)
    if n1 != n2:
        return False
    for i in range(n1):
        if mot[i] != mot_a_trous[i] and mot_a_trous[i] != '*':
            return False
    return True
    
assert correspond('INFORMATIQUE', 'INFO*MA*IQUE') == True
assert correspond('AUTOMATIQUE', 'INFO*MA*IQUE') == False
assert correspond('STOP', 'S*') == False
assert correspond('AUTO', '*UT*') == True

02_02.py

def est_cyclique(plan):
    '''Prend en paramètre un dictionnaire `plan` correspondant à
    un plan d'envoi de messages (ici entre les personnes A, B, C,
    D, E, F).
    Renvoie True si le plan d'envoi de messages est cyclique et
    False sinon.'''
    expediteur = 'A'
    destinataire = plan[expediteur]
    nb_destinaires = 1

    while destinataire != expediteur:
        destinataire = plan[destinataire]
        nb_destinaires += 1

    return nb_destinaires == len(plan)


assert est_cyclique({'A':'E','F':'A','C':'D','E':'B','B':'F','D':'C'}) == False
assert est_cyclique({'A':'E','F':'C','C':'D','E':'B','B':'F','D':'A'}) == True
assert est_cyclique({'A':'B','F':'C','C':'D','E':'A','B':'F','D':'E'}) == True
assert est_cyclique({'A':'B','F':'A','C':'D','E':'C','B':'F','D':'E'}) == False

03_02.py

class Pile:
    def __init__(self):
        self.valeurs = []

    def est_vide(self):
        return self.valeurs == []

    def empiler(self, c):
        self.valeurs.append(c)

    def depiler(self):
        if self.est_vide() == False:
            self.valeurs.pop()


def bon_parenthesage(ch):
    """Renvoie un booléen indiquant si la chaîne ch
    est bien parenthésée"""
    p = Pile()
    for c in ch:
        if c == "(":
            p.empiler(c)
        elif c == ")":
            if p.est_vide():
                return False
            else:
                p.depiler()
    return p.est_vide()


assert bon_parenthesage("((()())(()))") == True
assert bon_parenthesage("())(()") == False
assert bon_parenthesage("(())(()") == False

04_02.py

def distance_carre(point1, point2):
    """ Calcule et renvoie la distance au carré entre
    deux points."""
    return (point1[0] - point2[0])**2 + (point1[1] - point2[1])**2

def point_le_plus_proche(depart, tab):
    """ Renvoie les coordonnées du premier point du tableau tab se
    trouvant à la plus courte distance du point depart."""
    min_point = tab[0]
    min_dist = distance_carre(depart, tab[0])
    for i in range(1, len(tab)):
        if distance_carre(tab[i], depart) < min_dist:
            min_point = tab[i]
            min_dist = distance_carre(tab[i], depart)
    return min_point

assert distance_carre((1, 0), (5, 3)) == 25
assert distance_carre((1, 0), (0, 1)) == 2
assert point_le_plus_proche((0, 0), [(7, 9), (2, 5), (5, 2)]) == (2, 5)
assert point_le_plus_proche((5, 2), [(7, 9), (2, 5), (5, 2)]) == (5, 2)

05_01.py

def max_et_indice(tab):
    """
    Prend en paramètre une liste non vide tab de nombres entiers 
    et renvoie la valeur du plus grand élément de cette liste 
    ainsi que l’indice de sa première apparition dans cette liste.
    """
    index_m = 0
    maxi = tab[0]
    for i in range(1, len(tab)):
        if tab[i] > maxi:
            index_m = i
            maxi = tab[i]
    return maxi, index_m


assert max_et_indice([1, 5, 6, 9, 1, 2, 3, 7, 9, 8]) == (9, 3)
assert max_et_indice([-2]) == (-2, 0)
assert max_et_indice([-1, -1, 3, 3, 3]) == (3, 2)
assert max_et_indice([1, 1, 1, 1]) == (1, 0)

05_02.py

def est_un_ordre(tab):
    '''
    Renvoie True si tab est de longueur n et contient tous les
    entiers de 1 à n, False sinon
    '''
    n = len(tab)
    # les entiers vus lors du parcours
    vus = []

    for x in tab:
        if x < 1 or x >n or x in vus:
            return False
        vus.append(x)
    return True

def nombre_points_rupture(ordre):
    '''
    Renvoie le nombre de point de rupture de ordre qui représente
    un ordre de gènes de chromosome
    '''
    # on vérifie que ordre est un ordre de gènes
    assert est_un_ordre(ordre)
    n = len(ordre)
    nb = 0
    if ordre[0] != 1: # le premier n'est pas 1
        nb = nb + 1
    i = 0
    while i < n-1 :
        if ordre[i+1] - ordre[i] not in [-1, 1]: # l'écart n'est pas 1
            nb = nb + 1
        i = i + 1
    if ordre[i] != n: # le dernier n'est pas n
        nb = nb + 1
    return nb


# Assertions pour les exemples fournis
assert est_un_ordre([1, 6, 2, 8, 3, 7]) == False
assert est_un_ordre([5, 4, 3, 6, 7, 2, 1, 8, 9]) == True
assert nombre_points_rupture([5, 4, 3, 6, 7, 2, 1, 8, 9]) == 4
assert nombre_points_rupture([1, 2, 3, 4, 5]) == 0
assert nombre_points_rupture([1, 6, 2, 8, 3, 7, 4, 5]) == 7
assert nombre_points_rupture([2, 1, 3, 4]) == 2

06_01.py

def verifie(tab):
    for i in range(len(tab)-1):
        if tab[i] > tab[i+1]:
            return False
    return True

# Assertions pour les exemples fournis
assert verifie([0, 5, 8, 8, 9]) == True
assert verifie([8, 12, 4]) == False
assert verifie([-1, 4]) == True
assert verifie([]) == True
assert verifie([5]) == True

06_02.py

def depouille(urne):
    '''prend en paramètre une liste de suffrages et renvoie un
    dictionnaire avec le nombre de voix pour chaque candidat'''
    resultat = {}
    for bulletin in urne:
        if bulletin in resultat:
            resultat[bulletin] = resultat[bulletin] + 1
        else:
            resultat[bulletin]= 1
    return resultat

def vainqueurs(election):
    '''prend en paramètre un dictionnaire non vide avec le nombre de voix
    pour chaque candidat et renvoie la liste des vainqueurs'''
    nmax = 0
    for candidat in election:
        if election[candidat] > nmax :
            nmax =election[candidat]
    liste_finale = [ nom for nom in election if election[nom]==nmax ]
    return liste_finale

# Assertions pour les exemples fournis
assert depouille(['A', 'B', 'A']) == {'A': 2, 'B': 1}
assert depouille([]) == {}
election = depouille(['A', 'A', 'A', 'B', 'C', 'B', 'C', 'B', 'C', 'B'])
assert election == {'A': 3, 'B': 4, 'C': 3}
assert vainqueurs(election) == ['B']
assert vainqueurs({'A': 2, 'B': 2, 'C': 1}) == ['A', 'B']

07_01.py

def gb_vers_entier(tab):
    entier = 0
    for i in range(len(tab)):
        if tab[i]:
            entier += 2 ** (len(tab) - 1 - i)
    return entier

# Assertions pour les exemples fournis
assert gb_vers_entier([]) == 0
assert gb_vers_entier([True]) == 1
assert gb_vers_entier([True, False, True, False, False, True, True]) == 83
assert gb_vers_entier([True, False, False, False, False, False, True, False]) == 130

07_02.py

def tri_insertion(tab):
    '''Trie le tableau tab par ordre croissant
    en appliquant l'algorithme de tri par insertion'''
    n = len(tab)
    for i in range(1, n):
        valeur_insertion = tab[i]
        # la variable j sert à déterminer
        # où placer la valeur à ranger
        j = i
        # tant qu'on n'a pas trouvé la place de l'élément à
        # insérer on décale les valeurs du tableau vers la droite
        while j > 0 and valeur_insertion < tab[j-1]:
            tab[j] = tab[j-1]
            j -= 1
        tab[j] = valeur_insertion

# Exemple d'utilisation
tab = [98, 12, 104, 23, 131, 9]
tri_insertion(tab)
assert tab == [9, 12, 23, 98, 104, 131]

08_01.py

def delta(liste):
    resultat = [liste[0]]
    for i in range(1, len(liste)):
        resultat.append(liste[i] - liste[i - 1])
    return resultat

# Assertions pour les exemples fournis
assert delta([1000, 800, 802, 1000, 1003]) == [1000, -200, 2, 198, 3]
assert delta([42]) == [42]

08_02.py

class Expr:
    """Classe implémentant un arbre d'expression."""

    def __init__(self, g, v, d):
        """un objet Expr possède 3 attributs :
        - gauche : la sous-expression gauche ;
        - valeur : la valeur de l'étiquette, opérande ou nombre ;
        - droite : la sous-expression droite."""
        self.gauche = g
        self.valeur = v
        self.droite = d

    def est_une_feuille(self):
        """renvoie True si et seulement
        si le noeud est une feuille"""
        return self.gauche is None and self.droite is None

    def infixe(self):
        """renvoie la représentation infixe de l'expression en
        chaine de caractères"""
        s = ''
        if self.gauche is not None:
            s = '(' + s + self.gauche.infixe()
        s = s + str(self.valeur)
        if self.droite is not None:
            s = s + self.droite.infixe() + ')'
        return s


# Exemples d'utilisation
a = Expr(Expr(None, 1, None), '+', Expr(None, 2, None))
b = Expr(Expr(Expr(None, 1, None), '+', Expr(None, 2, None)), '*', Expr(Expr(None, 3, None), '+', Expr(None, 4, None)))
e = Expr(
    Expr(Expr(None, 3, None), '*', Expr(Expr(None, 8, None), '+', Expr(None, 7, None))),
    '-', Expr(Expr(None, 2, None), '+', Expr(None, 1, None)))

assert a.infixe() == '(1+2)'
assert b.infixe() == '((1+2)*(3+4))'
assert e.infixe() == '((3*(8+7))-(2+1))'

09_01.py

def effectif_notes(notes_eval):
    """Renvoie un tableau de longueur 11 tel que la valeur d'indice i soit le nombre de notes valant i."""
    effectifs = [0] * 11  # Initialise un tableau de 11 zéros
    for note in notes_eval:
        effectifs[note] += 1
    return effectifs

def notes_triees(effectifs):
    """Prend en paramètre le tableau des effectifs des notes et renvoie un tableau contenant les mêmes valeurs triées."""
    notes_triees = []
    for i in range(len(effectifs)):
        notes_triees += [i] * effectifs[i]  # Ajoute i, effectifs[i] fois, au tableau
    return notes_triees

# Exemple d'utilisation
notes_eval = [2, 0, 5, 9, 6, 9, 10, 5, 7, 9, 9, 5, 0, 9, 6, 5, 4]
eff = effectif_notes(notes_eval)
assert eff == [2, 0, 1, 0, 1, 4, 2, 1, 0, 5, 1]
assert notes_triees(eff) == [0, 0, 2, 4, 5, 5, 5, 5, 6, 6, 7, 9, 9, 9, 9, 9, 10]

09_02.py

def dec_to_bin(nb_dec):
    q, r = nb_dec // 2, nb_dec % 2
    if q == 0:
        return str(r)
    else:
        return dec_to_bin(q) + str(r)

def bin_to_dec(nb_bin):
    if len(nb_bin) == 1:
        if nb_bin == '0':
            return 0
        else:
            return 1
    else:
        if nb_bin[-1] == '0':
            bit_droit = 0
        else:
            bit_droit = 1
        return 2 * bin_to_dec(nb_bin[:-1]) + bit_droit

# Exemples d'utilisation
assert dec_to_bin(25) == '11001'
assert bin_to_dec('101010') == 42

10_01.py

def moyenne(notes):
    somme_notes = 0
    somme_coeffs = 0
    for note, coeff in notes:
        somme_notes += note * coeff
        somme_coeffs += coeff
    if somme_coeffs == 0:
        return None
    else:
        return somme_notes / somme_coeffs

# Exemples d'utilisation
assert moyenne([(8, 2), (12, 0), (13.5, 1), (5, 0.5)]) == 9.142857142857142
assert moyenne([(3, 0), (5, 0)]) == None

10_02.py

def affiche(dessin):
    ''' affichage d'une grille : les 1 sont représentés par
    des "*" , les 0 par un espace " " '''
    for ligne in dessin:
        affichage = ''
        for col in ligne:
            if col == 1:
                affichage = affichage + "*"
            else:
                affichage = affichage + " "
        print(affichage)

def liste_zoom(liste_depart, k):
    '''renvoie une liste contenant k fois chaque élément de
    liste_depart'''
    liste_zoomee = []
    for elt in liste_depart:
        for i in range(k):
            liste_zoomee.append(elt)
    return liste_zoomee

def dessin_zoom(grille, k):
    '''renvoie une grille où les lignes sont zoomées k fois
    ET répétées k fois'''
    grille_zoomee = []
    for ligne in grille:
        ligne_zoomee = liste_zoom(ligne, k)
        for i in range(k):
            grille_zoomee.append(ligne_zoomee)
    return grille_zoomee

# Exemples d'utilisation
coeur = [
    [0, 0, 0, 1, 1, 0, 0, 0, 1, 1, 0, 0, 0],
    [0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0],
    [0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0],
    [0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0],
    [0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0],
    [0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0],
    [0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0],
    [0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0]
]

affiche(coeur)
affiche(dessin_zoom(coeur,2))

11_01.py

def nombre_de_mots(phrase):
    nb = 0
    id_der = len(phrase) - 1
    for c in phrase:
        if c == " ":
            nb += 1
    if phrase[id_der] == "?" or phrase[id_der] == "!":
        return nb  # Ne pas ajouter 1 dans ce cas, car le dernier mot est déjà compté grâce à l'espace le précédant.
    else:
        return nb + 1  # Ajoute 1 pour compter le dernier mot qui n'est pas suivi par un espace.

# Exemples d'utilisation
assert nombre_de_mots('Cet exercice est simple.') == 4
assert nombre_de_mots('Le point d exclamation est séparé !') == 6
assert nombre_de_mots('Combien de mots y a t il dans cette phrase ?') == 10
assert nombre_de_mots('Fin.') == 1

11_02.py

class Noeud:
    def __init__(self, etiquette):
        '''Méthode constructeur pour la classe Noeud.
        Crée une feuille d'étiquette donnée.'''
        self.etiquette = etiquette
        self.gauche = None
        self.droit = None

    def inserer(self, cle):
        '''Insère la clé dans l'arbre binaire de recherche
        en préservant sa structure.'''
        if cle < self.etiquette:
            if self.gauche is not None:
                self.gauche.inserer(cle)
            else:
                self.gauche = Noeud(cle)
        else:
            if self.droit is not None:
                self.droit.inserer(cle)
            else:
                self.droit = Noeud(cle)

# Exemple d'utilisation
arbre = Noeud(7)
for cle in (3, 9, 1, 6):
    arbre.inserer(cle)

# Vérification
assert arbre.gauche.etiquette == 3
assert arbre.droit.etiquette == 9
assert arbre.gauche.gauche.etiquette == 1
assert arbre.gauche.droit.etiquette == 6

12_01.py

def tri_selection(tab):
    n = len(tab)
    for i in range(n):
        # Trouver le plus petit élément restant dans tab[i:n]
        min_index = i
        for j in range(i+1, n):
            if tab[j] < tab[min_index]:
                min_index = j
        # Échanger l'élément le plus petit trouvé avec l'élément à l'indice i
        tab[i], tab[min_index] = tab[min_index], tab[i]

# Exemple d'utilisation
tab = [1, 52, 6, -9, 12]
tri_selection(tab)
assert tab == [-9, 1, 6, 12, 52]

12_02.py

from random import randint

def plus_ou_moins():
    nb_mystere = randint(1, 99)
    nb_test = int(input("Proposez un nombre entre 1 et 99 : "))
    compteur = 1
    while nb_mystere != nb_test and compteur < 10:
        compteur += 1
        if nb_mystere > nb_test:
            nb_test = int(input("Trop petit ! Testez encore : "))
        else:
            nb_test = int(input("Trop grand ! Testez encore : "))
    if nb_mystere == nb_test:
        print("Bravo ! Le nombre était", nb_mystere)
        print("Nombre d'essais:", compteur)
    else:
        print("Perdu ! Le nombre était", nb_mystere)

13_01.py

def recherche(elt, tab):
    for i in range(len(tab)):
        if tab[i] == elt:
            return i
    return None

# Exemples d'utilisation
assert recherche(1, [2, 3, 4]) == None
assert recherche(1, [10, 12, 1, 56]) == 2
assert recherche(50, [1, 50, 1]) == 1
assert recherche(15, [8, 9, 10, 15]) == 3

13_02.py

def insere(tab, a):
    """
    Insère l'élément a (int) dans le tableau tab (list)
    trié par ordre croissant à sa place et renvoie le
    nouveau tableau.
    """
    tab_a = [a] + tab  # Nouveau tableau contenant a suivi des éléments de tab
    i = 0
    while i < len(tab) and a > tab[i]:
        tab_a[i] = tab[i]
        tab_a[i+1] = a
        i = i + 1
    return tab_a

# Exemples d'utilisation
assert insere([1, 2, 4, 5], 3) == [1, 2, 3, 4, 5]
assert insere([1, 2, 7, 12, 14, 25], 30) == [1, 2, 7, 12, 14, 25, 30]
assert insere([2, 3, 4], 1) == [1, 2, 3, 4]
assert insere([], 1) == [1]

14_01.py

def min_et_max(tab):
    min_val = tab[0]
    max_val = tab[0]
    for val in tab[1:]:
        if val < min_val:
            min_val = val
        if val > max_val:
            max_val = val
    return {'min': min_val, 'max': max_val}

# Exemples d'utilisation
assert min_et_max([0, 1, 4, 2, -2, 9, 3, 1, 7, 1]) == {'min': -2, 'max': 9}
assert min_et_max([0, 1, 2, 3]) == {'min': 0, 'max': 3}
assert min_et_max([3]) == {'min': 3, 'max': 3}
assert min_et_max([1, 3, 2, 1, 3]) == {'min': 1, 'max': 3}
assert min_et_max([-1, -1, -1, -1, -1]) == {'min': -1, 'max': -1}

14_02.py

class Carte:
    def __init__(self, c, v):
        """Initialise les attributs couleur (entre 1 et 4),
        et valeur (entre 1 et 13). """
        self.couleur = c
        self.valeur = v

    def recuperer_valeur(self):
        """ Renvoie la valeur de la carte :
        As, 2, ..., 10, Valet, Dame, Roi """
        valeurs = ['As', '2', '3', '4', '5', '6', '7', '8', '9', '10', 'Valet', 'Dame', 'Roi']
        return valeurs[self.valeur - 1]

    def recuperer_couleur(self):
        """ Renvoie la couleur de la carte
        (parmi pique, coeur, carreau, trèfle). """
        couleurs = ['pique', 'coeur', 'carreau', 'trèfle']
        return couleurs[self.couleur - 1]

class Paquet_de_cartes:
    def __init__(self):
        """ Initialise l'attribut contenu avec une liste des 52
        objets Carte possibles rangés par valeurs croissantes en
        commençant par pique, puis cœur, carreau et trèfle. """
        self.contenu=[]
        for c in range(1,5):
            for v in range(1,14):
                self.contenu.append(Carte(c,v))

    def recuperer_carte(self, pos):
        """ Renvoie la carte qui se trouve à la position pos
        (entier compris entre 0 et 51). """
        assert 0 <= pos < 52, "paramètre pos invalide"
        return self.contenu[pos]

# Exemples d'utilisation
jeu = Paquet_de_cartes()
carte1 = jeu.recuperer_carte(20)
print(carte1.recuperer_valeur() + " de " + carte1.recuperer_couleur())
# "8 de coeur"
carte2 = jeu.recuperer_carte(0)
print(carte2.recuperer_valeur() + " de " + carte2.recuperer_couleur())
# "As de pique"
# La ligne suivante, si décommentée, lèverait une AssertionError :
# carte3 = jeu.recuperer_carte(52)

15_02.py

def binaire(a):
    '''convertit un nombre entier a en sa representation
    binaire sous forme de chaine de caractères.'''
    if a == 0:
        return '0'
    bin_a = ''
    while a > 0:
        bin_a = str(a % 2) + bin_a
        a = a // 2
    return bin_a

# Exemples d'utilisation
assert binaire(83) == '1010011'
assert binaire(6) == '110'
assert binaire(127) == '1111111'
assert binaire(0) == '0'

16_01.py

def ecriture_binaire_entier_positif(n):
    if n == 0:
        return '0'
    resultat = ''
    while n > 0:
        resultat = str(n % 2) + resultat
        n = n // 2
    return resultat

# Exemples d'utilisation
assert ecriture_binaire_entier_positif(0) == '0'
assert ecriture_binaire_entier_positif(2) == '10'
assert ecriture_binaire_entier_positif(105) == '1101001'

16_02.py

def echange(tab, i, j):
    '''Echange les éléments d'indice i et j dans le tableau tab.'''
    temp = tab[i]
    tab[i] = tab[j]
    tab[j] = temp

def tri_bulles(tab):
    '''Trie le tableau tab dans l'ordre croissant
    par la méthode du tri à bulles.'''
    n = len(tab)
    for i in range(n-1):
        for j in range(n-1-i):
            if tab[j] > tab[j+1]:
                echange(tab, j, j+1)

# Exemples d'utilisation
tab = []
tri_bulles(tab)
assert tab == []

tab2 = [9, 3, 7, 2, 3, 1, 6]
tri_bulles(tab2)
assert tab2 == [1, 2, 3, 3, 6, 7, 9]

tab3 = [9, 7, 4, 3]
tri_bulles(tab3)
assert tab3 == [3, 4, 7, 9]

17_01.py

def nb_repetitions(elt, tab):
    compteur = 0
    for element in tab:
        if element == elt:
            compteur += 1
    return compteur

# Exemples d'utilisation
assert nb_repetitions(5, [2, 5, 3, 5, 6, 9, 5]) == 3
assert nb_repetitions('A', ['B', 'A', 'B', 'A', 'R']) == 2
assert nb_repetitions(12, [1, '!', 7, 21, 36, 44]) == 0

17_02.py

def binaire(a):
    '''convertit un nombre entier a en sa representation
    binaire sous forme de chaine de caractères.'''
    if a == 0:
        return '0'
    bin_a = ''
    while a > 0:
        bin_a = str(a % 2) + bin_a
        a = a // 2
    return bin_a

# Exemples d'utilisation
assert binaire(0) == '0'
assert binaire(77) == '1001101'

18_01.py

def multiplication(n1,n2):
    s=0
    if n1==0 or n2==0:
        return 0
    if n1<0:
        return -multiplication(-n1,n2)
    if n2<0:
        return -multiplication(n1,-n2)
    for _ in range(n2):
        s = s+n1
    return s
    
# Exemples d'utilisation
assert multiplication(3, 5) == 15
assert multiplication(-4, -8) == 32
assert multiplication(-2, 6) == -12
assert multiplication(-2, 0) == 0

18_02.py

def chercher(tab, x, i, j):
    '''Renvoie l'indice de x dans tab, si x est dans tab,
    None sinon.
    On suppose que tab est trié dans l'ordre croissant.'''
    if i > j:
        return None
    m = (i + j) // 2
    if tab[m] < x:
        return chercher(tab, x, m + 1, j)
    elif tab[m] > x:
        return chercher(tab, x, i, m - 1)
    else:
        return m

# Exemples d'utilisation
assert chercher([1, 5, 6, 6, 9, 12], 7, 0, 10) == None
assert chercher([1, 5, 6, 6, 9, 12], 7, 0, 5) == None
assert chercher([1, 5, 6, 6, 9, 12], 9, 0, 5) == 4
assert chercher([1, 5, 6, 6, 9, 12], 6, 0, 5) == 2

19_01.py

def liste_puissances(a, n):
    tab = [a]
    for _ in range(2, n+1):
        r = tab[-1]*a
        tab.append(r)
    return tab

def liste_puissances_borne(a, borne):
    if borne <= a:
        return []
    tab = [a]
    c = True
    while c:
        r = tab[-1]*a
        if r < borne:
            tab.append(r)
        else :
            c = False
    return tab
            
# Exemples d'utilisation
assert liste_puissances(3, 5) == [3, 9, 27, 81, 243]
assert liste_puissances(-2, 4) == [-2, 4, -8, 16]
assert liste_puissances_borne(2, 16) == [2, 4, 8]
assert liste_puissances_borne(2, 17) == [2, 4, 8, 16]
assert liste_puissances_borne(5, 5) == []

19_02.py

dico = {"A": 1, "B": 2, "C": 3, "D": 4, "E": 5, "F": 6,
        "G": 7, "H": 8, "I": 9, "J": 10, "K": 11, "L": 12,
        "M": 13, "N": 14, "O": 15, "P": 16, "Q": 17,
        "R": 18, "S": 19, "T": 20, "U": 21, "V": 22,
        "W": 23, "X": 24, "Y": 25, "Z": 26}

def codes_parfait(mot):
    """Renvoie un triplet 
    (code_additionne, code_concatene, mot_est_parfait) où :
    - code_additionne est la somme des codes des lettres du mot ;
    - code_concatene est le code des lettres du mot concaténées ;
    - mot_est_parfait est un booléen indiquant si le mot est parfait."""
    code_concatene = ""
    code_additionne = 0
    for c in mot:
        code_concatene = code_concatene + str(dico[c])
        code_additionne = code_additionne + dico[c]
    code_concatene = int(code_concatene)
    mot_est_parfait = True if code_concatene % code_additionne == 0 else False
    return code_additionne, code_concatene, mot_est_parfait

# Exemples d'utilisation
assert codes_parfait("PAUL") == (50, 1612112, False)
assert codes_parfait("ALAIN") == (37, 1121914, True)

20_01.py

from random import randint

def lancer(n):
    """Renvoie un tableau de n entiers obtenus aléatoirement entre 1 et 6."""
    return [randint(1, 6) for _ in range(n)]

def paire_6(tab):
    """Renvoie True si le nombre de 6 dans tab est supérieur ou égal à 2, False sinon."""
    nb_six = 0
    for nombre in tab:
        if nombre == 6:
            nb_six += 1
            if nb_six >= 2:
                return True
    return False

# Exemples d'utilisation
lancer1 = lancer(5)
print(lancer1, paire_6(lancer1))

lancer2 = lancer(5)
print(lancer2, paire_6(lancer2))

lancer3 = lancer(3)
print(lancer3, paire_6(lancer3))

lancer4 = lancer(0)
print(lancer4, paire_6(lancer4))

20_02.py

def nombre_lignes(image):
    '''renvoie le nombre de lignes de l'image'''
    return len(image)

def nombre_colonnes(image):
    '''renvoie la largeur de l'image'''
    return len(image[0])

def negatif(image):
    '''renvoie le negatif de l'image sous la forme d'une liste de listes'''
    # on cree une image de 0 aux memes dimensions que le parametre image
    nouvelle_image = [[0 for k in range(nombre_colonnes(image))] for i in range(nombre_lignes(image))]
    for i in range(nombre_lignes(image)):
        for j in range(nombre_colonnes(image)):
            nouvelle_image[i][j] = 255 - image[i][j]
    return nouvelle_image

def binaire(image, seuil):
    '''renvoie une image binarisee de l'image sous la forme d'une liste de listes contenant des 0 si la valeur du pixel est strictement inferieure au seuil et 1 sinon'''
    nouvelle_image = [[0] * nombre_colonnes(image) for i in range(nombre_lignes(image))]
    for i in range(nombre_lignes(image)):
        for j in range(nombre_colonnes(image)):
            if image[i][j] < seuil:
                nouvelle_image[i][j] = 0
            else:
                nouvelle_image[i][j] = 1
    return nouvelle_image


# Exemples
img=[[20, 34, 254, 145, 6], [23, 124, 237, 225, 69],
     [197, 174, 207, 25, 87], [255, 0, 24, 197, 189]]

assert nombre_lignes(img) == 4
assert nombre_colonnes(img) == 5
assert negatif(img) == [[235, 221, 1, 110, 249], [232, 131, 18, 30, 186], [58, 81, 48, 230, 168], [0, 255, 231, 58, 66]]
assert binaire(img, 120) == [[0, 0, 1, 1, 0], [0, 1, 1, 1, 0], [1, 1, 1, 0, 0], [1, 0, 0, 1, 1]]

21_01.py

def recherche_motif(motif, texte):
    positions = []
    if motif == "":
        return positions
    for i in range(len(texte)):
        if texte[i:i+len(motif)] == motif:
            positions.append(i)
    return positions

# Exemples
assert recherche_motif("ab", "") == []
assert recherche_motif("ab", "cdcdcdcd") == []
assert recherche_motif("ab", "abracadabra") == [0, 7]
assert recherche_motif("ab", "abracadabraab") == [0, 7, 11]

21_02.py

def parcours(adj, x, acc):
    '''Réalise un parcours en profondeur récursif
    du graphe donné par les listes d'adjacence adj
    depuis le sommet x en accumulant les sommets
    rencontrés dans acc'''
    if x not in acc:
        acc.append(x)
        for y in adj[x]:
            parcours(adj, y, acc)

def accessibles(adj, x):
    '''Renvoie la liste des sommets accessibles dans le
    graphe donné par les listes d'adjacence adj depuis
    le sommet x.'''
    acc = []
    parcours(adj, x, acc)
    return acc

# Exemples
assert accessibles([[1, 2], [0], [0, 3], [1], [5], [4]], 0) == [0, 1, 2, 3]
assert accessibles([[1, 2], [0], [0, 3], [1], [5], [4]], 4) == [4, 5]

22_01.py

def recherche_indices_classement(elt, tab):
    indices_inf = []
    indices_egal = []
    indices_sup = []
    
    for i, valeur in enumerate(tab):
        if valeur < elt:
            indices_inf.append(i)
        elif valeur == elt:
            indices_egal.append(i)
        else:
            indices_sup.append(i)
            
    return indices_inf, indices_egal, indices_sup

# Assertions pour vérifier
assert recherche_indices_classement(3, [1, 3, 4, 2, 4, 6, 3, 0]) == ([0, 3, 7], [1, 6], [2, 4, 5])
assert recherche_indices_classement(3, [1, 4, 2, 4, 6, 0]) == ([0, 2, 5], [], [1, 3, 4])
assert recherche_indices_classement(3, [1, 1, 1, 1]) == ([0, 1, 2, 3], [], [])
assert recherche_indices_classement(3, []) == ([], [], [])

22_02.py

def moyenne(nom, resultats):
    '''Renvoie la moyenne de l'élève nom, selon le dictionnaire
    resultats. Si nom n'est pas dans le dictionnaire,
    la fonction renvoie None.'''
    if nom in resultats:
        notes = resultats[nom]
        if not notes:  # pas de notes
            return 0
        total_points = 0
        total_coefficients = 0
        for valeurs in notes.values():
            note, coefficient = valeurs
            total_points = total_points + note * coefficient
            total_coefficients = total_coefficients + coefficient
        return round(total_points / total_coefficients, 1)
    else:
        return None

resultats = {
    'Dupont': {
        'DS1': [15.5, 4],
        'DM1': [14.5, 1],
        'DS2': [13, 4],
        'PROJET1': [16, 3],
        'DS3': [14, 4]
    },
    'Durand': {
        'DS1': [6 , 4],
        'DS2': [8, 4],
        'PROJET1': [9, 3],
        'IE1': [7, 2],
        'DS3': [12, 4]
    }
}

# Assertions pour vérifier
assert moyenne("Dupont", resultats) == 14.5
assert moyenne("Durand", resultats) == 8.5

23_01.py

def insertion_abr(a, cle):
    if a is None:
        return (None, cle, None)
    else:
        g, v, d = a
        if cle < v:
            return (insertion_abr(g, cle), v, d)
        elif cle > v:
            return (g, v, insertion_abr(d, cle))
        else:  # cle == v
            return a

# Création de l'arbre abr1 pour tester la fonction
n0 = (None, 0, None)
n3 = (None, 3, None)
n2 = (None, 2, n3)
abr1 = (n0, 1, n2)

# Tests de la fonction avec assertions
assert insertion_abr(abr1, 4) == ((None, 0, None), 1, (None, 2, (None, 3, (None, 4, None))))
assert insertion_abr(abr1, -5) == (((None, -5, None), 0, None), 1, (None, 2, (None, 3, None)))
assert insertion_abr(abr1, 2) == ((None, 0, None), 1, (None, 2, (None, 3, None)))

23_02.py

def empaqueter(liste_masses, c):
    """Renvoie le nombre minimal de boîtes nécessaires pour
    empaqueter les objets de la liste liste_masses, sachant
    que chaque boîte peut contenir au maximum c kilogrammes"""
    n = len(liste_masses)
    nb_boites = 0
    boites = [0 for _ in range(n)]
    for masse in liste_masses:
        i = 0
        while i < nb_boites and boites[i] + masse > c:
            i = i + 1
        if i == nb_boites:
            nb_boites += 1
        boites[i] += masse
    return nb_boites


assert empaqueter([1, 2, 3, 4, 5], 10) == 2
assert empaqueter([1, 2, 3, 4, 5], 5) == 4
assert empaqueter([7, 6, 3, 4, 8, 5, 9, 2], 11) == 5

24_01.py

def parcours_largeur(arbre):
    if arbre is None:
        return []
    file = [arbre]
    resultats = []
    while file:
        current_node = file.pop(0)
        g, x, d = current_node
        resultats.append(x)
        if g is not None:
            file.append(g)
        if d is not None:
            file.append(d)
    return resultats

arbre = (((None, 1, None), 2, (None, 3, None)), 4, ((None, 5, None), 6, (None, 7, None)))
assert parcours_largeur(arbre) == [4, 2, 6, 1, 3, 5, 7]

arbre_vide = None
assert parcours_largeur(arbre_vide) == []

arbre_simple = (None, 1, None)
assert parcours_largeur(arbre_simple) == [1]

arbre_complexe = ((None, 1, (None, 2, None)), 3, ((None, 4, None), 5, (None, 6, None)))
assert parcours_largeur(arbre_complexe) == [3, 1, 5, 2, 4, 6]

24_02.py

def somme_max(tab):
    n = len(tab)
    sommes_max = [0]*n
    sommes_max[0] = tab[0]
    # on calcule la plus grande somme se terminant en i
    for i in range(1, n):
        if sommes_max[i-1] + tab[i] > tab[i]:
            sommes_max[i] = sommes_max[i-1] + tab[i]
        else:
            sommes_max[i] = tab[i]
    # on en déduit la plus grande somme de celles-ci
    maximum = sommes_max[0]
    for i in range(1, n):
        if sommes_max[i] > maximum:
            maximum = sommes_max[i]
    return maximum

assert somme_max([1, 2, 3, 4, 5]) == 15
assert somme_max([1, 2, -3, 4, 5]) == 9
assert somme_max([1, 2, -2, 4, 5]) == 10
assert somme_max([1, -2, 3, 10, -4, 7, 2, -5]) == 18

25_01.py

def recherche_min(tab):
    if not tab:
        return None
    min_val = tab[0]
    min_index = 0
    for i in range(1, len(tab)):
        if tab[i] < min_val:
            min_val = tab[i]
            min_index = i
    return min_index

# Assertions pour tester la fonction
assert recherche_min([5]) == 0
assert recherche_min([2, 4, 1]) == 2
assert recherche_min([5, 3, 2, 2, 4]) == 2
assert recherche_min([-1, -2, -3, -3]) == 2

25_02.py

def separe(tab):
    '''Separe les 0 et les 1 dans le tableau tab'''
    gauche = 0
    droite = len(tab) - 1
    while gauche < droite:
        if tab[gauche] == 0:
            gauche += 1
        else:
            # Respect de la structure imposée
            temp = tab[gauche]
            tab[gauche] = tab[droite]
            tab[droite] = temp
            droite -= 1
    return tab

# Assertions pour vérifier la fonction `separe`
assert separe([1, 0, 1, 0, 1, 0, 1, 0]) == [0, 0, 0, 0, 1, 1, 1, 1]
assert separe([1, 0, 0, 0, 1, 1, 0, 1, 1, 0, 1, 0, 1, 1, 1, 0]) == [0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1]
assert separe([0, 0, 0, 0]) == [0, 0, 0, 0]
assert separe([1, 1, 1, 1]) == [1, 1, 1, 1]
assert separe([]) == []

26_01.py

def ajoute_dictionnaires(d1, d2):
    d = {}
    for k in d1:
        if k in d2:
            d[k] = d1[k] + d2[k]
        else:
            d[k] = d1[k]
    for k in d2:
        if k not in d:
            d[k] = d2[k]
    return d

# Assertions pour tester la fonction
assert ajoute_dictionnaires({1: 5, 2: 7}, {2: 9, 3: 11}) == {1: 5, 2: 16, 3: 11}
assert ajoute_dictionnaires({}, {2: 9, 3: 11}) == {2: 9, 3: 11}
assert ajoute_dictionnaires({1: 5, 2: 7}, {}) == {1: 5, 2: 7}
assert ajoute_dictionnaires({1: 2}, {1: 3, 4: 5}) == {1: 5, 4: 5}
assert ajoute_dictionnaires({3: 4, 5: 6}, {3: 2, 7: 8}) == {3: 6, 5: 6, 7: 8}

26_02.py

from random import randint

def nombre_coups():
    '''Simule un jeu de plateau avec 12 cases et renvoie le nombre
    minimal de coups pour visiter toutes les cases.'''
    nombre_cases = 12
    # indique si une case a été vue
    cases_vues = [False] * nombre_cases
    nombre_cases_vues = 1
    cases_vues[0] = True
    case_en_cours = 0
    n = 0
    while nombre_cases_vues < nombre_cases:
        x = randint(1, 6)
        case_en_cours = (case_en_cours + x) % nombre_cases
        if not cases_vues[case_en_cours]:
            cases_vues[case_en_cours] = True
            nombre_cases_vues += 1
        n += 1
    return n

# Tests
print(nombre_coups())  # Résultat variable à chaque exécution

27_01.py

def couples_consecutifs(tab):
    """
    prend en paramètre une liste de nombres entiers tab non vide, et qui renvoie la liste (éventuellement vide) des couples d'entiers consécutifs successifs qu'il peut y avoir dans tab.
    """
    t = []
    for i in range(len(tab)-1):
        if tab[i+1] -  tab[i] == 1:
            t.append((tab[i], tab[i+1]))
    return t

assert couples_consecutifs([1, 4, 3, 5]) == []
assert couples_consecutifs([1, 4, 5, 3]) == [(4, 5)]
assert couples_consecutifs([1, 1, 2, 4]) == [(1, 2)]
assert couples_consecutifs([7, 1, 2, 5, 3, 4]) == [(1, 2), (3, 4)]
assert couples_consecutifs ([5, 1, 2, 3, 8, -5, -4, 7]) == [(1, 2), (2, 3), (-5, -4)]

27_02.py

def colore_comp1(M, i, j, val):
    if M[i][j] != 1:
        return
    M[i][j] = val
    if i - 1 >= 0:  # propage à gauche
        colore_comp1(M, i - 1, j, val)
    if i + 1 < len(M):  # propage à droite
        colore_comp1(M, i + 1, j, val)
    if j - 1 >= 0:  # propage en haut
        colore_comp1(M, i, j - 1, val)
    if j + 1 < len(M[0]):  # propage en bas
        colore_comp1(M, i, j + 1, val)

# Exemple :
M = [[0, 0, 1, 0], [0, 1, 0, 1], [1, 1, 1, 0], [0, 1, 1, 0]]
colore_comp1(M, 2, 1, 3)
assert M == [[0, 0, 1, 0], [0, 3, 0, 1], [3, 3, 3, 0], [0, 3, 3, 0]]

28_01.py

def fibonacci(n):
    if n == 1 or n == 2:
        return 1
    tab = [None] * (n + 1)
    tab[1] = 1
    tab[2] = 1
    for i in range(3, n + 1):
        tab[i] = tab[i - 1] + tab[i - 2]
    return tab[n]

# Assertions pour vérifier le fonctionnement de la fonction
assert fibonacci(1) == 1, "Le premier terme devrait être 1"
assert fibonacci(2) == 1, "Le deuxième terme devrait être 1"
assert fibonacci(3) == 2, "Le troisième terme devrait être 2"
assert fibonacci(4) == 3, "Le quatrième terme devrait être 3"
assert fibonacci(5) == 5, "Le cinquième terme devrait être 5"
assert fibonacci(6) == 8, "Le sixième terme devrait être 8"
assert fibonacci(25) == 75025, "Le 25ème terme devrait être 75025"

# Cette version de la fonction fibonacci
# utilise une approche de programmation dynamique
# en stockant tous les termes calculés dans un tableau

28_02.py

def eleves_du_mois(eleves, notes):
    note_maxi = 0
    meilleurs_eleves = []
    for i in range(len(notes)):
        if notes[i] == note_maxi:
            meilleurs_eleves.append(eleves[i])
        elif notes[i] > note_maxi:
            note_maxi = notes[i]
            meilleurs_eleves = [eleves[i]]
    return (note_maxi, meilleurs_eleves)

# Assertions
assert eleves_du_mois(['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j'], [30, 40, 80, 60, 58, 80, 75, 80, 60, 24]) == (80, ['c', 'f', 'h'])
assert eleves_du_mois([], []) == (0, [])

29_01.py

def moyenne(notes):
    total = 0
    total_coefficients = 0
    
    for note, coefficient in notes:
        total += note * coefficient
        total_coefficients += coefficient
    
    return total / total_coefficients
    
assert moyenne([(15.0, 2), (9.0, 1), (12.0, 3)]) == 12.5

29_02.py

def ligne_suivante(ligne):
    '''Renvoie la ligne suivant ligne du triangle de Pascal'''
    ligne_suiv = [1]
    for i in range(len(ligne) - 1):
        ligne_suiv.append(ligne[i] + ligne[i + 1])
    ligne_suiv.append(1)
    return ligne_suiv

def pascal(n):
    '''Renvoie le triangle de Pascal de hauteur n'''
    triangle = [[1]]
    for k in range(n):
        ligne_k = ligne_suivante(triangle[-1])
        triangle.append(ligne_k)
    return triangle

# Assertions
assert ligne_suivante([1, 3, 3, 1]) == [1, 4, 6, 4, 1]
assert pascal(2) == [[1], [1, 1], [1, 2, 1]]
assert pascal(3) == [[1], [1, 1], [1, 2, 1], [1, 3, 3, 1]]

30_01.py

def fusion(tab1, tab2):
    n1 =  len(tab1)
    n2 = len(tab2)
    i1 = 0
    i2  = 0
    tab=[]
    while i1 < n1 and i2 < n2:
        if tab1[i1] > tab2[i2]:
            tab.append(tab2[i2])
            i2 = i2 + 1
        else :
            tab.append(tab1[i1])
            i1 = i1 + 1
    while i1 < n1 :
        tab.append(tab1[i1])
        i1 = i1 + 1
    while i2 < n2 :
        tab.append(tab2[i2])
        i2 = i2 + 1
    return tab
    
        
assert fusion([3, 5], [2, 5]) == [2, 3, 5, 5]
assert fusion([-2, 4], [-3, 5, 10]) == [-3, -2, 4, 5, 10]
assert fusion([4], [2, 6]) == [2, 4, 6]
assert fusion([], []) == []
assert fusion([1, 2, 3], []) == [1, 2, 3]

30_02.py

romains = {"I": 1, "V": 5, "X": 10, "L": 50, "C": 100, "D": 500, "M": 1000}

def traduire_romain(nombre):
    """ Renvoie l'écriture décimale du nombre donné en chiffres romains """
    if len(nombre) == 1:
        return romains[nombre]
    elif romains[nombre[0]] >= romains[nombre[1]]:
        return romains[nombre[0]] + traduire_romain(nombre[1:])
    else:
        return -romains[nombre[0]] + traduire_romain(nombre[1:])
        
assert traduire_romain("XIV") == 14
assert traduire_romain("CDI") == 401

31_01.py

def multiplication(n1, n2):
    if n1 == 0 or n2 == 0:
        return 0
    result = 0
    negative = (n1 < 0) != (n2 < 0)
    n1, n2 = abs(n1), abs(n2)
    for _ in range(n1):
        result += n2
    if negative:
        result = -result
    return result

assert multiplication(3, 5) == 15
assert multiplication(-4, -8) == 32
assert multiplication(-2, 6) == -12
assert multiplication(-2, 0) == 0

31_02.py

def dichotomie(tab, x):
    """
    tab : tableau d'entiers trié dans l'ordre croissant
    x : nombre entier
    La fonction renvoie True si tab contient x et False sinon
    """
    debut = 0
    fin = len(tab) - 1
    while debut <= fin:
        m = (debut + fin) // 2
        if x == tab[m]:
            return True
        if x > tab[m]:
            debut = m + 1
        else:
            fin = m - 1
    return False

# Exemples
assert dichotomie([15, 16, 18, 19, 23, 24, 28, 29, 31, 33], 28) == True
assert dichotomie([15, 16, 18, 19, 23, 24, 28, 29, 31, 33], 27) == False

32_01.py

def xor(a, b):
    # Définition manuelle de la table de XOR
    if a == b:
        return 0
    else:
        return 1

def ou_exclusif(tab1, tab2):
    result = []
    for i in range(len(tab1)):
        result.append(xor(tab1[i], tab2[i]))
    return result

# Exemples
assert ou_exclusif([1, 0, 1, 0, 1, 1, 0, 1], [0, 1, 1, 1, 0, 1, 0, 0]) == [1, 1, 0, 1, 1, 0, 0, 1]
assert ou_exclusif([1, 1, 0, 1], [0, 0, 1, 1]) == [1, 1, 1, 0]

32_02.py

class Carre:
    def __init__(self, liste, n):
        self.ordre = n
        self.tableau = [[liste[i + j * n] for i in range(n)] for j in range(n)]

    def affiche(self):
        '''Affiche un carré'''
        for i in range(self.ordre):
            print(self.tableau[i])

    def somme_ligne(self, i):
        '''Calcule la somme des valeurs de la ligne i'''
        return sum(self.tableau[i])

    def somme_col(self, j):
        '''Calcule la somme des valeurs de la colonne j'''
        return sum(self.tableau[i][j] for i in range(self.ordre))

    def est_semimagique(self):
        s = self.somme_ligne(0)
        # test de la somme de chaque ligne
        for i in range(self.ordre):
            if self.somme_ligne(i) != s:
                return False
        # test de la somme de chaque colonne
        for j in range(self.ordre):
            if self.somme_col(j) != s:
                return False
        return True


# Exemples de carrés
lst_c2 = [4, 4, 4, 4]  # Inventé, 2x2 semimagique pour l'exemple
c2 = Carre(lst_c2, 2)

lst_c3 = [3, 4, 5, 4, 4, 4, 5, 4, 3]  # Semimagique selon l'énoncé
c3 = Carre(lst_c3, 3)

lst_c3bis = [5, 5, 5, 2, 4, 4, 3, 3, 3]  # Inventé, pas semimagique pour l'exemple
c3bis = Carre(lst_c3bis, 3)

# Assertions
assert c2.est_semimagique() == True, "c2 devrait être semimagique"
assert c3.est_semimagique() == True, "c3 devrait être semimagique"
assert c3bis.est_semimagique() == False, "c3bis ne devrait pas être semimagique"

33_02.py

def crible(n):
    """Renvoie un tableau contenant tous les nombres premiers plus petits que n."""
    premiers = []
    tab = [True] * n
    tab[0], tab[1] = False, False
    for i in range(2, n):
        if tab[i]:
            premiers.append(i)
            multiple = 2 * i
            while multiple < n:
                tab[multiple] = False
                multiple += i
    return premiers

# Assertions
assert crible(40) == [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37]
assert crible(5) == [2, 3]

34_01.py

def nbr_occurrences(chaine):
    occurrences = {}
    for caractere in chaine:
        if caractere in occurrences:
            occurrences[caractere] += 1
        else:
            occurrences[caractere] = 1
    return occurrences

# Assertions
assert nbr_occurrences('bonjour') == {'b': 1, 'o': 2, 'n': 1, 'j': 1, 'u': 1, 'r': 1}
assert nbr_occurrences('Bébé') == {'B': 1, 'é': 2, 'b': 1}
assert nbr_occurrences('Hello world !') == {'H': 1, 'e': 1, 'l': 3, 'o': 2, ' ': 2, 'w': 1, 'r': 1, 'd': 1, '!': 1}

34_02.py

def fusion(lst1, lst2):
    n1 = len(lst1)
    n2 = len(lst2)
    lst12 = [0] * (n1 + n2)
    i1 = 0
    i2 = 0
    i=0
    while i1 < n1 and i2 < n2 :
        if lst1[i1] < lst2[i2]:
            lst12[i] = lst1[i1]
            i1 = i1 + 1
        else:
            lst12[i] = lst2[i2]
            i2 = i2 + 1
        i += 1
    while i1 < n1:
        lst12[i] = lst1[i1]
        i1 = i1 + 1
        i = i + 1
    while i2 < n2:
        lst12[i] = lst2[i2]
        i2 = i2 + 1
        i = i + 1
    return lst12

# Assertions
assert fusion([1, 2, 3], []) == [1, 2, 3]
assert fusion([], []) == []
assert fusion([1, 6, 10], [0, 7, 8, 9]) == [0, 1, 6, 7, 8, 9, 10]

35_01.py

t_moy = [14.9, 13.3, 13.1, 12.5, 13.0, 13.6, 13.7]
annees = [2013, 2014, 2015, 2016, 2017, 2018, 2019]

def annee_temperature_minimale(releve, date):
    m = releve[0]
    indice = 0
    for i in range(1, len(releve)):
        if releve[i]<m:
            m = releve[i]
            indice = i
    return m, date[indice]


# Assertion
assert annee_temperature_minimale(t_moy, annees) == (12.5, 2016)

35_02.py

def inverse_chaine(chaine):
    '''Retourne la chaine inversée'''
    resultat = ''
    for caractere in chaine:
        resultat = caractere + resultat
    return resultat

def est_palindrome(chaine):
    '''Renvoie un booléen indiquant si la chaine ch est un palindrome'''
    inverse = inverse_chaine(chaine)
    return chaine == inverse

def est_nbre_palindrome(nbre):
    '''Renvoie un booléen indiquant si le nombre nbre est un palindrome'''
    chaine = str(nbre)
    return est_palindrome(chaine)

# Assertions
assert inverse_chaine('bac') == 'cab'
assert est_palindrome('NSI') == False
assert est_palindrome('ISN-NSI') == True
assert est_nbre_palindrome(214312) == False
assert est_nbre_palindrome(213312) == True

36_01.py

def occurrences(caractere, chaine):
    count = 0
    for c in chaine:
        if c == caractere:
            count += 1
    return count

# Assertions
assert occurrences('e', "sciences") == 2
assert occurrences('i', "mississippi") == 4
assert occurrences('a', "mississippi") == 0

36_02.py

valeurs = [100, 50, 20, 10, 5, 2, 1]

def rendu_glouton(a_rendre, rang):
    if a_rendre == 0:
        return []
    v = valeurs[rang]
    if v <= a_rendre:
        return [v] + rendu_glouton(a_rendre - v, rang)
    else:
        return rendu_glouton(a_rendre, rang + 1)
        
# Assertions
assert rendu_glouton(67, 0) == [50, 10, 5, 2]
assert rendu_glouton(291, 0) == [100, 100, 50, 20, 20, 1]
assert rendu_glouton(291, 1) == [50, 50, 50, 50, 50, 20, 20, 1]

37_01.py

def moyenne(tab):
    if not tab:
        return None  # Retourner None si le tableau est vide
    somme = 0
    for element in tab:
        somme += element
    return somme / len(tab)
    
# Assertion
assert moyenne([5, 3, 8]) == 5.333333333333333
assert moyenne([1, 2, 3, 4, 5, 6, 7, 8, 9, 10]) == 5.5
assert moyenne([]) == None

37_02.py

def tri(tab):
    '''tab est un tableau d'entiers contenant des 0 et des 1.
    La fonction trie ce tableau en plaçant tous les 0 à gauche'''
    i = 0  # premier indice de la zone non triée
    j = len(tab) - 1  # dernier indice de la zone non triée
    while i < j:
        if tab[i] == 0:
            i = i + 1
        else:
            valeur = tab[i]
            tab[i] = tab[j]
            tab[j] = valeur
            j = j- 1

# Assertion
tab = [0, 1, 0, 1, 0, 1, 0, 1, 0]
tri(tab)
assert tab == [0, 0, 0, 0, 0, 1, 1, 1, 1]

38_01.py

def indices_maxi(tab):
    t_maxi = []
    maxi = tab[0]
    n = len(tab)
    for i in range(1,n):
        if tab[i]>maxi:
            maxi = tab[i]
    for i in range(n):
        if tab[i] == maxi:
            t_maxi.append(i)
    return maxi, t_maxi
    
# Assertions
assert indices_maxi([1, 5, 6, 9, 1, 2, 3, 7, 9, 8]) == (9, [3, 8])
assert indices_maxi([7]) == (7, [0])

38_02.py

def renverse(pile):
    '''renvoie une pile contenant les mêmes éléments que pile,
    mais dans l'ordre inverse.
    Cette fonction détruit pile.'''
    pile_inverse = []
    while pile != []:
        pile_inverse.append(pile.pop())
    return pile_inverse

def positifs(pile):
    '''renvoie une pile contenant les éléments positifs de pile,
    dans le même ordre. Cette fonction détruit pile.'''
    pile_positifs = []
    while pile != []:
        valeur = pile.pop()
        if valeur >= 0:
            pile_positifs.append(valeur)
    return renverse(pile_positifs)

# Assertions
assert renverse([1, 2, 3, 4, 5]) == [5, 4, 3, 2, 1]
assert positifs([-1, 0, 5, -3, 4, -6, 10, 9, -8]) == [0, 5, 4, 10, 9]
assert positifs([-2]) == []

39_01.py

def recherche(elt, tab):
    indice = None
    for i in range(len(tab)):
        if tab[i] == elt:
            indice = i
    return indice

# Assertions
assert recherche(1, [2, 3, 4]) == None
assert recherche(1, [10, 12, 1, 56]) == 2
assert recherche(1, [1, 0, 42, 7]) == 0
assert recherche(1, [1, 50, 1]) == 2
assert recherche(1, [8, 1, 10, 1, 7, 1, 8]) == 5

39_02.py

class AdresseIP:
    def __init__(self, adresse):
        self.adresse = adresse

    def liste_octets(self):
        """renvoie une liste de nombres entiers,
        la liste des octets de l'adresse IP"""
        return [int(i) for i in self.adresse.split(".")]

    def est_reservee(self):
        """renvoie True si l'adresse IP est une adresse
        réservée, False sinon"""
        reservees = ['192.168.0.0', '192.168.0.255']
        return self.adresse in reservees

    def adresse_suivante(self):
        """renvoie un objet de AdresseIP avec l'adresse
        IP qui suit l'adresse self si elle existe et None sinon"""
        octets = self.liste_octets()
        if octets[3] == 255:
            return None
        octet_nouveau = octets[3] + 1
        return AdresseIP('192.168.0.' + str(octet_nouveau))

# Instanciation des objets
adresse1 = AdresseIP('192.168.0.1')
adresse2 = AdresseIP('192.168.0.2')
adresse3 = AdresseIP('192.168.0.0')

# Assertions
assert adresse1.liste_octets() == [192, 168, 0, 1]
assert adresse1.est_reservee() == False
assert adresse3.est_reservee() == True
assert adresse2.adresse_suivante().adresse == '192.168.0.3'

40_01.py

def selection_enclos(animaux, num_enclos):
    resultats = []
    for animal in animaux:
        if animal['enclos'] == num_enclos:
            resultats.append(animal)
    return resultats

# Exemple avec la table animaux donnée
animaux = [
    {'nom':'Medor', 'espece':'chien', 'age':5, 'enclos':2},
    {'nom':'Titine', 'espece':'chat', 'age':2, 'enclos':5},
    {'nom':'Tom', 'espece':'chat', 'age':7, 'enclos':4},
    {'nom':'Belle', 'espece':'chien', 'age':6, 'enclos':3},
    {'nom':'Mirza', 'espece':'chat', 'age':6, 'enclos':5}
]

assert selection_enclos(animaux, 5) == [{'nom':'Titine', 'espece':'chat', 'age':2, 'enclos':5}, {'nom':'Mirza', 'espece':'chat', 'age':6, 'enclos':5}]
assert selection_enclos(animaux, 2) == [{'nom':'Medor', 'espece':'chien', 'age':5, 'enclos':2}]
assert selection_enclos(animaux, 7) == []

40_02.py

def trouver_intrus(tab, g, d):
    """Renvoie la valeur de l'intrus situé entre les indices g et d
    dans le tableau tab où :
    tab vérifie les conditions de l'exercice,
    g et d sont des multiples de 3."""
    if g == d:
        return tab[g]
    else:
        nombre_de_triplets = (d - g) // 3
        indice = g + 3 * (nombre_de_triplets // 2)
        if tab[indice] == tab[indice + 1]:
            return trouver_intrus(tab, indice + 3, d)
        else:
            return trouver_intrus(tab, g, indice)

# Assertions
assert trouver_intrus([3, 3, 3, 9, 9, 9, 1, 1, 1, 7, 2, 2, 2, 4, 4, 4, 8, 8, 8], 0, 18) == 7
assert trouver_intrus([8, 5, 5, 5, 9, 9, 9, 18, 18, 18, 3, 3, 3], 0, 12) == 8
assert trouver_intrus([5, 5, 5, 1, 1, 1, 0, 0, 0, 6, 6, 6, 3, 8, 8, 8], 0, 15) == 3

41_01.py

class Noeud:
    def __init__(self, etiquette, gauche, droit):
        self.v = etiquette
        self.gauche = gauche
        self.droit = droit

def taille(a):
    if a is None:
        return 0
    else:
        return 1 + taille(a.gauche) + taille(a.droit)

def hauteur(a):
    if a is None:
        return -1
    else:
        return 1 + max(hauteur(a.gauche), hauteur(a.droit))

# Tests
a = Noeud(1, Noeud(4, None, None), Noeud(0, None, Noeud(7, None, None)))
assert hauteur(a) == 2
assert taille(a) == 4
assert hauteur(None) == -1
assert taille(None) == 0
assert hauteur(Noeud(1, None, None)) == 0
assert taille(Noeud(1, None, None)) == 1

41_02.py

def ajoute(indice, element, tab):
    '''Renvoie un nouveau tableau obtenu en insérant
    element à l'indice indice dans le tableau tab.'''
    nbre_elts = len(tab)
    tab_ins = [0] * (nbre_elts + 1)
    for i in range(indice):
        tab_ins[i] = tab[i]
    tab_ins[indice] = element
    for i in range(indice + 1, nbre_elts + 1):
        tab_ins[i] = tab[i - 1]
    return tab_ins

# Tests
assert ajoute(1, 4, [7, 8, 9]) == [7, 4, 8, 9]
assert ajoute(3, 4, [7, 8, 9]) == [7, 8, 9, 4]
assert ajoute(0, 4, [7, 8, 9]) == [4, 7, 8, 9]

42_01.py

def moyenne(tab):
    '''Calcul de la moyenne d'un tableau d'entiers non vide'''
    somme = 0
    for nombre in tab:
        somme += nombre
    return somme / len(tab)

# Tests
assert moyenne([1]) == 1.0
assert moyenne([1, 2, 3, 4, 5, 6, 7]) == 4.0
assert moyenne([1, 2]) == 1.5

42_02.py

def dichotomie(tab, x):
    """Applique une recherche dichotomique pour déterminer si x est dans le tableau trié tab.
    La fonction renvoie True si tab contient x et False sinon."""
    debut = 0
    fin = len(tab) - 1
    while debut <= fin:
        m = (debut + fin) // 2
        if x == tab[m]:
            return True
        if x > tab[m]:
            debut = m + 1
        else:
            fin = m - 1
    return False

# Tests
assert dichotomie([15, 16, 18, 19, 23, 24, 28, 29, 31, 33], 28) == True
assert dichotomie([15, 16, 18, 19, 23, 24, 28, 29, 31, 33], 27) == False
assert dichotomie([15, 16, 18, 19, 23, 24, 28, 29, 31, 33], 1) == False
assert dichotomie([], 28) == False

43_01.py

def a_doublon(tab):
    """Vérifie si le tableau trié tab contient au moins deux nombres identiques."""
    if len(tab) < 2:
        return False
    
    for i in range(len(tab) - 1):
        if tab[i] == tab[i + 1]:
            return True
    
    return False

# Tests
assert a_doublon([]) == False
assert a_doublon([1]) == False
assert a_doublon([1, 2, 4, 6, 6]) == True
assert a_doublon([2, 5, 7, 7, 7, 9]) == True
assert a_doublon([0, 2, 3]) == False

43_02.py

def voisinage(n, ligne, colonne):
    """ Renvoie la liste des coordonnées des voisins de la case
    (ligne, colonne) en gérant les cases sur les bords. """
    voisins = []
    for l in range(max(0, ligne - 1), min(n, ligne + 2)):
        for c in range(max(0, colonne - 1), min(n, colonne + 2)):
            if (l, c) != (ligne, colonne):
                voisins.append((l, c))
    return voisins

def incremente_voisins(grille, ligne, colonne):
    """ Incrémente de 1 toutes les cases voisines d'une bombe."""
    voisins = voisinage(len(grille), ligne, colonne)
    for l, c in voisins:
        if grille[l][c] != -1:  # si ce n'est pas une bombe
            grille[l][c] += 1  # on ajoute 1 à sa valeur

def genere_grille(bombes):
    """ Renvoie une grille de démineur de taille nxn où n est
    le nombre de bombes, en plaçant les bombes à l'aide de
    la liste bombes de coordonnées (tuples) passée en
    paramètre. """
    n = len(bombes)
    # Initialisation d'une grille nxn remplie de 0
    grille = [[0 for _ in range(n)] for _ in range(n)]
    # Place les bombes et calcule les valeurs des autres cases
    for ligne, colonne in bombes:
        grille[ligne][colonne] = -1  # place la bombe
        incremente_voisins(grille, ligne, colonne)  # incrémente ses voisins
    return grille

# Test de l'exemple donné
resultat = genere_grille([(1, 1), (2, 4), (3, 1), (3, 3), (4, 4)])

assert resultat == [[1, 1, 1, 0, 0],
                    [1, -1, 1, 1, 1],
                    [2, 2, 3, 2, -1],
                    [1, -1, 2, -1, 3],
                    [1, 1, 2, 2, -1]]

44_01.py

def enumere(tab):
    d = {}
    i = 0
    for elem in tab:
        if elem not in d:
            d[elem] = []
        d[elem].append(i)
        i += 1
    return d

# Tests
assert enumere([]) == {}
assert enumere([1, 2, 3]) == {1: [0], 2: [1], 3: [2]}
assert enumere([1, 1, 2, 3, 2, 1]) == {1: [0, 1, 5], 2: [2, 4], 3: [3]}

44_02.py

class Noeud:
    """Classe représentant un noeud d'un arbre binaire"""
    def __init__(self, etiquette, gauche, droit):
        """Crée un noeud de valeur etiquette avec
        gauche et droit comme fils."""
        self.etiquette = etiquette
        self.gauche = gauche
        self.droit = droit

def parcours(arbre, liste):
    """parcours récursivement l'arbre en ajoutant les étiquettes
    de ses noeuds à la liste passée en argument en ordre infixe."""
    if arbre is not None:
        parcours(arbre.gauche, liste)
        liste.append(arbre.etiquette)
        parcours(arbre.droit, liste)
    return liste

def insere(arbre, cle):
    """insere la cle dans l'arbre binaire de recherche
    représenté par arbre.
    Retourne l'arbre modifié."""
    if arbre is None:
        return Noeud(cle, None, None)  # création d'une feuille
    else:
        if cle < arbre.etiquette:
            arbre.gauche = insere(arbre.gauche, cle)
        else:
            arbre.droit = insere(arbre.droit, cle)
    return arbre

# Test
arbre = Noeud(6, Noeud(4, Noeud(1, None, None), Noeud(5, None, None)), Noeud(8, None, None))
print("Arbre avant insertion :", parcours(arbre, []))
insere(arbre, 1)
insere(arbre, 4)
insere(arbre, 6)
insere(arbre, 8)
print("Arbre après insertion :", parcours(arbre, []))

45_01.py

# Fonction compte_occurrences
def compte_occurrences(x, tab):
    """Compte le nombre d'occurrences de x dans le tableau tab."""
    occurrences = 0
    for elem in tab:
        if elem == x:
            occurrences += 1
    return occurrences

# Assertions
assert compte_occurrences(5, []) == 0
assert compte_occurrences(5, [-2, 3, 1, 5, 3, 7, 4]) == 1
assert compte_occurrences('a', ['a', 'b', 'c', 'a', 'd', 'e', 'a']) == 3

45_02.py

def rendu_monnaie(somme_due, somme_versee):
    '''Renvoie la liste des pièces à rendre pour rendre la monnaie
    lorsqu'on doit rendre somme_versee - somme_due'''
    pieces = [1, 2, 5, 10, 20, 50, 100, 200]  
    rendu = []  
    a_rendre = somme_versee - somme_due
    i = len(pieces) - 1 
    
    while a_rendre > 0:
        while pieces[i] > a_rendre:
            i -= 1
        rendu.append(pieces[i])
        a_rendre -= pieces[i]
    
    return rendu

# Tests
assert rendu_monnaie(700, 700) == []
assert rendu_monnaie(102, 500) == [200, 100, 50, 20, 20, 5, 2, 1]

46_01.py

def recherche(tab, n):
    """Effectue une recherche dichotomique du nombre n dans le tableau tab.
    Renvoie l'indice correspondant au nombre cherché s'il est dans le tableau, None sinon."""
    debut = 0
    fin = len(tab) - 1
    
    while debut <= fin:
        milieu = (debut + fin) // 2
        if tab[milieu] == n:
            return milieu
        elif tab[milieu] < n:
            debut = milieu + 1
        else:
            fin = milieu - 1
    
    return None

# Tests
assert recherche([2, 3, 4, 5, 6], 5) == 3
assert recherche([2, 3, 4, 6, 7], 5) == None

46_02.py

ALPHABET = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
def position_alphabet(lettre):
    return ord(lettre) - ord('A')
def cesar(message, decalage):
    resultat = ''
    for c in message:
        if 'A' <= c and c <= 'Z':
            indice = (position_alphabet(c) + decalage) % 26
            resultat = resultat + ALPHABET[indice]
        else:
            resultat = resultat + c
    return resultat

# Tests
assert cesar('BONJOUR A TOUS. VIVE LA MATIERE NSI !', 4) == 'FSRNSYV E XSYW. ZMZI PE QEXMIVI RWM !'
assert cesar('GTSOTZW F YTZX. ANAJ QF RFYNJWJ SXN !', -5) == 'BONJOUR A TOUS. VIVE LA MATIERE NSI !'

47_01.py

def max_dico(dico):
    val_max = -float('inf')  
    cle_max = ''  
    
    for cle, val in dico.items():
        if val > val_max:
            cle_max = cle
            val_max = val
        elif val == val_max and cle < cle_max:
            cle_max = cle

    return (cle_max, val_max)

# Test
assert max_dico({ 'Bob': 102, 'Ada': 201, 'Alice': 103, 'Tim': 50 }) == ('Ada', 201)
assert max_dico({ 'Alan': 222, 'Ada': 201, 'Eve': 222, 'Tim': 50 }) == ('Alan', 222)

47_02.py

class Pile:
    """Classe définissant une structure de pile."""
    def __init__(self):
        self.contenu = []

    def est_vide(self):
        """Renvoie un booléen indiquant si la pile est vide."""
        return self.contenu == []

    def empiler(self, v):
        """Place l'élément v au sommet de la pile"""
        self.contenu.append(v)

    def depiler(self):
        """
        Retire et renvoie l'élément placé au sommet de la pile,
        si la pile n’est pas vide. Produit une erreur sinon.
        """
        assert not self.est_vide()
        return self.contenu.pop()

def eval_expression(tab):
    p = Pile()
    for element in tab:
        if isinstance(element, int):
            p.empiler(element)
        else:
            if element == '+':
                resultat = p.depiler() + p.depiler()
            else:
                resultat = p.depiler() * p.depiler()
            p.empiler(resultat)
    return p.depiler()

# Tests
assert eval_expression([2, 3, '+', 5, '*']) == 25
assert eval_expression([1, 2, '+', 3, '*']) == 9
assert eval_expression([1, 2, 3, '+', '*']) == 5

48_01.py

def voisins_entrants(adj, x):
    voisins = []
    for i in range(len(adj)):
        if x in adj[i]:
            voisins.append(i)
    return voisins

# Tests
assert voisins_entrants([[1, 2], [2], [0], [0]], 0) == [2, 3]
assert voisins_entrants([[1, 2], [2], [0], [0]], 1) == [0]

48_02.py

def nombre_suivant(s):
    resultat = ''
    chiffre = s[0]
    compte = 1
    for i in range(1, len(s)):
        if s[i] == chiffre:
            compte += 1
        else:
            resultat += str(compte) + chiffre
            chiffre = s[i]
            compte = 1
    lecture_chiffre = str(compte) + chiffre      
    resultat += lecture_chiffre
    return resultat

# Tests
assert nombre_suivant('1211') == '111221'
assert nombre_suivant('311') == '1321'

01_01.py

01_02.py

02_01.py

02_02.py

03_01.py

03_02.py

04_01.py

04_02.py

05_01.py

05_02.py

06_01.py

06_02.py

07_01.py

07_02.py

08_01.py

08_02.py

09_01.py

09_02.py

10_01.py

10_02.py

11_01.py

11_02.py

12_01.py

12_02.py

13_01.py

13_02.py

14_01.py

14_02.py

15_01.py

15_02.py

16_01.py

16_02.py

17_01.py

17_02.py

18_01.py

18_02.py

19_01.py

19_02.py

20_01.py

20_02.py

21_01.py

21_02.py

22_01.py

22_02.py

23_01.py

23_02.py

24_01.py

24_02.py

25_01.py

25_02.py

26_01.py

26_02.py

27_01.py

27_02.py

28_01.py

28_02.py

29_01.py

29_02.py

30_01.py

30_02.py

31_01.py

31_02.py

32_01.py

32_02.py

33_01.py

33_02.py

34_01.py

34_02.py

35_01.py

35_02.py

36_01.py

36_02.py

37_01.py

37_02.py

38_01.py

38_02.py

39_01.py

39_02.py

40_01.py

40_02.py