duranton.net

Exercices d'algorithmiques.

Avant-propos :

Ici se trouve une série d'exercices d'algorithmique.

Ils sont constitués d'exercices de l'épreuve pratique du baccalauréat de fin de terminale.

Ils sont globalement classés par difficulté.

1. Exercice : (sujet 34 - 2023)

Programmer la fonction moyenne prenant en paramètre un tableau d'entiers tab (de type list) qui renvoie la moyenne de ses éléments si le tableau est non vide. Proposer une façon de traiter le cas où le tableau passé en paramètre est vide.

Dans cet exercice, on s’interdira d’utiliser la fonction Python sum.

Exemples :

>>> moyenne([5, 3, 8])
5.333333333333333
>>> moyenne([1, 2, 3, 4, 5, 6, 7, 8, 9, 10])
5.5
>>> moyenne([])
# Comportement différent suivant le traitement proposé.

2. Exercice : (sujet 10 - 2023)

Écrire la fonction maxliste, 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 : 

>>> maxliste([98, 12, 104, 23, 131, 9])
131
>>> maxliste([-27, 24, -3, 15])
24

3. Exercice : (sujet 31 - 2023)

Écrire une fonction python appelée nb_repetitions qui prend en paramètres un élément elt et une liste tab et renvoie le nombre de fois où l’élément apparaît dans la liste.

Exemples :

>>> nb_repetitions(5, [2, 5, 3, 5, 6, 9, 5])
3
>>> nb_repetitions('A', [ 'B', 'A', 'B', 'A', 'R'])
2
>>> nb_repetitions(12, [1, '! ', 7, 21, 36, 44])
0

4. Exercice : (sujet 1 - 2023)

Programmer la fonction verifie qui prend en paramètre un tableau de valeurs numériques non vide et qui renvoie True si ce tableau est trié dans l’ordre croissant, False sinon.

Exemples : 

>>> verifie([0, 5, 8, 8, 9])
True
>>> verifie([8, 12, 4])
False
>>> verifie([-1, 4])
True
>>> verifie([5])
True

5. Exercice : (sujet 23 - 2023)

On considère des tables (des tableaux de dictionnaires) qui contiennent des enregistrements relatifs à des animaux hébergés dans un refuge. Les attributs des enregistrements sont 'nom', 'espece', 'age', 'enclos'. Voici un exemple d'une telle table :

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

Programmer une fonction selection_enclos qui :

Exemples avec la table animaux ci-dessus :

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

6. Exercice : (sujet 44 - 2023)

Programmer une fonction renverse, prenant en paramètre une chaîne de caractères non vide, mot, et qui renvoie une chaîne de caractères en inversant ceux de la chaîne mot.

Exemple :

>>> renverse("informatique")
"euqitamrofni"

7. Exercice : (sujet 6 - 2023)

Programmer la fonction recherche, prenant en paramètre un tableau non vide tab (de type list) d'entiers et un entier n, et qui renvoie l'indice de la dernière occurrence de l'élément cherché. Si l'élément n'est pas présent, la fonction renvoie la longueur du tableau.

Exemples :

>>> recherche([5, 3], 1)
2
>>> recherche([2, 4], 2)
0
>>> recherche([2, 3, 5, 2, 4], 2)
3

8. Exercice : (sujet 38 - 2023)

On considère des mots à trous : ce sont des chaînes de caractères contenant uniquement des majuscules et des caractères '*'. Par exemple 'INFO*MA*IQUE', '***I***E**' et '*S*' sont des mots à trous.

Programmer une fonction correspond qui :

Exemples :

>>> correspond('INFORMATIQUE', 'INFO*MA*IQUE')
True
>>> correspond('AUTOMATIQUE', 'INFO*MA*IQUE')
False
>>> correspond('STOP', 'S*')
False
>>> correspond('AUTO', '*UT*')
True

9. Exercice : (sujet 25 - 2023)

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

Exemple :

>>> enumere([1, 1, 2, 3, 2, 1])
{1: [0, 1, 5], 2: [2, 4], 3: [3]}

10. Exercice : (sujet 13 - 2023)

Programmer la fonction recherche, prenant comme paramètres une variable a de type numérique (float ou int) et un tableau tab (de type list) et qui renvoie le nombre d'occurrences de a dans tab.

Exemples :

>>> recherche(5, [])
0
>>> recherche(5, [-2, 3, 4, 8])
0
>>> recherche(5, [-2, 3, 1, 5, 3, 7, 4])
1
>>> recherche(5, [-2, 5, 3, 5, 4, 5])
3

11. Exercice : (sujet 41 - 2023)

Écrire une fonction recherche(caractere, chaine) qui prend en paramètres caractere, un unique caractère (c’est-à-dire une chaîne de caractère de longueur 1), et chaine, une chaîne de caractères. Cette fonction renvoie le nombre d’occurrences de caractere dans chaine, c’est-à-dire le nombre de fois où caractere apparaît dans chaine.

Exemples :

>>> recherche('e', "sciences")
2
>>> recherche('i', "mississippi")
4
>>> recherche('a', "mississippi")
0

12. Exercice : (sujet 27 - 2023)

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

Exemples :

>>> recherche_min([5])
0
>>> recherche_min([2, 4, 1])
2
>>> recherche_min([5, 3, 2, 2, 4])
2

13. Exercice : (sujet 2 - 2023)

Écrire une fonction indices_maxi qui prend en paramètre une liste tab, non vide, de nombres entiers et renvoie un couple donnant d’une part le plus grand élément de cette liste et d’autre part la liste des indices de la liste tab où apparaît ce plus grand élément.

Exemples :

>>> indices_maxi([1, 5, 6, 9, 1, 2, 3, 7, 9, 8])
(9, [3, 8])
>>> indices_maxi([7])
(7,[0])

14. Exercice : (sujet 35 - 2023)

L'opérateur « ou exclusif » entre deux bits renvoie 0 si les deux bits sont égaux et 1 s'ils sont différents. Il est symbolisé par le caractère \( \oplus \).

Ainsi :

On représente ici une suite de bits par un tableau contenant des 0 et des 1.

Exemples :

a = [1, 0, 1, 0, 1, 1, 0, 1]
b = [0, 1, 1, 1, 0, 1, 0, 0]
c = [1, 1, 0, 1]
d = [0, 0, 1, 1]

Écrire la fonction ou_exclusif qui prend en paramètres deux tableaux de même longueur et qui renvoie un tableau où l’élément situé à position i est le résultat, par l’opérateur « ou exclusif », des éléments à la position i des tableaux passés en paramètres.

En considérant les quatre exemples ci-dessus, cette fonction donne :

>>> ou_exclusif(a, b)
[1, 1, 0, 1, 1, 0, 0, 1]
>>> ou_exclusif(c, d)
[1, 1, 1, 0]

15. Exercice : (sujet 27 - 2023)

On considère la fonction separe 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):

    gauche = 0
    droite = ...
    while gauche < droite :
        if tab[gauche] == 0 :
            gauche = ...
        else :
            tab[gauche], tab[droite] = ...
            droite = ...
    return tab

Exemples :

>>> separe([1, 0, 1, 0, 1, 0, 1, 0])
[0, 0, 0, 0, 1, 1, 1, 1]
>>> 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]

Description d’étapes effectuées par la fonction separe sur le tableau ci-dessous :

tab = [1, 0, 1, 0, 1, 0, 1, 0]

16. Exercice : (sujet 15 - 2023)

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 listes : l’une pour les températures, l’autre pour les années :

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

Écrire la fonction mini qui prend en paramètres un tableau releve des relevés et un tableau date des dates 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 :

>>> mini(t_moy, annees)
(12.5, 2016)

17. Exercice : (sujet 15 - 2023)

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

De même certains nombres sont eux aussi des palindromes : 33, 121, 345543.

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 sachant que la fonction est_nbre_palindrome s’appuiera sur la fonction est_palindrome qui elle-même s’appuiera sur la fonction inverse_chaine.

La fonction inverse_chaine inverse l'ordre des caractères d'une chaîne de caractères chaine et renvoie la chaîne inversée.

La fonction est_palindrome teste si une chaine de caractères chaine est un palindrome. Elle renvoie True si c’est le cas et False sinon. Cette fonction s’appuie sur la fonction précédente.

La fonction est_nbre_palindrome teste si un nombre nbre est un palindrome. Elle renvoie True si c’est le cas et False sinon. Cette fonction s’appuie sur la fonction précédente.

Compléter les trois fonctions ci-dessous :

def inverse_chaine(chaine):
    result = ...
    for caractere in chaine:
       result = ...
    return result

def est_palindrome(chaine):
    inverse = inverse_chaine(chaine)
    return ...
    
def est_nbre_palindrome(nbre):
    chaine = ...
    return est_palindrome(chaine)

Exemples:

>>> inverse_chaine('bac')
'cab'
>>> est_palindrome('NSI')
False
>>> est_palindrome('ISN-NSI')
True
>>> est_nbre_palindrome(214312)
False
>>> est_nbre_palindrome(213312)
True

18. Exercice : (sujet 22 - 2023)

On rappelle que :

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 \( a^0 \) , strictement inférieures à borne.

Exemples :

>>> liste_puissances(3, 5)
[3, 9, 27, 81, 243]
>>> liste_puissances(-2, 4)
[-2, 4, -8, 16]
>>> liste_puissances_borne(2, 16)
[2, 4, 8]
>>> liste_puissances_borne(2, 17)
[2, 4, 8, 16]
>>> liste_puissances_borne(5, 5)
[]

19. Exercice : (sujet 24 - 2023)

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 :

On cherche le nombre d’occurrences des caractères dans une chaîne de caractères. On souhaite stocker ces nombres d’occurrences dans un dictionnaire dont les clefs seraient les caractères de la chaîne et les valeurs le nombre d’occurrences de ces caractères.

Par exemple : avec la phrase 'Hello world !' le dictionnaire est le suivant :

{'H': 1, 'e': 1, 'l': 3, 'o': 2, ' ': 2, 'w': 1, 'r': 1, 'd': 1, '!': 1}

L’ordre des clefs n’a pas d’importance.

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

20. Exercice : (sujet 16 - 2023)

Écrire une fonction recherche_indices_classement qui prend en paramètres un entier elt et une liste d’entiers tab, et qui renvoie trois listes :

Exemples :

>>> recherche_indices_classement(3, [1, 3, 4, 2, 4, 6, 3, 0])
([0, 3, 7], [1, 6], [2, 4, 5])
>>> recherche_indices_classement(3, [1, 4, 2, 4, 6, 0])
([0, 2, 5], [], [1, 3, 4])
>>> recherche_indices_classement(3, [1, 1, 1, 1])
([0, 1, 2, 3], [], [])
>>> recherche_indices_classement(3, [])
([], [], [])

21. Exercice : (sujet 29 - 2023)

La méthode insert de la classe list permet d’insérer un élément dans une liste à un indice donné.

Le but de cet exercice est, sans utiliser cette méthode, d’écrire une fonction ajoute réalisant cette insertion en produisant une nouvelle liste.

Cette fonction ajoute prend en paramètres trois variables indice, element et liste et renvoie une liste L dans laquelle les éléments sont ceux de la liste liste avec, en plus, l’élément element à l’indice indice.

On considère que les variables indice et element sont des entiers positifs et que les éléments de liste sont également des entiers positifs.

Les éléments de la liste liste, dont les indices sont supérieurs ou égaux à indice apparaissent décalés vers la droite dans la liste L.

Si indice est supérieur ou égal au nombre d’éléments de la liste liste, l’élément element est ajouté dans L après tous les éléments de la liste liste.

Exemple : 

>>> ajoute(1, 4, [7, 8, 9])
[7, 4, 8, 9]
>>> ajoute(3, 4, [7, 8, 9])
[7, 8, 9, 4]
>>> ajoute(4, 4, [7, 8, 9])
[7, 8, 9, 4]

Compléter le code ci-dessous : 

def ajoute(indice, element, liste):
    nbre_elts = len(liste)
    L = [0 for i in range(nbre_elts + 1)]
    if ...:
        for i in range(indice):
            L[i] = ...
        L[...] = ...
        for i in range(indice + 1, nbre_elts + 1):
            L[i] = ...
    else:
        for i in range(nbre_elts):
            L[i] = ...
        L[...] = ...
    return L

22. Exercice : (sujet 21 - 2023)

Le codage par différence (delta encoding en anglais) permet de compresser un tableau de données en indiquant pour chaque donnée, sa différence avec la précédente (plutôt que la donnée elle-même). On se retrouve alors avec un tableau de données plus petit, nécessitant donc moins de place en mémoire. Cette méthode se révèle efficace lorsque les valeurs consécutives sont proches.

Programmer la fonction delta(liste) qui prend en paramètre un tableau non vide de nombres entiers et qui renvoie un tableau contenant les valeurs entières compressées à l’aide de cette technique.

Exemples :

>>> delta([1000, 800, 802, 1000, 1003])
[1000, -200, 2, 198, 3]
>>> delta([42])
[42]

23. Exercice : (sujet 30 - 2023)

On considère la fonction binaire ci-dessous qui prend en paramètre un entier positif a en écriture décimale. Cette fonction renvoie l’écriture binaire de a sous la forme d'une chaîne de caractères.

L’algorithme utilise la méthode des divisions euclidiennes successives comme l’illustre l’exemple ci-après.

Compléter le code de la fonction binaire :

def binaire(a):
    bin_a = ...
    a = a // 2
    while a ... :
        bin_a = ... + bin_a
        a = ...
    return bin_a

Exemples : 

>>> binaire(83)
'1010011'
>>> binaire(127)
'1111111'
>>> binaire(0)
'0'

24. Exercice : (sujet 40 - 2023)

Pour cet exercice :

Voici deux exemples :

Après avoir remarqué le lien entre le nombre de mots et le nombres de caractères espace dans une phrase, programmer une fonction nombre_de_mots qui prend en paramètre une phrase et renvoie le nombre de mots présents dans celle-ci.

Exemples :

>>> nombre_de_mots('Cet exercice est simple.')
4
>>> nombre_de_mots('Le point d exclamation est separe !')
6
>>> nombre_de_mots('Combien de mots y a t il dans cette phrase ?')
10
>>> nombre_de_mots('Fin.')
1

25. Exercice : (sujet 20 - 2023)

Écrire une fonction ajoute_dictionnaires qui prend en paramètres deux dictionnaires d1 et d2 dont les clés sont des nombres et renvoie le dictionnaire d défini de la façon suivante :

Exemples :

>>> ajoute_dictionnaires({1: 5, 2: 7}, {2: 9, 3: 11})
{1: 5, 2: 16, 3: 11}
>>> ajoute_dictionnaires({}, {2: 9, 3: 11})
{2: 9, 3: 11}
>>> ajoute_dictionnaires({1: 5, 2: 7}, {})
{1: 5, 2: 7}

26. Exercice : (sujet 16 - 2023)

Un professeur de NSI décide de gérer les résultats de sa classe sous la forme d’un dictionnaire :

Avec :

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

L’élève dont le nom est Durand a ainsi obtenu au DS2 la note de 8 avec un coefficient 4.

Le professeur crée une fonction moyenne qui prend en paramètre le nom d’un de ses élèves et renvoie sa moyenne arrondie au dixième.

Compléter le code ci-dessous : 

def moyenne(nom, dico_result):
    if nom in ...:
        notes = dico_result[nom]
        total_points = ...
        total_coefficients = ...
        for ...  in notes.values():
            note, coefficient = valeurs
            total_points = total_points + ... * coefficient
            total_coefficients = ... + coefficient
        return round( ... / total_coefficients, 1 )
    else:
        return -1

27. Exercice : (sujet 6 - 2023)

On souhaite programmer une fonction donnant la distance la plus courte entre un point de départ et une liste de points. Les points sont tous à coordonnées entières.

Les points sont donnés sous la forme d'un tuple de deux entiers.

La liste des points à traiter est donc un tableau, non vide, de tuples.

On rappelle que la distance entre deux points du plan de coordonnées \((x ; y)\) et \((x' ; y')\) est donnée par la formule :

$$ d = \sqrt{(x-x')^2 + (y-y')^2} $$

On importe pour cela la fonction racine carrée (sqrt) du module math de Python.

Compléter le code des fonctions distance et plus_courte_distance pour qu'elles répondent à leurs spécifications.

from math import sqrt # import de la fonction racine carrée
def distance(point1, point2):
    """ Calcule et renvoie la distance entre deux points. """
    return sqrt((...)**2 + (...)**2)


def plus_courte_distance(tab, depart):
    """ Renvoie le point du tableau tab se trouvant à la plus
        courte distance du point depart."""
    point = tab[0]
    min_dist = ...
    for i in range (1, ...):
        if distance(tab[i], depart)...:
            point = ...
            min_dist = ...
    return point

Exemples :

>>> distance((1, 0), (5, 3))
5.0
>>> distance((1, 0), (0, 1))
1.4142135623730951
>>> plus_courte_distance([(7, 9), (2, 5), (5, 2)], (0, 0))
(2, 5)
>>> plus_courte_distance([(7, 9), (2, 5), (5, 2)], (5, 2))
(5, 2)

28. Exercice : (sujet 14 - 2023)

On considère la fonction insere ci-dessous qui prend en arguments un entier a et un tableau tab d'entiers triés par ordre croissant. Cette fonction crée et renvoie un nouveau tableau à partir de celui fourni en paramètre en y insérant la valeur a de sorte que le tableau renvoyé soit encore trié par ordre croissant. Les tableaux seront représentés sous la forme de listes Python.

Compléter le code ci-dessous :

def insere(a, tab):
    """ Insère l'élément a (int) dans le tableau tab (list)
        trié par ordre croissant à sa place et renvoie le
        nouveau tableau. """
    l = list(tab) #l contient les memes elements que tab
    l.append(a)
    i = ...
    while a < ... and i >= 0: 
      l[i+1] = ...
      l[i] = a
      i = ...
    return l

Exemples :

>>> insere(3, [1, 2, 4, 5])
[1, 2, 3, 4, 5]
>>> insere(30, [1, 2, 7, 12, 14, 25])
[1, 2, 7, 12, 14, 25, 30]
>>> insere(1, [2, 3, 4])
[1, 2, 3, 4]
>>> insere(1, [])
[1]

29. Exercice : (sujet 3 - 2023)

Dans cet exercice, les nombres sont des entiers ou des flottants.

Écrire une fonction moyenne renvoyant la moyenne pondérée d’une liste non vide, passée en paramètre, de tuples à deux éléments de la forme (valeur,coefficient) où valeur et coefficient sont des nombres positifs ou nuls.

Si la somme des coefficients est nulle, la fonction renvoie None, si la somme des coefficients est non nulle, la fonction renvoie, sous forme de flottant, la moyenne des valeurs affectées de leur coefficient.

Exemples :

>>> moyenne([(8, 2), (12, 0), (13.5, 1), (5, 0.5)])
9.142857142857142
>>> moyenne([(3, 0), (5, 0)])
None

30. Exercice : (sujet 4 - 2023)

Écrire une fonction a_doublon qui prend en paramètre une liste triée de nombres et renvoie True si la liste contient au moins deux nombres identiques, False sinon.

Exemples :

>>> a_doublon([])
False
>>> a_doublon([1])
False
>>> a_doublon([1, 2, 4, 6, 6])
True
>>> a_doublon([2, 5, 7, 7, 7, 9])
True
>>> a_doublon([0, 2, 3])
False

31. Exercice : (sujet 8 - 2023)

Sur le réseau social TipTop, on s’intéresse au nombre de « like » des abonnés. Les données sont stockées dans des dictionnaires où les clés sont les pseudos et les valeurs correspondantes sont les nombres de « like » comme ci-dessous :

{'Bob': 102, 'Ada': 201, 'Alice': 103, 'Tim': 50}

Ecrire une fonction max_dico qui :

Exemples :

>>> max_dico({'Bob': 102, 'Ada': 201, 'Alice': 103, 'Tim': 50})
('Ada', 201)
>>> max_dico({'Alan': 222, 'Ada': 201, 'Eve': 220, 'Tim': 50})
('Alan', 222)

32. Exercice : (sujet 9 - 2023)

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 :

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

33. Exercice : (sujet 11 - 2023)

On modélise la représentation binaire d'un entier non signé par un tableau d'entiers dont les éléments sont 0 ou 1.

Par exemple, le tableau [1, 0, 1, 0, 0, 1, 1] représente l'écriture binaire de l'entier dont l'écriture décimale est :

$$ 2^6 + 2^4 + 2^1+2^0 = 83 $$

A l'aide d'un parcours séquentiel, écrire la fonction convertir répondant aux spécifications suivantes :

def convertir(tab):
    """
    tab est un tableau d'entiers, dont les éléments sont 0 ou 1,
    et représentant un entier écrit en binaire.
    Renvoie l'écriture décimale de l'entier positif dont la
    représentation binaire est donnée par le tableau tab
    """

Exemples :

>>> convertir([1, 0, 1, 0, 0, 1, 1])
83
>>> convertir([1, 0, 0, 0, 0, 0, 1, 0])
130

34. Exercice : (sujet 3 - 2023)

On travaille sur des dessins en noir et blanc obtenus à partir de pixels noirs et blancs :

La figure « cœur » ci-dessus va servir d’exemple.

On la représente par une grille de nombres, c’est-à-dire par une liste composée de sous-listes de mêmes longueurs.

Chaque sous-liste représentera donc une ligne du dessin.

Dans le code ci-dessous, la fonction affiche permet d’afficher le dessin. Les pixels noirs (1 dans la grille) seront représentés par le caractère " *" et les blancs (0 dans la grille) par deux espaces.

La fonction zoomListe prend en argument une liste liste_depart et un entier k. Elle renvoie une liste où chaque élément de liste_depart est dupliqué k fois.

La fonction zoomDessin prend en argument la grille dessin et renvoie une grille où toutes les lignes de dessin sont zoomées k fois (c’est-à-dire, on applique à chaque ligne la fonction zoomListe avec comme second paramètre k) et répétées k fois.

Compléter le code ci-dessous :

coeur = [[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [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],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]

def affiche(dessin):
    ''' affichage d'une grille : les 1 sont représentés par
        des " *" , les 0 par deux espaces " ".
        La valeur "" donnée au paramètre end permet de ne pas avoir
        de saut de ligne.'''
    for ligne in dessin:
        for col in ligne:
            if col == 1:
                print(" *", end= "")
            else:
                print(" ", end= "")
        print()

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




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

Résultats à obtenir :

35. Exercice : (sujet 17 - 2023)

On cherche à déterminer les valeurs du triangle de Pascal (Figure 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 la fonction pascal ci-après prenant en paramètre un entier n supérieur ou égal à 2. Cette fonction doit renvoyer une liste correspondant au triangle de Pascal de la ligne 0 à la ligne n. Le tableau représentant le triangle de Pascal sera contenu dans la variable triangle.

def pascal(n):
    triangle= [[1]]
    for k in range(1,...):
        ligne_k = [...]
        for i in range(1,k):
            ligne_k.append(triangle[...][i-1]+triangle[...][...])
        ligne_k.append(...)
        triangle.append(ligne_k)
    return triangle

Pour n=4, voici ce que l'on devra obtenir :

>>> pascal(4)
[[1], [1, 1], [1, 2, 1], [1, 3, 3, 1], [1, 4, 6, 4, 1]]

Pour n=5, voici ce que l'on devra obtenir :

>> pascal(5)
[[1], [1, 1], [1, 2, 1], [1, 3, 3, 1], [1, 4, 6, 4, 1],[1, 5, 10, 10, 5, 1]]

36. Exercice : (sujet 4 - 2023)

On souhaite générer des grilles du jeu de démineur à partir de la position des bombes à placer.

On se limite à la génération de grilles carrées de taille \(n \times n\) où \(n\) est le nombre de bombes du jeu.

Dans le jeu du démineur, chaque case de la grille contient soit une bombe, soit une valeur qui correspond aux nombres de bombes situées dans le voisinage direct de la case (au-dessus, en dessous, à droite, à gauche ou en diagonal : chaque case a donc 8 voisins si elle n'est pas située au bord de la grille).

Voici un exemple de grille \(5 \times 5 \) de démineur dans laquelle la bombe est représentée par une étoile :

On utilise une liste de listes pour représenter la grille et on choisit de coder une bombe par la valeur -1.

L'exemple ci-dessus sera donc codé par la liste : 

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

Compléter le code suivant afin de générer des grilles de démineur, on pourra vérifier que l’instruction genere_grille([(1, 1), (2, 4), (3, 1), (3, 3), (4, 4)]) produit bien la liste donnée en exemple.

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

37. Exercice : (sujet 39 - 2023)

On considère la fonction pantheon prenant en paramètres eleves et notes deux tableaux 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. Ainsi, l’instruction pantheon(['a', 'b', 'c', 'd'], [15,18,12,18]) renvoie le couple (18, ['b', 'd']).

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

eleves_nsi = ['a','b','c','d','e','f','g','h','i','j']
notes_nsi = [30, 40, 80, 60, 58, 80, 75, 80, 60, 24]

Compléter ce code.

Exemples :

>>> eleves_nsi = ['a','b','c','d','e','f','g','h','i','j']
>>> notes_nsi = [30, 40, 80, 60, 58, 80, 75, 80, 60, 24]
>>> pantheon(eleves_nsi, notes_nsi)
(80, ['c', 'f', 'h'])
>>> pantheon([],[])
(0, [])

38. Exercice : (sujet 18 - 2023)

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 :

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

Il y a donc 4 points de rupture.

Compléter les fonctions Python est_un_ordre et nombre_points_rupture proposées à la page suivante pour que :

def est_un_ordre(tab):
    '''
    Renvoie True si tab est de longueur n et contient tous les entiers
    de 1 à n, False sinon
    '''
    for i in range(1,...):
        if ...:
            return False
    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
    '''
    assert ... # ordre n'est pas un ordre de gènes
    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[...] != n: # le dernier n'est pas n
        nb = nb + 1
    return nb

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

39. Exercice : (sujet 19 - 2023)

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 (espace ou caractères de ponctuation : ‘!’,’ ?’...) ne sont pas codés.

La fonction position_alphabet ci-dessous prend en paramètre un caractère lettre et renvoie la position de lettre dans la chaîne de caractères ALPHABET s’il s’y trouve.

La fonction cesar prend en paramètre une chaîne de caractères message et un nombre entier decalage et renvoie le nouveau message codé avec le codage de César utilisant le décalage decalage.

Compléter la fonction cesar :

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

Exemples :

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

40. Exercice : (sujet 5 - 2023)

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.

La largeur de l’image est donc la longueur d’une sous-liste et la hauteur de l’image est le nombre de sous-listes.

Chaque sous-liste représente une ligne de l’image et chaque élément des sous-listes est un entier compris entre 0 et 255, représentant l’intensité lumineuse du pixel.

L négatif d’une image est l’image constituée des pixels x_n tels que x_n + x_i = 255 où x_i est le pixel correspondant de l’image initiale.

Compléter le programme proposé page suivante :

def nbLig(image):
    '''renvoie le nombre de lignes de l'image'''
    return ...

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

def negatif(image):
    '''renvoie le négatif de l'image sous la forme
        d'une liste de listes'''
    # on créé une image de 0 aux mêmes dimensions que le paramètre image
    L = [[0 for k in range(nbCol(image))] for i in range(nbLig(image))]
    for i in range(nbLig(image)):
        for j in range(...):
            L[i][j] = ...
    return L
    
def binaire(image, seuil):
    '''renvoie une image binarisée de l'image sous la forme
        d'une liste de listes contenant des 0 si la valeur
        du pixel est strictement inférieure au seuil
        et 1 sinon'''
    # on crée une image de 0 aux mêmes dimensions que le paramètre
    image
    L = [[0 for k in range(nbCol(image))] for i in range(nbLig(image))]
    for i in range(nbLig(image)):
        for j in range(...):
            if image[i][j] < ... :
                L[i][j] = ...
            else:
                L[i][j] = ...
    return L

Exemples:

>>> img=[[20, 34, 254, 145, 6], [23, 124, 237, 225, 69], [197, 174,207, 25, 87], [255, 0, 24, 197, 189]]
>>> nbLig(img)
4
>>> nbCol(img)
5
>>> negatif(img)
[[235, 221, 1, 110, 249], [232, 131, 18, 30, 186], [58, 81, 48, 230,168], [0, 255, 231, 58, 66]]
>>> binaire(img,120)
[[0, 0, 1, 1, 0], [0, 1, 1, 1, 0], [1, 1, 1, 0, 0], [1, 0, 0, 1, 1]]

41. Exercice : (sujet 11 - 2023)

La fonction tri_insertion suivante prend en argument une liste tab et trie cette liste en utilisant la méthode du tri par insertion. Compléter cette fonction pour qu'elle réponde à la spécification demandée.

On rappelle le principe du tri par insertion : on considère les éléments à trier un par un, le premier élément constituant, à lui tout seul, une liste triée de longueur 1. On range ensuite le second élément pour constituer une liste triée de longueur 2, puis on range le troisième élément pour avoir une liste triée de longueur 3 et ainsi de suite...

A chaque étape, le premier élément de la sous-liste non triée est placé dans la sous-liste des éléments déjà triés de sorte que cette sous-liste demeure triée.

Le principe du tri par insertion est donc d'insérer à la n-ième itération, le n-ième élément à la bonne place.

liste = [9, 5, 8, 4, 0, 2, 7, 1, 10, 3, 6]

def tri_insertion(tab):
    n = len(tab)
    for i in range(1, n):
        valeur_insertion = tab[...]
        # la variable j sert à déterminer où placer la valeur à ranger
        j = ...
        # tant qu'on 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] = ...

Exemples :

>>> liste = [9, 5, 8, 4, 0, 2, 7, 1, 10, 3, 6]
>>> tri_insertion(liste)
>>> liste
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

42. Exercice : (sujet 13 - 2023)

La fonction rendu_monnaie prend en paramètres deux nombres entiers positifs somme_due et somme_versee. Elle procède au rendu de la monnaie de la différence somme_versee – somme_due pour des achats effectués avec le système monétaire de la zone Euro. On utilise pour cela un algorithme glouton qui commence par rendre le maximum de pièces ou billets de plus grandes valeurs et ainsi de suite. Par la suite, on assimilera les billets à des pièces.

La fonction rendu_monnaie renvoie un tableau de type list contenant les pièces qui composent le rendu.

Toutes les sommes sont exprimées en euros. Les valeurs possibles pour les pièces sont donc contenues dans le tableau pieces = [1, 2, 5, 10, 20, 50, 100, 200].

Ainsi, l’instruction rendu_monnaie(452, 500) renvoie le tableau [20,20,5,2,1].

En effet, la somme à rendre est de 48 euros soit 20 + 20 + 5 + 2 + 1.

Le code de la fonction rendu_monnaie est à compléter :

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

def rendu_monnaie(somme_due, somme_versee):

    rendu = ...
    a_rendre = ...
    i = len(pieces) - 1
    while ... :
        if pieces[i] <= a_rendre :
            rendu.append(...)
            a_rendre = ...
        else :
            i = ...
    return rendu

Exemples :

>>> rendu_monnaie(700, 700)
[]
>>> rendu_monnaie(102, 500)
[200, 100, 50, 20, 20, 5, 2, 1]

43. Exercice : (sujet 22 - 2023)

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

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

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

Exemples :

Compléter la fonction est_parfait fournie à la page suivante qui prend comme argument une chaîne de caractères mot (en lettres majuscules) et qui renvoie le code alphabétique concaténé, le code additionné de mot, ainsi qu’un booléen qui indique si mot est parfait ou pas.

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 est_parfait(mot):
# mot est une chaine de caracteres (en lettres majuscules)
code_concatene = ""
code_additionne = ...
for c in mot:
    code_concatene = code_concatene + ...
    code_additionne = ...
code_concatene = int(code_concatene)
if ... :
    mot_est_parfait = True
else:
    mot_est_parfait = False
return code_additionne, code_concatene, mot_est_parfait

Exemples :

>>> est_parfait("PAUL")
(50, 1612112, False)
>>> est_parfait("ALAIN")
(37, 1121914, True)

44. Exercice : (sujet 26 - 2023)

Recopier et compléter sous Python la fonction suivante en respectant la spécification. On ne recopiera pas les commentaires.

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 :

>>> dichotomie([15, 16, 18, 19, 23, 24, 28, 29, 31, 33], 28)
True
>>> dichotomie([15, 16, 18, 19, 23, 24, 28, 29, 31, 33], 27)
False

45. Exercice : (sujet 7 - 2023)

Programmer la fonction fusion prenant en paramètres deux tableaux non vides tab1 et tab2 (de 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 :

>>> fusion([3, 5], [2, 5])
[2, 3, 5, 5]
>>> fusion([-2, 4], [-3, 5, 10])
[-3, -2, 4, 5, 10]
>>> fusion([4], [2, 6])
[2, 4, 6]