Aller au contenu

Devoir commun 2

Algorithmes avancés Sujet A

L'usage de la calculatrice n'est pas autorisé

Durée: 100 min

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 :

>>> min_et_max([0, 1, 4, 2, -2, 9, 3, 1, 7, 1])
{'min': -2, 'max': 9}
>>> min_et_max([0, 1, 2, 3])
{'min': 0, 'max': 3}
>>> min_et_max([3])
{'min': 3, 'max': 3}
>>> min_et_max([1, 3, 2, 1, 3])
{'min': 1, 'max': 3}
>>> min_et_max([-1, -1, -1, -1, -1])
{'min': -1, 'max': -1}
Corrigé 
def min_et_max(L):
    mini=L[0]
    maxi=L[0]
    for elt in L:
        if elt>maxi:
            maxi=elt
        if elt<mini:
            mini=elt
    return {'min': mini,'max':maxi}

Exercice 2

Pour cet exercice :

  • On appelle « mot » une chaĂ®ne de caractères composĂ©e avec des caractères choisis parmi les 26 lettres minuscules ou majuscules de l'alphabet,

  • On appelle « phrase » une chaĂ®ne de caractères :

    • composĂ©e avec un ou plusieurs « mots » sĂ©parĂ©s entre eux par un seul caractère espace ' ',
    • se finissant :
      • soit par un point '.' qui est alors collĂ© au dernier mot,
      • soit par un point d'exclamation '!' ou d'interrogation '?' qui est alors sĂ©parĂ© du dernier mot par un seul caractère espace ' '.

Exemples :

  • 'Cet exercice est simple.'
  • 'Le point d exclamation est separe !'

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

>>> nombre_de_mots('Le point d exclamation est separe !')
6
>>> nombre_de_mots('Il y a un seul espace entre les mots !')
9
>>> nombre_de_mots('Combien de mots y a t il dans cette phrase ?')
10
>>> nombre_de_mots('Fin.')
1
Corrigé 
def nombre_de_mots(C):
    if C[-1]=='.':
        return C.count(' ')+1
    else:
        return C.count(' ')

Sans la méthode count:

def nombre_de_mots(C):
    for car in C:
        if car=' ':
            nbm=nbm+1
    if C[-1]=='.':
        return nbm+1
    else:
        return nbm

Exercice 3

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

  • les clefs sont les noms des Ă©lèves ;
  • les valeurs sont des dictionnaires dont les clefs sont les types d’épreuves sous forme de chaĂ®ne de caractères et les valeurs sont les notes obtenues associĂ©es Ă  leurs coefficients dans une liste.

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 du professeur 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
Corrigé

1: dico_result

2: 0

3: 0

4: valeurs

5: note

6: total_coefficients

7: total_points

Exercice 4

Écrire une fonction couples_consecutifs qui prend en paramètre une liste de nombres entiers tab non vide, et qui renvoie la liste (éventuellement vide) des couples d'entiers consécutifs successifs qu'il peut y avoir dans tab.

Exemples : 

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

Corrigé 
def couples_consecutifs(tab):
    res=[]
    for i in range(len(tab)-1):
        if tab[i]+1==tab[i+1]:
        res.append((tab[i],tab[i]+1))
    return res

Exercice 5

On considère l'algorithme de tri de tableau suivant : à chaque étape, on parcourt le sous-tableau des éléments non rangés et on place le plus petit élément en première position de ce sous-tableau.

Exemple avec le tableau : t = [41, 55, 21, 18, 12, 6, 25]

  • Étape 1 : on parcourt tous les Ă©lĂ©ments du tableau, on permute le plus petit Ă©lĂ©ment avec le premier. Le tableau devient t = [6, 55, 21, 18, 12, 41, 25]

  • Étape 2 : on parcourt tous les Ă©lĂ©ments sauf le premier, on permute le plus petit Ă©lĂ©ment trouvĂ© avec le second. Le tableau devient : t = [6, 12, 21, 18, 55, 41, 25]

Et ainsi de suite.

La code de la fonction tri_selection qui implémente cet algorithme est donné ci- dessous.

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

Compléter le code de cette fonction de façon à obtenir :

>>> liste = [41, 55, 21, 18, 12, 6, 25]
>>> tri_selection(liste)
>>> liste
[6, 12, 18, 21, 25, 41, 55]

On rappelle que l'instruction a, b = b, a Ă©change les contenus de a et de b.

Corrigé

1: N

2: k

3: k+1 ou k

4: tab[imin]

5: tab[k]

6: tab[k]

Exercice 6

La fonction rendu_monnaie prend en paramètres deux nombres entiers positifs somme_due et somme_versee et elle permet de procéder au rendu de monnaie de la différence somme_versee – somme_due pour des achats effectués avec le système de pièces de la zone Euro. On utilise pour cela un algorithme glouton qui commence par rendre le maximum de pièces 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 [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 donné ci-dessous :

def rendu_monnaie(somme_due, somme_versee):
    pieces = [1, 2, 5, 10, 20, 50, 100, 200]
    rendu = ...
    a_rendre = ...
    i = len(pieces) - 1
    while a_rendre > ... :
        if pieces[i] <= a_rendre :
            rendu.append(...)
            a_rendre = ...
        else :
            i = ...
    return rendu

Compléter ce code en sachant que rendu_monnaie(700,700) retourne [] et rendu_monnaie(102,500) retourne [200, 100, 50, 20, 20, 5, 2, 1].

Corrigé

1: []

2: somme_versee-somme_due

3: 0

4: pieces[i]

5: a_rendre-pieces[i]

6: i-1

Exercice 7

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.

L'algorithme traite le cas du tableau vide et il est Ă©crit pour que la recherche dichotomique ne se fasse que dans le cas oĂą la valeur est comprise entre les valeurs extrĂŞmes du tableau.

On distingue les trois cas qui renvoient False en renvoyant False, 1 , False, 2 et False, 3.

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

def dichotomie(tab, x):
    # cas du tableau vide
    if ...:
        return False, 1
    # cas oĂą x n'est pas compris entre les valeurs extrĂŞmes
    if (x < tab[0]) or ...:
        return False, 2

    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, 3)
>>> dichotomie([15, 16, 18, 19, 23, 24, 28, 29, 31, 33],1)
(False, 2)
>>> dichotomie([],28)
(False, 1)
Corrigé

1: tab==[]

2: x>tab[-1]

3: (debut+fin)//2

4: True

5: m-1

6: False,3

Exercice 8

On souhaite rechercher dans un tableau les \(k\) plus proches voisins d'un objet donné.

On dispose pour cela d’un tableau t non vide contenant des objets d'un même type et d'une fonction distance qui renvoie la distance entre deux objets quelconques de ce type. Cette fonction distance n'est pas à écrire.

Étant donné un objet cible du même type que ceux du tableau t, on cherche à déterminer les indices des \(k\) éléments du tableau t qui sont les plus proches de cet objet (c’est-à-dire ceux dont la distance à l’objet cible est la plus petite).

  1. On suppose dans cette question que \(k=1\).

    La fonction plus_proche_voisin(t, cible) ci-dessous prend en argument le tableau t et l'objet cible.

    Écrire sur votre copie uniquement le bloc d'instructions manquant pour que la fonction renvoie l'indice d'un plus proche voisin de cible.

    def plus_proche_voisin(t, cible) :
    dmin = distance(t[0], cible)
    idx_ppv = 0
    n = len(t)
    for idx in range(1, n) :
        #bloc Ă  Ă©crire
    return idx_ppv
    2. On considère que le coût en temps du bloc manquant est constant.

    Quel est le coût de la fonction plus_proche_voisin quand \(k = 1\) ?

    Dans la suite, on suppose que \(k \geq 1\).

  2. Une approche naïve consiste aà parcourir le tableau t pour trouver l'indice de l'élément le plus proche de cible, puis à recommencer pour trouver l'indice du deuxième élément le plus proche de cible, et ainsi de suite. Cela implique de parcourir \(k\) fois tout le tableau.

    Afin de réduire le nombre d'appels à la fonction distance, la stratégie suivante permet de ne parcourir le tableau t qu'une seule fois. Lors de ce parcours, on stocke dans une liste kppv, initialement vide, les tuples (idx, d) où idx est l'indice d'un \(k\) plus proche voisin de cible déjà rencontré et d la distance correspondante, triés dans l'ordre décroissant de leur distance à cible.

    La fonction recherche_kppv(t, k, cible) ci-après renvoie ainsi la liste des tuples (idx, d) où idx est l'indice d'un \(k\) plus proche voisin de cible dans le tableau t et d la distance correspondante.

    On admet que la fonction insertion(kppv, idx, d) insère le tuple (idx, d) dans la liste kppv de sorte que celle-ci demeure triée dans l’ordre décroissant des distances.

    def recherche_kppv(t, k, cible):
    kppv = []
    n = len(t)
    for idx in range(n):
        obj = t[idx]
        if len(kppv)<k:
            insertion(kppv, idx, distance(obj, cible))
        else:
            i0, d0 = kppv[0]
            if distance(obj, cible)<d0:
                kppv.pop(0) # supprime le 1er élément de kppv
                insertion(kppv, idx, distance(obj, cible))
    return kppv

    a. On remarque qu'il y a plusieurs appels identiques Ă  la fonction distance(obj,cible). Comment ne faire qu'un seul appel de cette fonction ?

    b. Expliquer l'intérêt de maintenir la liste kppvtriée.

    c. Écrire une fonction insertion(kppv, idx, d) qui insère le tuple (idx, d) dans la liste kppv préalablement triée en préservant l'ordre décroissant selon l'élément d.

    On pourra éventuellement utiliser la méthode insert dont un exemple d'utilisation est rappelé: 

    >>> liste = [4, 2, 8, 9]
>>> liste.insert(1, 3)
>>> liste
[4, 3, 2, 8, 9]