Sujet n°11

Sujet original

Pour télécharger l'énoncé original, cliquer ici.

Exercice n°1

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

À 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

Une solution

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
    """
    resultat = 0
    puis = 1
    for i in range(len(tab)-1, -1, -1):
        resultat = resultat + tab[i]*puis
        puis = puis*2
    return resultat


if __name__ == '__main__':
    # Exemples de l'énoncé
    print(convertir([1, 0, 1, 0, 0, 1, 1]) == 83)
    print(convertir([1, 0, 0, 0, 0, 0, 1, 0]) == 130)

    # Exemples supplémentaires
    print(convertir([0]) == 0)
    print(convertir([1]) == 1)
    print(convertir([1, 1, 1]) == 7)
    print(convertir([1, 0, 0]) == 4)

Exercice n°2

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.

Commentaires

Ici, le mot « liste » est à comprendre dans le sens « liste Python » (c'est-à-dire tableau) plutôt que dans le sens du type abstrait de données liste étudié en Terminale.

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.

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

Commentaires sur le code original

1. Pour télécharger l'original du fichier à compléter, cliquer ici.

2. Dans cet exercice, il faut reprogrammer un algorithme usuel, à avoir travaillé de nombreuses fois !

Exemple

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

Une solution

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

if __name__ == '__main__':
    # Exemple de l'énoncé
    liste = [9, 5, 8, 4, 0, 2, 7, 1, 10, 3, 6]
    tri_insertion(liste)
    print(liste == [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10])

    # Exemples supplémentaires
    liste = [2, 5, -1, 7, 0, 28]
    tri_insertion(liste)
    print(liste == [-1, 0, 2, 5, 7, 28])

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