Exercice 1: ★ ★ ★ ★ ★

On considère dans cet exercice un graphe orienté représenté sous forme de listes d’adjacence. On suppose que les sommets sont numérotés de 0 à n-1. Par exemple, le graphe suivant :

est représenté par la liste d’adjacence suivante:
adj = [[1, 2], [2], [0], [0]]

Écrire une fonction voisins_entrants(adj, x) qui prend en paramètre le graphe donné sous forme de liste d’adjacence et qui renvoie une liste contenant les voisins entrants du sommet x, c’est-à-dire les sommets y tels qu’il existe une arête de y vers x.

def voisins_entrants(adj, x):
    return [i for i, voisins in enumerate(adj) if x in voisins]
	

Exercice 2: ★ ★ ★ ★ ★

On considère dans cet exercice la suite de nombres suivante : 1, 11, 21, 1211, 111221, … Cette suite est construite ainsi : pour passer d’une valeur à la suivante, on la lit et on l’écrit sous la forme d’un nombre. Ainsi, pour 1211 :
                • on lit un 1, un 2, deux 1 ;
                • on écrit donc en nombre 1 1, 1 2, 2 1 ;
                • puis on concatène 111221.
Compléter la fonction nombre_suivant(s) qui prend en entrée un nombre sous forme de chaîne de caractère et qui renvoie le nombre suivant par ce procédé, encore sous forme de chaîne de caractère.

def nombre_suivant(s):
    '''Renvoie le nombre suivant de celui représenté 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

def nombre_suivant(s):
    '''Renvoie le nombre suivant de celui représenté par s
    en appliquant le procédé de lecture.'''
    resultat = ''
    chiffre = s[0]
    compte = 1
    for i in range(1, len(s)):
        if s[i] == chiffre:
            compte = compte + 1
        else:
            resultat += str(compte) + chiffre
            chiffre = s[i]
            compte = 1
    resultat += str(compte) + chiffre
    return resultat

Exercice 1: ★ ★ ★ ★ ★

Écrire une fonction max_et_indice qui prend en paramètre un tableau non vide tab (type Python list) de nombres entiers et qui renvoie la valeur du plus grand élément de ce tableau ainsi que l'indice de sa première apparition dans ce tableau. L'utilisation de la fonction native max n'est pas autorisée.

Exemples :

def max_et_indice(tab):
    """
    Recherche le maximum et son premier indice dans un tableau
    Args:
        tab (list): tableau non vide d'entiers
    Returns:
        tuple: (valeur_max, indice_première_occurrence)
    """
    # Initialisation avec le premier élément
    max_val = tab[0]  # On part du principe que le max est le premier élément
    index = 0         # Son indice est donc 0
    
    # Parcours du reste du tableau
    for i in range(1, len(tab)):
        # Si on trouve un élément plus grand
        if tab[i] > max_val:
            max_val = tab[i]  # On met à jour le maximum
            index = i        # Et on enregistre son indice
    
    # Retour du résultat sous forme de tuple
    return max_val, index

Exercice 2: ★ ★ ★ ★ ★

L’ordre des gènes sur un chromosome est représenté par un tableau ordre de n cases d’entiers distincts deux à deux et compris entre 1 et n. Par exemple, ordre = [5, 4, 3, 6, 7, 2, 1, 8, 9] dans le cas n = 9.

On dit qu’il y a un point de rupture dans ordre dans chacune des situations suivantes :

•                 1️⃣ la première valeur de ordre n’est pas 1 ;
•                 2️⃣ l’écart entre deux gènes consécutifs n’est pas égal à 1 ;
•                 3️⃣ la dernière valeur de ordre n’est pas n.

Par exemple, si ordre = [5, 4, 3, 6, 7, 2, 1, 8, 9] avec n = 9, on a :

•                 1️⃣ un point de rupture au début car 5 est différent de 1
•                 2️⃣ un point de rupture entre 3 et 6 (l’écart est de 3)
•                 3️⃣ un point de rupture entre 7 et 2 (l’écart est de 5)
•                 4️⃣ un point de rupture entre 1 et 8 (l’écart est de 7)

Il y a donc 4 points de rupture.

Compléter les fonctions Python est_un_ordre et nombre_points_rupture proposées ci-dessous :

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

# Exemples :
# >>> est_un_ordre([1, 6, 2, 8, 3, 7])
# False
# >>> est_un_ordre([5, 4, 3, 6, 7, 2, 1, 8, 9])
# True
# >>> nombre_points_rupture([5, 4, 3, 6, 7, 2, 1, 8, 9])
# 4
# >>> nombre_points_rupture([1, 2, 3, 4, 5])
# 0
# >>> nombre_points_rupture([1, 6, 2, 8, 3, 7, 4, 5])
# 7
# >>> nombre_points_rupture([2, 1, 3, 4])
# 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)
    vus = []  # Liste pour suivre les éléments déjà rencontrés
    for x in tab:
        # Vérifie trois conditions cumulatives :
        # 1. x doit être ≥ 1
        # 2. x doit être ≤ n
        # 3. x ne doit pas être déjà dans la liste
        if x < 1 or x > n or x in vus:
            return False
        vus.append(x)  # Ajoute l'élément valide à la liste
    return True  # Si toutes les vérifications passent


def nombre_points_rupture(ordre):
    '''
    Renvoie le nombre de point de rupture de ordre qui représente
    un ordre de gènes de chromosome
    '''
    # Vérification préalable que l'ordre est valide
    assert est_un_ordre(ordre)  
    
    n = len(ordre)
    nb = 0  # Initialisation du compteur de points de rupture
    
    # Point de rupture 1: le premier élément doit être 1
    if ordre[0] != 1:
        nb += 1
    
    # Parcours des éléments consécutifs
    for i in range(n - 1):
        # Point de rupture 2: écart entre éléments consécutifs doit être ±1
        if abs(ordre[i] - ordre[i + 1]) != 1:
            nb += 1
    
    # Point de rupture 3: le dernier élément doit être n
    if ordre[-1] != n:
        nb += 1
    
    return nb  # Retourne le total des points de rupture

Exercice 1: ★ ★ ★ ★ ★

On s’intéresse à la suite d’entiers définie par :

•         1️⃣ les deux premières valeurs sont égales à 1 ;
•         2️⃣ ensuite, chaque valeur est obtenue en faisant la somme des deux valeurs qui la précèdent.

La troisième valeur est donc 1+1 = 2, la quatrième est 1+2 = 3, la cinquième est 2+3 = 5, la sixième est 3 + 5 = 8, et ainsi de suite.
Cette suite d’entiers est connue sous le nom de suite de Fibonacci.

Écrire en Python une fonction fibonacci qui prend en paramètre un entier n supposé strictement positif et qui renvoie le terme d’indice n de cette suite.

Exemples :

def fibonacci(n):
    """
    Calcul de la suite de Fibonacci
    Args:
        n (int): indice du terme à calculer
    Returns:
        int: le terme d'indice n de la suite
    """
    # Cas de base
    if n == 1 or n == 2:
        return 1
    # Initialisation des deux premiers termes
    a, b = 1, 1
    # Calcul des termes suivants
    for _ in range(3, n + 1):
        a, b = b, a + b
    return b

Exercice 2: ★ ★ ★ ★ ★

On considère la fonction eleves_du_mois prenant en paramètres eleves et notes deux tableaux non vides de même longueur, le premier contenant le nom des élèves et le second, des entiers positifs désignant leur note à un contrôle de sorte que eleves[i] a obtenu la note notes[i].

Cette fonction renvoie le couple constitué de la note maximale attribuée et des noms des élèves ayant obtenu cette note regroupés dans un tableau.

Compléter le code suivant :

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)

Exemples :

def eleves_du_mois(eleves, notes):
    note_maxi = 0
    meilleurs_eleves = []  # Liste pour stocker les meilleurs élèves
    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)

Exercice 1: ★ ★ ★ ★ ★

Écrire une fonction ecriture_binaire_entier_positif qui prend en paramètre un entier positif n et renvoie une chaîne de caractères correspondant à l’écriture binaire de n.

On rappelle que :

• l’écriture binaire de 25 est 11001 car 25 = 1 × 2⁴ + 1 × 2³ + 0 × 2² + 0 × 2¹ + 1 × 2⁰;
• n % 2 vaut 0 ou 1 selon que n est pair ou impair ;
• n // 2 donne le quotient de la division euclidienne de n par 2.

Il est interdit dans cet exercice d’utiliser la fonction bin de Python.

Exemples :

def ecriture_binaire_entier_positif(n):
    """
    Convertit un entier positif en chaîne binaire
    Args:
        n (int): entier positif
    Returns:
        str: représentation binaire de n
    """
    # Cas spécial pour n = 0
    if n == 0:
        return '0'
    # Initialisation de la chaîne binaire
    binaire = ''
    # Boucle pour construire la chaîne binaire
    while n > 0:
        binaire = str(n % 2) + binaire
        n //= 2
    return binaire

Exercice 2: ★ ★ ★ ★ ★

La fonction tri_bulles prend en paramètre un tableau tab d’entiers (type list) et le modifie pour le trier par ordre croissant.

Le tri à bulles est un tri en place qui commence par placer le plus grand élément en dernière position en parcourant le tableau de gauche à droite et en échangeant au passage les éléments voisins mal ordonnés (si la valeur de l’élément d’indice i a une valeur strictement supérieure à celle de l’indice i + 1, ils sont échangés).

Compléter le code Python ci-dessous qui implémente la fonction tri_bulles.

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

Exemples :

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):
        for j in range(n - 1 - i):
            if tab[j] > tab[j + 1]:
                echange(tab, j, j + 1)

Exercice 1: ★ ★ ★ ★ ★

Programmer une fonction renverse, prenant en paramètre une chaîne de caractères non vide mot et renvoie cette chaîne de caractères en ordre inverse.

Exemple :

def renverse(mot):
    """
    Renverse une chaîne de caractères
    Args:
        mot (str): chaîne de caractères à renverser
    Returns:
        str: chaîne de caractères renversée
    """
    # Utilisation de la notation par tranches pour inverser
    return mot[::-1]

Exercice 2: ★ ★ ★ ★ ★

Un nombre premier est un nombre entier naturel qui admet exactement deux diviseurs distincts entiers et positifs : 1 et lui-même.

Le crible d’Ératosthène permet de déterminer les nombres premiers plus petits qu’un certain nombre n fixé strictement supérieur à 1.

On dispose de la fonction crible, donnée ci-dessous et à compléter, prenant en paramètre un entier n strictement supérieur à 1 et renvoyant un tableau contenant tous les nombres premiers plus petits que n.

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

Exemples :

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.append(i)  # Ajoute i à la liste des premiers
            multiple = 2 * i  # Commence à marquer les multiples de i
            while multiple < n:
                tab[multiple] = False  # Marque le multiple comme non premier
                multiple += i  # Passe au multiple suivant
    return premiers

Exercice 1: ★ ★ ★ ★ ★

On rappelle que :

• le nombre an est le nombre a × a × a × ⋯ × a, où le facteur a apparaît n fois,
• en langage Python, l’instruction t[-1] permet d’accéder au dernier élément du tableau t.

Dans cet exercice, l’opérateur ** et la fonction pow ne sont pas autorisés.

Programmer en langage Python une fonction liste_puissances qui prend en argument un nombre entier a, un entier strictement positif n et qui renvoie la liste de ses puissances [a1, a2, ..., an].

Programmer également une fonction liste_puissances_borne qui prend en argument un nombre entier a supérieur ou égal à 2 et un entier borne, et qui renvoie la liste de ses puissances, à l’exclusion de a0, strictement inférieures à borne.

Exemples :

def liste_puissances(a, n):
    puissances = []
    # Calcul des puissances
    for i in range(1, n + 1):
        valeur = 1
        for _ in range(i):
            valeur *= a
        puissances.append(valeur)
    return puissances

def liste_puissances_borne(a, borne):
    puissances = []
    # Calcul des puissances jusqu'à la borne
    valeur = a
    while valeur < borne:
        puissances.append(valeur)
        valeur *= a
    return puissances

Exercice 2: ★ ★ ★ ★ ★

On affecte à chaque lettre de l’alphabet un code selon le tableau ci-dessous :

Pour un mot donné, on détermine d’une part son code alphabétique concaténé, obtenu par la juxtaposition des codes de chacun de ses caractères, et d’autre part, son code additionné, qui est la somme des codes de chacun de ses caractères.

Par ailleurs, on dit que ce mot est « parfait » si le code additionné divise le code concaténé.

Compléter la fonction codes_parfait qui prend en paramètre un mot en majuscule et renvoie un triplet constitué du code additionné, du code concaténé et d’un booléen indiquant si le mot est parfait ou non.

def codes_parfait(mot):
    '''Renvoie le code additionné, le code concaténé et un booléen indiquant si le mot est parfait.'''
    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}
    code_concatene = ...
    code_additionne = ...
    parfait = ...
    return (code_additionne, code_concatene, parfait)

Exemples :

def codes_parfait(mot):
    '''Renvoie le code additionné, le code concaténé et un booléen indiquant si le mot est parfait.'''
    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}
    code_concatene = ''
    code_additionne = 0
    # Calcul des codes
    for char in mot:
        code_concatene += str(dico[char])
        code_additionne += dico[char]
    parfait = int(code_concatene) % code_additionne == 0
    return (code_additionne, code_concatene, parfait)

Exercice 1: ★ ★ ★ ★ ★

Le nombre d’occurrences d’un caractère dans une chaîne de caractère est le nombre d’apparitions de ce caractère dans la chaîne.

Exemples :

•         1️⃣ le nombre d’occurrences du caractère 'o' dans 'bonjour' est 2 ;
•         2️⃣ le nombre d’occurrences du caractère 'b' dans 'Bébé' est 1 ;
•         3️⃣ le nombre d’occurrences du caractère 'B' dans 'Bébé' est 1 ;
•         4️⃣ le nombre d’occurrences du caractère ' ' dans 'Hello world !' est 2.

On cherche les occurrences des caractères dans une phrase. On souhaite stocker ces occurrences dans un dictionnaire dont les clefs seraient les caractères de la phrase et les valeurs l’occurrence de ces caractères.

Écrire une fonction nbr_occurrences prenant comme paramètre une chaîne de caractères chaine et renvoyant le dictionnaire des nombres d’occurrences des caractères de cette chaîne.

def nbr_occurrences(chaine):
    """
    Compte les occurrences des caractères dans une chaîne
    Args:
        chaine (str): chaîne de caractères à analyser
    Returns:
        dict: dictionnaire des occurrences des caractères
    """
    # Initialisation du dictionnaire
    occurrences = {}
    # Parcours de chaque caractère dans la chaîne
    for char in chaine:
        # Incrémente l'occurrence du caractère
        occurrences[char] = occurrences.get(char, 0) + 1
    return occurrences

Exercice 2: ★ ★ ★ ★ ★

La fonction fusion prend deux tableaux tab1, tab2 (type list) d’entiers triés par ordre croissant et les fusionne en un tableau trié tab12 qu’elle renvoie.

Compléter le code de la fonction fusion ci-dessous.

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

Exemple :

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 i2 < n2: 
        if tab1[i1] < tab2[i2]:
            tab12[i] = tab1[i1] 
            i1 += 1 
        else:
            tab12[i] = tab2[i2]
            i2 += 1 
        i += 1
    while i1 < n1:
        tab12[i] = tab1[i1] 
        i1 += 1
        i += 1 
    while i2 < n2:
        tab12[i] = tab2[i2] 
        i2 += 1
        i += 1 
    return tab12

Exercice 1: ★ ★ ★ ★ ★

Écrire la fonction maximum_tableau, prenant en paramètre un tableau non vide de nombres tab (de type list) et renvoyant le plus grand élément de ce tableau.

Exemples :

def maximum_tableau(tab):
    """
    Renvoie le plus grand élément d'un tableau
    Args:
        tab (list): tableau non vide de nombres
    Returns:
        int: le plus grand élément
    """
    # Initialisation avec le premier élément
    max_val = tab[0]
    # Parcours du tableau pour trouver le maximum
    for num in tab:
        if num > max_val:
            max_val = num
    return max_val

Exercice 2: ★ ★ ★ ★ ★

On dispose de chaînes de caractères contenant uniquement des parenthèses ouvrantes et fermantes.

Un parenthésage est correct si :

• le nombre de parenthèses ouvrantes de la chaîne est égal au nombre de parenthèses fermantes ;
• en parcourant la chaîne de gauche à droite, le nombre de parenthèses déjà ouvertes doit être, à tout moment, supérieur ou égal au nombre de parenthèses déjà fermées.

Compléter le code de la fonction bon_parenthesage ci-dessous :

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

Exemples :

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

Exercice 1: ★ ★ ★ ★ ★

Programmer la fonction multiplication, prenant en paramètres deux nombres entiers relatifs n1 et n2, et qui renvoie le produit de ces deux nombres.

Les seules opérations autorisées sont l’addition et la soustraction.

Exemples :

def multiplication(n1, n2):
    """
    Calcule le produit de deux entiers
    Args:
        n1 (int): premier entier
        n2 (int): deuxième entier
    Returns:
        int: produit de n1 et n2
    """
    
    # Gérer le cas où n2 est négatif
    if n2 < 0:
        return -multiplication(n1, -n2)

    # Initialisation du produit
    produit = 0
    # Additionner n1, n2 fois
    for _ in range(n2):
        produit += n1
    return produit

Exercice 2: ★ ★ ★ ★ ★

On s’intéresse dans cet exercice à la recherche dichotomique dans un tableau trié d’entiers.

Compléter la fonction suivante en respectant la spécification.

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

Exemples :

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  # Calcul de l'indice médian
        if x == tab[m]:
            return True  # x trouvé
        if x > tab[m]:
            debut = m + 1
        else:
            fin = m - 1  # Ajustement de l'intervalle
    return False  # x non trouvé

Exercice 1: ★ ★ ★ ★ ★

Écrire une fonction recherche qui prend en paramètres un tableau tab de nombres entiers triés par ordre croissant et un nombre entier n, et qui effectue une recherche dichotomique du nombre entier n dans le tableau non vide tab.

Cette fonction doit renvoyer un indice correspondant au nombre cherché s’il est dans le tableau, None sinon.

Exemples :

def recherche(tab, n):
    """
    Recherche dichotomique d'un entier dans un tableau trié
    Args:
        tab (list): tableau trié d'entiers
        n (int): nombre à rechercher
    Returns:
        int or None: indice de n ou None
    """
    gauche, droite = 0, len(tab) - 1
    while gauche <= droite:
        milieu = (gauche + droite) // 2
        if tab[milieu] == n:
            return milieu
        elif tab[milieu] < n:
            gauche = milieu + 1
        else:
            droite = milieu - 1
    return None

Exercice 2: ★ ★ ★ ★ ★

Le codage de César transforme un message en changeant chaque lettre en la décalant dans l’alphabet. Par exemple, avec un décalage de 3, le A se transforme en D, le B en E, …, le X en A, le Y en B et le Z en C. Les autres caractères (‘!’,’ ?’ …) ne sont pas codés.

Compléter la fonction cesar ci-dessous, prenant en paramètre une chaîne de caractères message et un nombre entier decalage et renvoyant le nouveau message codé avec le codage de César utilisant le décalage decalage.

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

Exemples :

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

Exercice 1: ★ ★ ★ ★ ★

Un arbre binaire est soit vide, représenté en Python par la valeur None, soit un noeud représenté par un triplet (g, x, d) où x est l’étiquette du noeud et g et d sont les sous-arbres gauche et droit.

On souhaite écrire une fonction parcours_largeur qui prend en paramètre un arbre binaire et qui renvoie la liste des étiquettes des noeuds de l’arbre parcourus en largeur.

Exemples :

def parcours_largeur(arbre):
    """
    Effectue un parcours en largeur d'un arbre binaire
    Args:
        arbre (tuple): arbre binaire
    Returns:
        list: étiquettes des noeuds en ordre de parcours
    """
    if arbre is None:
        return []
    
    # Initialisation de la file et du résultat
    file = [arbre]
    result = []
    
    # Parcours en largeur
    while file:
        noeud = file.pop(0)
        g, x, d = noeud
        result.append(x)  # Ajoute l'étiquette du noeud
        if g:
            file.append(g)  # Ajoute le sous-arbre gauche à la file
        if d:
            file.append(d)  # Ajoute le sous-arbre droit à la file
    
    return result

Exercice 2: ★ ★ ★ ★ ★

On considère un tableau non vide de nombres entiers, positifs ou négatifs, et on souhaite déterminer la plus grande somme possible de ses éléments consécutifs.

Compléter la fonction somme_max ci-dessous qui réalise cet algorithme.

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[...]

Exemples :

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

Exercice 1: ★ ★ ★ ★ ★

Programmer la fonction fusion prenant en paramètres deux tableaux non vides tab1 et tab2 (type list) d’entiers, chacun dans l’ordre croissant, et renvoyant un tableau trié dans l’ordre croissant et contenant l’ensemble des valeurs de tab1 et tab2.

Exemples :

def fusion(tab1, tab2):
    """
    Fusionne deux tableaux triés dans l'ordre croissant
    Args:
        tab1 (list): premier tableau d'entiers
        tab2 (list): second tableau d'entiers
    Returns:
        list: tableau fusionné et trié
    """
    
    # Initialisation des index et du tableau résultat
    i, j = 0, 0
    resultat = []

    # Fusion des deux tableaux
    while i < len(tab1) and j < len(tab2):
        if tab1[i] < tab2[j]:
            resultat.append(tab1[i])
            i += 1
        else:
            resultat.append(tab2[j])
            j += 1

    # Ajout des éléments restants
    resultat.extend(tab1[i:])
    resultat.extend(tab2[j:])

    return resultat

Exercice 2: ★ ★ ★ ★ ★

Le but de cet exercice est d’écrire une fonction récursive traduire_romain qui prend en paramètre une chaîne de caractères, non vide, représentant un nombre écrit en chiffres romains et qui renvoie son écriture décimale.

Les chiffres romains considérés sont : I, V, X, L, C, D et M. Ils représentent respectivement les nombres 1, 5, 10, 50, 100, 500, et 1000 en base dix.

On dispose d’un dictionnaire romains dont les clés sont les caractères apparaissant dans l’écriture en chiffres romains et les valeurs sont les nombres entiers associés :

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

Compléter le code de la fonction traduire_romain :

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

Exemples :

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

Exercice 1: ★ ★ ★ ★ ★

Écrire une fonction recherche qui prend en paramètres elt (nombre entier) et tab (un tableau de nombres entiers, type list), et qui renvoie l’indice de la première occurrence de elt dans tab si elt est dans tab et None sinon.

L’objectif de cet exercice est de parcourir un tableau, il est interdit d’utiliser la méthode index des listes Python.

Exemples :

def recherche(elt, tab):
    """
    Recherche l'indice de la première occurrence de elt dans tab
    Args:
        elt (int): élément à rechercher
        tab (list): tableau d'entiers
    Returns:
        int or None: indice de la première occurrence ou None
    """
    # Parcours du tableau
    for i in range(len(tab)):
        if tab[i] == elt:
            return i  # Retourne l'indice si trouvé
    return None  # Retourne None si non trouvé

Exercice 2: ★ ★ ★ ★ ★

On considère la fonction insere ci-dessous qui prend en argument un tableau tab d’entiers triés par ordre croissant et un entier a. Cette fonction crée et renvoie un nouveau tableau tab d’entiers triés par ordre croissant.

Compléter la fonction insere ci-dessus.

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

Exemples :

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
    i = 0
    while i < len(tab) and a > tab[i]:
        tab_a[i] = tab[i]  # Décale les éléments
        i += 1
    tab_a[i] = a  # Insère a à sa place
    return tab_a

Exercice 1: ★ ★ ★ ★ ★

Dans cet exercice, les tableaux sont représentés par des listes Python (type list).

Écrire en Python deux fonctions :

• lancer de paramètre n, un entier positif, qui renvoie un tableau de n entiers obtenus aléatoirement entre 1 et 6 (1 et 6 inclus) ;
• paire_6 de paramètre tab, un tableau de n entiers compris entre 1 et 6 et qui renvoie un booléen égal à True si le nombre de 6 est supérieur ou égal à 2, False sinon.

On pourra utiliser la fonction randint(a,b) du module random.

Exemples :

import random

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

def paire_6(tab):
    """Renvoie True si le nombre de 6 est supérieur ou égal à 2, False sinon."""
    return tab.count(6) >= 2

Exercice 2: ★ ★ ★ ★ ★

On considère une image en 256 niveaux de gris que l’on représente par une grille de nombres, c’est-à-dire une liste composée de sous-listes toutes de longueurs identiques.

Compléter le programme ci-dessous :

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

Exemples :

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]) if image else 0

def negatif(image):
    '''renvoie le negatif de l'image sous la forme d'une liste de listes'''
    nouvelle_image = [[0 for _ in range(nombre_colonnes(image))]
                      for _ 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'''
    nouvelle_image = [[0] * nombre_colonnes(image) for _ 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] = 255
    return nouvelle_image

Exercice 1: ★ ★ ★ ★ ★

Programmer la fonction multiplication qui prend en paramètres deux nombres entiers relatifs n1 et n2, et qui renvoie le produit de ces deux nombres.

Les seules opérations arithmétiques autorisées sont l’addition et la soustraction.

Exemples :

def multiplication(n1, n2):
    """
    Calcule le produit de deux entiers
    Args:
        n1 (int): premier entier
        n2 (int): second entier
    Returns:
        int: produit de n1 et n2
    """
    # Cas de base pour la multiplication par 0
    if n2 == 0:
        return 0
    # Cas de base pour la multiplication par 1
    if n2 == 1:
        return n1
    # Si n2 est négatif, on inverse les signes
    if n2 < 0:
        return -multiplication(n1, -n2)
    # Addition répétée
    return n1 + multiplication(n1, n2 - 1)

Exercice 2: ★ ★ ★ ★ ★

Soit tab un tableau non vide d’entiers triés dans l’ordre croissant et n un entier.

La fonction chercher ci-dessous doit renvoyer un indice où la valeur n apparaît dans tab si cette valeur y figure et None sinon.

Recopier et compléter le code de la fonction chercher suivante :

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

Exemples :

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  # Calcul de l'indice médian
    if tab[m] < x:
        return chercher(tab, x, m + 1, j)  # Recherche dans la moitié droite
    elif tab[m] > x:
        return chercher(tab, x, i, m - 1)  # Recherche dans la moitié gauche
    else:
        return m  # Retourne l'indice trouvé

Exercice 1: ★ ★ ★ ★ ★

Écrire une fonction moyenne(notes) qui renvoie la moyenne pondérée des résultats contenus dans le tableau notes, non vide, donné en paramètre. Ce tableau contient des couples (note, coefficient) dans lesquels :

• note est un nombre de type flottant (float) compris entre 0 et 20 ;
• coefficient est un nombre entier strictement positif.

Ainsi l’expression moyenne([(15.0, 2), (9.0, 1), (12.0, 3)]) devra renvoyer 12.5 comme résultat du calcul suivant :

\(\frac{(2 \times 15 + 1 \times 9 + 3 \times 12)}{(2 + 1 + 3)} = 12.5\)

def moyenne(notes):
    """
    Calcule la moyenne pondérée des notes
    Args:
        notes (list): liste de tuples (note, coefficient)
    Returns:
        float: la moyenne pondérée
    """
    # Initialisation des sommes
    total_notes = 0
    total_coefficients = 0
    # Calcul des sommes
    for note, coeff in notes:
        total_notes += note * coeff
        total_coefficients += coeff
    # Retour de la moyenne pondérée
    return total_notes / total_coefficients

Exercice 2: ★ ★ ★ ★ ★

On cherche à déterminer les valeurs du triangle de Pascal. Dans le triangle de Pascal, chaque ligne commence et se termine par le nombre 1.

Dans le triangle de Pascal, chaque ligne commence et se termine par le nombre 1. Comme l’illustre la Figure 2, on additionne deux valeurs successives d’une ligne pour obtenir la valeur qui se situe sous la deuxième valeur.

Compléter les fonctions ligne_suivante et pascal ci-dessous.

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

Exemples :

def ligne_suivante(ligne):
    '''Renvoie la ligne suivant ligne du triangle de Pascal'''
    ligne_suiv = [1]  # Commence par 1
    for i in range(len(ligne) - 1):
        ligne_suiv.append(ligne[i] + ligne[i + 1])  # Somme des deux éléments
    ligne_suiv.append(1)  # Termine par 1
    return ligne_suiv

def pascal(n):
    '''Renvoie le triangle de Pascal de hauteur n'''
    triangle = [[1]]
    for k in range(1, n + 1):
        ligne_k = ligne_suivante(triangle[k - 1])  # Génère la ligne suivante
        triangle.append(ligne_k)
    return triangle

Exercice 1: ★ ★ ★ ★ ★

Un arbre binaire est soit vide, représenté en Python par la valeur None, soit un noeud, contenant une étiquette et deux sous-arbres gauche et droit et représenté par une instance de la classe Noeud donnée ci-dessous.

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

L’arbre ci-dessus sera donc implémenté de la manière suivante :

a = Noeud(1, Noeud(4, None, None),
             Noeud(0, None,
                    Noeud(7, None, None)))

Écrire une fonction récursive taille prenant en paramètre un arbre a et qui renvoie la taille de l’arbre que cette instance implémente.

Écrire de même une fonction récursive hauteur prenant en paramètre un arbre a et qui renvoie la hauteur de l’arbre que cette instance implémente.

On considère que la hauteur d’un arbre vide est -1 et la taille d’un arbre vide est 0.

Exemples :

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

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

Exercice 2: ★ ★ ★ ★ ★

On rappelle que les tableaux sont représentés par des listes en Python du type list.

Le but de cet exercice est d’écrire une fonction ajoute qui prend en paramètres trois arguments indice, element et tab et renvoie un tableau tab_ins dans lequel les éléments sont ceux du tableau tab avec, en plus, l’élément element à l’indice indice.

Exemples :

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, nbre_elts):
        tab_ins[i + 1] = tab[i]
    return tab_ins

Exercice 1: ★ ★ ★ ★ ★

Écrire une fonction moyenne qui prend en paramètre un tableau d’entiers non vide et qui renvoie un nombre flottant donnant la moyenne de ces entiers.

Attention : il est interdit d’utiliser la fonction sum ou la fonction mean (module statistics) de Python.

Exemples :

def moyenne(tab):
    """
    Calcule la moyenne d'un tableau d'entiers
    Args:
        tab (list): tableau d'entiers
    Returns:
        float: moyenne des entiers
    """
    # Initialisation des variables
    total = 0
    # Calcul de la somme des éléments
    for nombre in tab:
        total += nombre
    # Retourne la moyenne
    return total / len(tab)

Exercice 2: ★ ★ ★ ★ ★

Le but de l’exercice est de compléter une fonction qui détermine si une valeur est présente dans un tableau de valeurs triées dans l’ordre croissant.

Compléter l’algorithme de dichotomie donné ci-après.

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

Exemples :

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  # Initialisation de fin
    while debut <= fin:
        m = (debut + fin) // 2  # Calcul de l'indice du milieu
        if x == tab[m]:
            return True  # x trouvé
        if x > tab[m]:
            debut = m + 1  # Recherche dans la partie droite
        else:
            fin = m - 1  # Recherche dans la partie gauche
    return False  # x non trouvé

Exercice 1: ★ ★ ★ ★ ★

Écrire une fonction recherche_min qui prend en paramètre un tableau de nombres tab non vide, et qui renvoie l’indice de la première occurrence du minimum de ce tableau. Les tableaux seront représentés sous forme de liste Python.

Exemples :

def recherche_min(tab):
    """
    Renvoie l'indice de la première occurrence du minimum
    Args:
        tab (list): tableau de nombres
    Returns:
        int: indice de la première occurrence du minimum
    """
    min_val = tab[0]  # Initialiser avec le premier élément
    index = 0  # Son indice est donc 0
    
    # Parcours du tableau
    for i in range(1, len(tab)):
        if tab[i] < min_val:  # Si on trouve un minimum
            min_val = tab[i]
            index = i  # Mettre à jour l'indice
    
    return index

Exercice 2: ★ ★ ★ ★ ★

On considère la fonction separe ci-dessous qui prend en argument un tableau tab dont les éléments sont des 0 et des 1 et qui sépare les 0 des 1 en plaçant les 0 en début de tableau et les 1 à la suite.

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

Exemples :

def separe(tab):
    '''Separe les 0 et les 1 dans le tableau tab'''
    gauche = 0
    droite = len(tab) - 1  # Initialiser droite à la fin du tableau
    while gauche < droite:
        if tab[gauche] == 0:
            gauche += 1  # Déplacer à droite si c'est un 0
        else:
            tab[gauche], tab[droite] = tab[droite], tab[gauche]  # Échanger les valeurs
            droite -= 1  # Déplacer gauche et droite
    return tab

Exercice 1: ★ ★ ★ ★ ★

Écrire une fonction min_et_max qui prend en paramètre un tableau de nombres tab non vide, et qui renvoie la plus petite et la plus grande valeur du tableau sous la forme d’un dictionnaire à deux clés min et max.

Les tableaux seront représentés sous forme de liste Python. L’utilisation des fonctions natives min, max et sorted, ainsi que la méthode sort n’est pas autorisée.

Exemples :

def min_et_max(tab):
    """
    Renvoie un dictionnaire avec les valeurs min et max
    Args:
        tab (list): tableau non vide de nombres
    Returns:
        dict: {'min': valeur_min, 'max': valeur_max}
    """
    # Initialisation avec le premier élément
    min_val = tab[0]
    max_val = tab[0]
    
    # Parcours du tableau
    for num in tab:
        # Mise à jour de min_val et max_val
        if num < min_val:
            min_val = num
        if num > max_val:
            max_val = num
    
    return {'min': min_val, 'max': max_val}

Exercice 2: ★ ★ ★ ★ ★

On dispose d’une classe Carte permettant de créer des objets modélisant des cartes à jouer.

Compléter la classe Paquet_de_cartes suivante en respectant les spécifications données dans les chaînes de documentation. Ajouter une assertion dans la méthode recuperer_carte de la classe Paquet_de_cartes afin de vérifier que le paramètre pos est correct.

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 coeur, carreau et trèfle. """
        ...
        ...
            ...
                ...
                
    def recuperer_carte(self, pos):
        """ Renvoie la carte qui se trouve à la position pos
        (entier compris entre 0 et 51). """
        ...
        ...

Exemple :

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 coeur, carreau et trèfle. """
        self.contenu = [Carte(couleur, valeur) 
                        for couleur in range(1, 5) 
                        for valeur in range(1, 14)]

    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]

Exercice 1: ★ ★ ★ ★ ★

Écrire une fonction indices_maxi qui prend en paramètre un tableau non vide de nombres entiers tab, représenté par une liste Python et qui renvoie un tuple (maxi, indices) où :

• maxi est le plus grand élément du tableau tab ;
• indices est une liste Python contenant les indices du tableau tab où apparaît ce plus grand élément.

Exemple :

def indices_maxi(tab):
    """
    Trouve le maximum et ses indices dans un tableau
    Args:
        tab (list): tableau non vide d'entiers
    Returns:
        tuple: (maxi, indices)
    """
    maxi = tab[0]
    indices = []
    
    # Parcours du tableau pour trouver le maximum et ses indices
    for i in range(len(tab)):
        if tab[i] > maxi:
            maxi = tab[i]
            indices = [i]
        elif tab[i] == maxi:
            indices.append(i)
    
    return (maxi, indices)

Exercice 2: ★ ★ ★ ★ ★

Cet exercice utilise des piles qui seront représentées par des listes Python.

On cherche à écrire une fonction positifs qui prend une pile de nombres entiers en paramètre et qui renvoie une nouvelle pile contenant les entiers positifs de la pile initiale, dans le même ordre, quitte à modifier la pile initiale.

Pour cela, on va également écrire une fonction renverse qui prend une pile en paramètre et qui renvoie une nouvelle pile contenant les mêmes éléments que la pile initiale, mais dans l’ordre inverse. Cette fonction sera également amenée à modifier la pile passée en paramètre.

Compléter le code Python des fonctions renverse et positifs ci-après.

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

Exemples :

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 pile_positifs

Exercice 1: ★ ★ ★ ★ ★

Écrire une fonction recherche qui prend en paramètres elt un nombre entier et tab un tableau de nombres entiers (type list), et qui renvoie l’indice de la dernière occurrence de elt dans tab si elt est dans tab et None sinon.

Exemples :

def recherche(elt, tab):
    """
    Recherche l'indice de la dernière occurrence de elt dans tab
    Args:
        elt (int): l'élément à rechercher
        tab (list): tableau d'entiers
    Returns:
        int or None: indice de la dernière occurrence ou None
    """
    # Parcours du tableau à l'envers
    for i in range(len(tab) - 1, -1, -1):
        if tab[i] == elt:
            return i
    return None

Exercice 2: ★ ★ ★ ★ ★

On définit une classe gérant une adresse IPv4.

On rappelle qu’une adresse IPv4 est une adresse de longueur 4 octets, notée en décimale à point, en séparant chacun des octets par un point. On considère un réseau privé avec une plage d’adresses IP de 192.168.0.0 à 192.168.0.255.

Les adresses IP 192.168.0.0 et 192.168.0.255 sont des adresses réservées.

Compléter le code ci-dessous pour la classe AdresseIP :

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"""
        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.' + ...)

Instancier trois objets : adresse1, adresse2, adresse3 avec les arguments suivants : '192.168.0.1', '192.168.0.2', '192.168.0.0'

Vérifier que :

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] == 254:
            return None
        octet_nouveau = octets[3] + 1
        return AdresseIP('192.168.0.' + str(octet_nouveau))

Exercice 1: ★ ★ ★ ★ ★

On veut trier par ordre croissant les notes d’une évaluation qui sont des nombres entiers compris entre 0 et 10 (inclus). Ces notes sont contenues dans un tableau notes_eval (type list).

Écrire une fonction effectif_notes prenant en paramètre le tableau notes_eval et renvoyant un tableau de longueur 11 tel que la valeur d’indice i soit le nombre de notes valant i dans le tableau notes_eval.

Écrire ensuite une fonction notes_triees prenant en paramètre le tableau des effectifs des notes et renvoyant un tableau contenant les mêmes valeurs que notes_eval mais triées dans l’ordre croissant.

Exemple :

def effectif_notes(notes_eval):
    """Renvoie un tableau des effectifs des notes."""
    effectifs = [0] * 11  # Tableau de longueur 11 initialisé à 0
    for note in notes_eval:
        effectifs[note] += 1
    return effectifs

def notes_triees(effectifs):
    """Renvoie un tableau des notes triées à partir des effectifs."""
    notes_triees = []
    for i in range(len(effectifs)):
        notes_triees.extend([i] * effectifs[i])  # Ajoute i effectifs[i] fois
    return notes_triees

Exercice 2: ★ ★ ★ ★ ★

L’objectif de cet exercice est d’écrire deux fonctions récursives dec_to_bin et bin_to_dec assurant respectivement la conversion de l’écriture décimale d’un nombre entier vers son écriture en binaire et, réciproquement, la conversion de l’écriture en binaire d’un nombre vers son écriture décimale.

Compléter, puis tester, le code des deux fonctions suivantes :

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

Exemple :

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:
        bit_droit = 0 if nb_bin[-1] == '0' else 1
    return bit_droit + 2 * bin_to_dec(nb_bin[:-1])

Exercice 1: ★ ★ ★ ★ ★

Écrire une fonction enumere qui prend en paramètre un tableau tab (type list) et renvoie un dictionnaire d dont les clés sont les éléments de tab avec pour valeur associée la liste des indices de l’élément dans le tableau tab.

Exemple :

def enumere(tab):
    """
    Renvoie un dictionnaire d'indices pour les éléments de tab
    Args:
        tab (list): tableau d'éléments
    Returns:
        dict: dictionnaire des éléments et leurs indices
    """
    d = {}
    for index, element in enumerate(tab):
        if element not in d:
            d[element] = []
        d[element].append(index)
    return d

Exercice 2: ★ ★ ★ ★ ★

Un arbre binaire est soit vide, représenté en Python par la valeur None, soit un noeud, contenant une étiquette et deux sous-arbres gauche et droit représentés par une instance de la classe Noeud donnée ci-dessous.

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

La fonction récursive parcours renvoie la liste des étiquettes des noeuds de l’arbre implémenté par l’instance arbre dans l’ordre du parcours en profondeur infixe à partir d’une liste vide passée en argument.

Compléter le code de la fonction insere, qui prend en argument un arbre binaire de recherche arbre et une étiquette cle, non présente dans l’arbre, et qui :

•                 1️⃣ renvoie une nouvelle feuille d’étiquette cle s’il est vide ;
•                 2️⃣ renvoie l’arbre après l’avoir modifié en insérant cle sinon ;
•                 3️⃣ garantit que l’arbre ainsi complété soit encore un arbre binaire de recherche.

Tester ensuite ce code en utilisant la fonction parcours et en insérant successivement des noeuds d’étiquette 1, 4, 6 et 8 dans l’arbre binaire de recherche représenté ci-dessous :

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

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 cle < arbre.etiquette:
            arbre.gauche = insere(arbre.gauche, cle)
        else:
            arbre.droit = insere(arbre.droit, cle)
    return arbre

Exercice 1: ★ ★ ★ ★ ★

On a relevé les valeurs moyennes annuelles des températures à Paris pour la période allant de 2013 à 2019. Les résultats ont été récupérés sous la forme de deux tableaux (de type list) :

Écrire la fonction annee_temperature_minimale qui prend en paramètres ces deux tableaux et qui renvoie la plus petite valeur relevée au cours de la période et l’année correspondante.

On suppose que la température minimale est atteinte une seule fois.

Exemple :

def annee_temperature_minimale(t_moy, annees):
    """
    Renvoie la température minimale et l'année correspondante
    Args:
        t_moy (list): liste des températures
        annees (list): liste des années
    Returns:
        tuple: (temperature_minimale, annee)
    """
    # Recherche de la température minimale et de son indice
    indice_min = t_moy.index(min(t_moy))
    temperature_min = t_moy[indice_min]
    annee = annees[indice_min]
    return temperature_min, annee

Exercice 2: ★ ★ ★ ★ ★

Un mot palindrome peut se lire de la même façon de gauche à droite ou de droite à gauche : kayak, radar, et non sont des mots palindromes.

L’objectif de cet exercice est d’obtenir un programme Python permettant de tester si un nombre est un nombre palindrome.

Pour remplir cette tâche, on vous demande de compléter le code des trois fonctions ci-dessous qui s’appuient les unes sur les autres :

•             1️⃣ inverse_chaine : qui renvoie une chaîne de caractères inversée ;
•             2️⃣ est_palindrome : qui teste si une chaîne de caractères est un palindrome ;
•             3️⃣ est_nbre_palindrome : qui teste si un nombre est un palindrome.

Compléter le code des trois fonctions ci-dessous :

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)

Exemples :

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 inverse == chaine

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