EP 2025 Correction

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]

01_02.py : Chaînes caractères (1er)

Sujet 2 :def nombre_suivant(s):
    '''Renvoie le nombre suivant de celui representé par s
    en appliquant le procédé de lecture.'''
    resultat = ''
    chiffre = s[0]
    compte = 1
    for i in range(...): 
        if s[i] == chiffre:
            compte = ... 
        else:
            resultat += ... + ... 
            chiffre = ... 
            ...
    lecture_... = ... + ... 
    resultat += lecture_chiffre
    return resultat


Correction :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'

02_01.py : Valeur et indice du maximum (1er)

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)

02_02.py : Ordre des gènes sur un chromosome (1er)

Sujet 2 :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 < ... or x >... or ...: 
            return False
        ... .append(...) 
    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 ... 
    n = len(ordre)
    nb = 0
    if ordre[...] != 1: # le premier n'est pas 1 
        nb = nb + 1
    i = 0
    while i < ...: 
        if ... not in [-1, 1]: # l'écart n'est pas 1 
            nb = nb + 1
        i = i + 1
    if ordre[i] != ...: # le dernier n'est pas n 
        nb = nb + 1
    return nb


Correction :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

03_01.py : Suite de Fibonacci (1er)

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

03_02.py : Liste élèves note maximale (1er)

Sujet 2 :def eleves_du_mois(eleves, notes):
    note_maxi = 0
    meilleurs_eleves = ... 

    for i in range(...): 
        if notes[i] == ...: 
            meilleurs_eleves.append(...) 
        elif notes[i] > note_maxi:
            note_maxi = ... 
            meilleurs_eleves = [...] 

    return (note_maxi, meilleurs_eleves)


Correction :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, [])

04_01.py : Conversion entier vers binaire (1er)

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'

04_02.py : Tri à Bulles (Tle)

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

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(...): 
        for j in range(...): 
            if ... > ...: 
                echange(tab, j, ...) 


Correction :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]

05_01.py : Ecriture d'une chaine de caractères à l'envers (1er)

def renverse(mot):
    chaine = ''
    for c in mot:
        chaine = c + chaine
    return chaine

# Assertions
assert renverse("") == ""
assert renverse("abc") == "cba"
assert renverse("informatique") == "euqitamrofni"

05_02.py : Crible d'Erasthotène (1er)

Sujet 2 :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(n):
        if tab[i]:
            premiers.... 
            multiple = ... 
            while multiple < n:
                tab[multiple] = ... 
                multiple = ... 
    return premiers


Correction :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]

06_01.py : Calcul de puissances (1er)

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) == []

06_02.py : Codage d'un mot - dictionnaire (1er)

Sujet 2 :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 = ... 
    for c in mot:
        code_concatene = code_concatene + ... 
        code_additionne = code_additionne + ... 
    code_concatene = int(code_concatene)
    mot_est_parfait = ... 
    return code_additionne, code_concatene, mot_est_parfait


Correction :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)

07_01.py : Nombre d'occurrences des caractères (1er)

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}

07_02.py : Tri fusion de deux listes triées (1er)

Sujet 2 :def fusion(tab1,tab2):
    '''Fusionne deux tableaux triés et renvoie
    le nouveau tableau trié.'''
    n1 = len(tab1)
    n2 = len(tab2)
    tab12 = [0] * (n1 + n2)
    i1 = 0
    i2 = 0
    i = 0
    while i1 < n1 and ...: 
        if tab1[i1] < tab2[i2]:
            tab12[i] = ... 
            i1 = ... 
        else:
            tab12[i] = tab2[i2]
            i2 = ... 
        i += 1
    while i1 < n1:
        tab12[i] = ... 
        i1 = i1 + 1
        i = ... 
    while i2 < n2:
        tab12[i] = ... 
        i2 = i2 + 1
        i = ... 
    return tab12


Correction :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]

08_01.py : Maximum des éléments d'un tableau (1er)

def maximum_tableau(tab):
    maxi = tab[0]
    for v in tab:
        if v > maxi:
            maxi = v
    return maxi

assert maximum_tableau([98, 12, 104, 23, 131, 9]) == 131
assert maximum_tableau([-27, 24, -3, 15]) == 24

08_02.py : Parenthésage correct POO Pile (Tle)

Sujet 2 :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 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():
                ...
            else:
                ...
    return ... 


Correction :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

09_01.py : Multiplications avec uniquement + et - (1er)

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

09_02.py : Recherche par dichotomique (1er)

Sujet 2 :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 = ... 
        if x == tab[m]:
            return ... 
        if x > tab[m]:
            debut = m + 1
        else:
            fin = ... 
    return ... 


Correction :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

10_01.py : Recherche dichotomique (1er)

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

10_02.py : Code de César (1er)

Sujet 2 :alphabet = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'

def position_alphabet(lettre):
    '''Renvoie la position de la lettre dans l'alphabet'''
    return ord(lettre) - ord('A')

def cesar(message, decalage):
    '''Renvoie le message codé par la méthode de César
    pour le decalage donné'''
    resultat = ''
    for ... in message: 
        if 'A' <= c and c <= 'Z':
            indice = (...) % 26 
            resultat = resultat + alphabet[indice]
        else:
            resultat = ... 
    return resultat


Correction :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 !'

11_01.py : Arbre binaire Parcours Largeur (Tle)

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]

11_02.py : Plus grande somme possible (Tle)

Sujet 2 :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] = ... 
        else:
            sommes_max[i] = ... 
    # on en déduit la plus grande somme de celles-ci
    maximum = 0
    for i in range(1, n):
        if ... > ...: 
            maximum = i

    return sommes_max[...] 


Correction :def somme_max(tab):
    n = len(tab)
    sommes_max = [0] * n
    sommes_max[0] = tab[0]
    for i in range(1, n):
        if tab[i] + sommes_max[i-1] > tab[i]:
            sommes_max[i] = tab[i] + sommes_max[i-1]
        else:
            sommes_max[i] = tab[i]
    maximum = 0
    for i in range(1, n):
        if sommes_max[i] > sommes_max[maximum]:
            maximum = i
    return sommes_max[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

12_01.py : Tri et fusion de deux listes triées (1er)

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]

12_02.py : Numération romaine Recursif et dictionnaires (Tle)

Sujet 2 :def traduire_romain(nombre):
    """ Renvoie l'écriture décimale du nombre donné en chiffres
    romains """
    if len(nombre) == 1:
        return ... 
    elif romains[nombre[0]] >= ...: 
        return romains[nombre[0]] + ... 
    else:
        return ... 


Correction :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

13_01.py : Recherche indice de la première occurrence (1er)

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 : Insertion dans une liste triée (1er)

Sujet 2 :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 < ... and a > ...: 
        tab_a[i] = ... 
        tab_a[i+1] = a
        i = ... 
    return tab_a


Correction :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 : Simulation de lancers de dés (1er)

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))

14_02.py : Représentation d'une image par une liste de listes (1er)

Sujet 2 :def nombre_lignes(image):
    '''renvoie le nombre de lignes de l'image'''
    return ... 

def nombre_colonnes(image):
    '''renvoie la largeur de l'image'''
    return ... 

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(...): 
            nouvelle_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 255 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(...): 
            if image[i][j] < ... : 
                nouvelle_image[i][j] = ... 
            else:
                nouvelle_image[i][j] = ... 
    return nouvelle_image


Correction :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]]

15_01.py : Multiplications avec uniquement + et - (1er)

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

15_02.py : Dichotomique récursive (Tle)

Sujet 2 :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) // ... 
    if ... < x: 
        return chercher(tab, x, ... , ...) 
    elif tab[m] > x:
        return chercher(tab, x, ... , ...) 
    else:
        return ... 


Correction :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

16_01.py : Moyenne pondérée (1er)

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

16_02.py : Triangle de Pascal (1er) Maths (Tle)

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

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


Correction :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]]

17_01.py : Fonction arbre récursive taille (Tle)

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

17_02.py : Insertion d'un élément dans une liste (1er)

Sujet 2 :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_ins[...] = ... 
    for i in range(indice + 1, nbre_elts + 1):
        tab_ins[i] = ... 
    return tab_ins


Correction :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]

18_01.py : Moyenne des éléments d'un tableau (1er)

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

18_02.py : Recherche par dichotomie (1er)

Sujet 2 :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 = ... 
    while debut <= fin:
        m = ... 
        if x == tab[m]:
            return ... 
        if x > tab[m]:
            debut = ... 
        else:
            fin = ... 
    return False


Correction :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

19_01.py : Première occurence du minimum (1er)

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

19_02.py : Separation des 0 et des 1 dans un tableau (Erreur!) (1er)

Sujet 2 :def separe(tab):
    '''Separe les 0 et les 1 dans le tableau tab'''
    gauche = 0
    droite = ... 
    while gauche < droite:
        if tab[gauche] == 0 :
            gauche = ... 
        else :
            tab[gauche] = ... 
            tab[droite] = ... 
            droite = ... 
    return tab


Correction :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([]) == []

20_01.py : Minimum et maximum (1er)

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}

20_02.py : Cartes à jouer POO (Tle)

Sujet 2 :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. """
        ...
        ...
            ...
                ...

    def recuperer_carte(self, pos):
        """ Renvoie la carte qui se trouve à la position pos 
        (entier compris entre 0 et 51). """
        ...
        ...


Correction :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)

21_01.py : Liste des indices du maximum (1er)

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])

21_02.py : Pile des éléments positifs (Tle)

Sujet 2 :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 != []:
        ... .append(...) 
    return ... 


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 != []:
        ... = pile.pop() 
        if ... >= 0: 
            ...
    return ... 


Correction :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]) == []

22_01.py : Indice de la dernière occurence (1er)

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

22_02.py : Classe des adresse IP POO (Tle)

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

    def liste_octets(self):
        """renvoie une liste de nombres entiers,
        la liste des octets de l'adresse IP"""
        # Note : split découpe la chaine de caractères 
        # en fonction du séparateur
        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 = [ ... ] 
        return ... 

    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 = ... 
        if ... == 254: 
            return None
        octet_nouveau = ... + ... 
        return AdresseIP('192.168.0.' + ...) 

Correction :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'

23_01.py : Trier par ordre croissant (1er)

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]

23_02.py : Fonctions récursives dec_to_bin et bin_to_dec (Tle)

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

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


Correction :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

24_01.py : Renvoie d'un dictionnaire (1er)

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]}

24_02.py : Arbre Binaire parcours profondeur insertion POO (Tle)

Sujet 2 :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 != 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 == None:
        return Noeud(cle, None, None) # creation d'une feuille
    else:
        if ...: 
            arbre.gauche = insere(arbre.gauche, cle)
        else:
            arbre.droit = ... 
        return arbre


Correction :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, []))

25_01.py : Minimum d'une liste de température (1er)

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)

25_02.py : Chaînes caractères : Palindromes (1er)

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

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

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



Correction :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

26_01.py : Fusion de deux dictionnaires (1er)

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 : Simulation d'un jeu de dés (1er)

Sujet 2 :from random import randint

def nombre_coups():
    '''Simule un jeu de plateau avec 12 cases et renvoie le nombre
    nécessaire 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 = ... 
    while ... < ...: 
        x = randint(1, 6)
        case_en_cours = (case_en_cours + ...) % ... 
        if ...: 
            cases_vues[case_en_cours] = True
            nombre_cases_vues = ... 
        n = ... 
    return n

Correction :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 : Liste est triée ou non (1er)

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

27_02.py : Comptabilisation de votes (1er)

Sujet 2 :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 ...: 
            resultat[bulletin] = resultat[bulletin] + 1
        else:
            ...
    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 ... > ... : 
            nmax = ... 
    liste_finale = [ nom for nom in election if ... ] 
    return ... 


Correction :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']

28_01.py : Doublons dans une liste triée (1er)

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

28_02.py : Grille au démineur (1er)

Sujet 2 :def voisinage(n, ligne, colonne):
    """ Renvoie la liste des coordonnées des voisins de la case
    (ligne, colonne) dans un grille de taille n x n,
    en tenant compte des cases sur les bords. """
    voisins = []
    for dl in range(-1, 2):
        for dc in range(-1, 2):
            l = ligne + dl
            c = colonne + dc
            if (l, c) != (ligne, colonne) \
                    and 0 <= l < n and 0 <= c < n:
                voisins.append((l,c))
    return voisins

def incremente_voisins(grille, ligne, colonne):
    """ Incrémente de 1 toutes les cases voisines d'une bombe."""
    voisins = ... 
    for l, c in voisins:
        if grille[l][c] != ...: # si ce n'est pas une bombe 
            ...  # 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 colonne in range(n)] for ligne in range(n)]
    # Place les bombes et calcule les valeurs des autres cases
    for ligne, colonne in bombes:
        grille[ligne][colonne] = ... # place la bombe 
        ...  # incrémente ses voisins 
    return grille


Correction :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]]

29_01.py : Traitement de données en table (1er)

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) == []

29_02.py : Recherche récursive dans un tableau (Tle)

Sujet 2 :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 ... 
    else:
        nombre_de_triplets = (d - g) // ... 
        indice = g + 3 * (nombre_de_triplets // 2)
        if ...: 
            return ... 
        else:
            return ... 


Correction :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

30_01.py : Codage par différence (1er)

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]

30_02.py : Expression arithmétique Recursif POO arbre (Tle)

Sujet 2 :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érateur 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 + '(' + ... .infixe() 
        s = s + ... 
        if ... is not None: 
            s = s + ... + ... 
        return s


Correction :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))'

31_01.py : Recherche Motif dans Texte (Tle)

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]

31_02.py : Graphe liste d’adjacence parcours profondeur (Tle)

Sujet 2 :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 ...: 
        acc.append(x)
        for y in ...: 
            parcours(adj, ...) 

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, ...) 
    return acc


Correction :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]

32_01.py : Nombre d'occurrences dans une liste (1er)

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

32_02.py : Rendu de monnaie Glouton Recursivité (Tle)

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

def rendu_glouton(a_rendre, rang):
    if a_rendre == 0:
        return ... 
    v = valeurs[rang]
    if v <= ...: 
        return ... + rendu_glouton(a_rendre - v, rang) 
    else:
        return rendu_glouton(a_rendre, ...) 


Correction :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]

33_01.py : Ajout d'une clé dans un arbre binaire POO (Tle)

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)))

33_02.py : Fonction empaqueter Glouton (1er)

Sujet 2 :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 ...: 
        i = 0
        while i < nb_boites and boites[i] + ... > c: 
            i = i + 1
        if i == nb_boites:
            ...
        boites[i] = ... 
    return ... 


Correction :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

34_01.py : Tri par sélection (1er)

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]

34_02.py : Jeu du plus ou moins (1er)

Sujet 2 :from random import randint

def plus_ou_moins():
    nb_mystere = randint(1, ...) 
    nb_test = int(input("Proposez un nombre entre 1 et 99 : "))
    compteur = ... 

    while nb_mystere != ... and compteur < ...: 
        compteur = 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 ", ...) 
        print("Nombre d'essais: ", ...) 
    else:
        print ("Perdu ! Le nombre était ", ...) 

Correction :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)

35_01.py : Maximum des valeurs d'un dictionnaire (1er)

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)

35_02.py : Fonction eval_expression POO Piles (Tle)

Sujet 2 :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 ... in tab: 
        if element != '+' ... element != '*': 
            p.empiler(...) 
        else:
            if element == ...: 
                resultat = ... + ... 
            else:
                resultat = ... 
            p.empiler(...) 
    return ... 


Correction :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 element != '+' and element != '*':
            p.empiler(element)
        else:
            if element == '+':
                resultat = p.depiler() + p.depiler()
            else:
                resultat = p.depiler() * p.depiler()
            p.empiler(resultat)
    return p.depiler()

print(eval_expression([2, 3, '+', 5, '*']))  # Résultat attendu : 25
print(eval_expression([1, 2, '+', 3, '*']))  # Résultat attendu : 9
print(eval_expression([1, 2, 3, '+', '*']))  # Résultat attendu : 5

36_01.py : Nombre de mots dans une phrase (1er)

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

36_02.py : Insérer une clé dans ABR POO (Tle)

Sujet 2 :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 != None:
                ...
            else:
                self.gauche = ... 
        else:
            ...
                ...
            else:
                ... = Noeud(cle) 


Correction :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

37_01.py : Représentation binaire d’un entier (1er)

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

37_02.py : Tri par insertion (1er)

Sujet 2 :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 = ... 
        # la variable j sert à déterminer 
        # où placer la valeur à ranger
        j = ... 
        # 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 > ... and valeur_insertion < tab[...]: 
            tab[j] = tab[j-1]
            j = ... 
        tab[j] = ... 


Correction :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]

38_01.py : Calcul de moyenne (1er)

def moyenne(tab):
    total = 0
    for valeur in tab:
        total += valeur
    return total / len(tab)

# Exemples d'utilisation
assert moyenne([1.0]) == 1.0
assert moyenne([1.0, 2.0, 4.0]) == 2.3333333333333335

38_02.py : Conversion du décimal vers le binaire (1er)

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


Correction :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'

39_01.py : Calcul d'une moyenne (1er)

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

39_02.py : Séparation des 0 et des 1 dans un tableau (1er)

Sujet 2 :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 = ... # premier indice de la zone non triée 
    j = ... # dernier indice de la zone non triée 
    while i < j:
        if tab[i] == 0:
            i = ... 
        else:
            valeur = ... 
            tab[j] = ... 
            ...
            j = ... 


Correction :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]

40_01.py : Liste des indices < > = à une valeur (1er)

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, []) == ([], [], [])

40_02.py : Calcul de moyenne (dictionnaire) (1er)

Sujet 2 :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]
    }
}

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 ...: 
        notes = resultats[nom]
        if ...: # pas de notes 
            return 0
        total_points = ... 
        total_coefficients = ... 
        for ...  in notes.values(): 
            note, coefficient = valeurs
            total_points = total_points + ... * coefficient 
            ... = ... + coefficient 
        return round( ... / total_coefficients, 1 ) 
    else:
        return None


Correction :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

41_01.py : XOR de 2 listes de bits (1er)

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]

41_02.py : Carrés semi-magiques POO (Tle)

Sujet 2 :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''' 
        somme = 0             
                                   
        for j in range(self.ordre): 
            somme = somme + self.tableau[i][j] 
        return somme          
                                   
    def somme_col(self, j):   
        '''Calcule la somme des valeurs de la colonne j''' 
        somme = 0
                                   
        for i in range(self.ordre): 
            somme = somme + self.tableau[i][j] 
        return somme          
                                   
                                   
    def est_semimagique(self): 
        s = self.somme_ligne(0) 
        #test de la somme de chaque ligne 
        for i in range(...): 
            if ... != s: 
                return ... 
                                   
        #test de la somme de chaque colonne 
        for j in range(...): 
            if ... != s: 
                return ... 
                                   
        return ... 


Correction :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"

42_01.py : Nombre d'occurrences dans une liste (1er)

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

42_02.py : Conversion entier vers binaire (1er)

Sujet 2 :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 ...: 
        bin_a = ... + bin_a 
        a = ... 
    return bin_a



Correction :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'

43_01.py : Liste des couples d'entiers consécutifs (1er)

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)]

43_02.py : Codage d'une image (1er)

Sujet 2 :def colore_comp1(M, i, j, val):
    if M[i][j] != 1:
        return

    M[i][j] = val

    if i-1 >= 0: # propage en haut
        colore_comp1(M, i-1, j, val)
    if ... < len(M): # propage en bas 
        colore_comp1(M, ..., j, val) 
    if ...: # propage à gauche 
        colore_comp1(M, ..., ..., val) 
    if ...: # propage à droite 
        ...


Correction :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]]

44_01.py : Moyenne pondérée (1er)

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

44_02.py : Figure « cœur » liste_zoom et dessin_zoom (1er)

Sujet 2 :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]]

def affiche(dessin):
    ''' affichage d'une grille : les 1 sont représentés par 
        un "*" , les 0 par une 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 ... : 
        for i in range(k):
            ...
    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 = ... 
        for i in range(k):
            ... .append(...) 
    return grille_zoomee


Correction :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))

45_01.py : Mot à trous (1er)

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

45_02.py : est_cyclique (1er)

Sujet 2 :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[...] 
    nb_destinataires = 1

    while destinataire != expediteur:
        destinataire = ... 
        nb_destinataires = ... 

    return nb_destinataires == ... 


Correction :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

46_01.py : Nombre d'occurrences dans une liste (1er)

# 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

46_02.py : Glouton : Rendu de monnaie (1er)

Sujet 2 :pieces = [1, 2, 5, 10, 20, 50, 100, 200]

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'''
    rendu = ... 
    a_rendre = ... 
    i = len(pieces) - 1
    while a_rendre > ...: 
        while pieces[i] > a_rendre:
            i = i - 1
        rendu.append(...) 
        a_rendre = ... 
    return rendu


Correction :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]

47_01.py : Taille d'un arbre binaire (Tle)

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

47_02.py : Tri par sélection (1er)

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

def tri_selection(tab):
    '''Trie le tableau tab dans l'ordre croissant
    par la méthode du tri par sélection.'''
    N = len(tab)
    for k in range(...): 
        imin = ... 
        for i in range(..., N): 
            if tab[i] < ...: 
                imin = i
        echange(tab, ..., ...) 


Correction :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]

48_01.py : Dernière occurrence (1er)

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

assert recherche([5, 3],1) == None
assert recherche([2,4],2) == 0
assert recherche([2,3,5,2,4],2) == 3

48_02.py : point_le_plus_proche (1er)

Sujet 2 :def distance_carre(point1, point2):
    """ Calcule et renvoie la distance au carre entre 
    deux points."""
    return (...)**2 + (...)**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 = ... 
    for i in range(1, len(tab)):
        if distance_carre(tab[i], depart) < ...: 
            min_point = ... 
            min_dist = ... 
    return min_point


Correction :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)