Sujet n°43

Sujet original

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

Exercice n°1

Écrire une fonction ecriture_binaire_entier_positif qui prend en paramètre un entier positif n et renvoie une liste d'entiers correspondant à l'écriture binaire de n.

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.

Ne pas oublier d’ajouter au corps de la fonction une documentation et une ou plusieurs assertions pour vérifier les pré-conditions.

Exemples

>>> ecriture_binaire_entier_positif(0) 
[0]

>>> ecriture_binaire_entier_positif(2) 
[1, 0]

>>> ecriture_binaire_entier_positif(105) 
[1, 1, 0, 1, 0, 0, 1]

Aide

• l'opérateur // donne le quotient de la division euclidienne : 5//2 donne 2 ;
• l'opérateur % donne le reste de la division euclidienne : 5%2 donne 1 ;
• append est une méthode qui ajoute un élément à une liste existante :
  Soit T = [5, 2, 4], alors T.append(10) ajoute 10 à la liste T. Ainsi, T devient [5, 2, 4, 10].
• reverse est une méthode qui renverse les éléments d'une liste.
  Soit T = [5, 2, 4, 10]. Après T.reverse(), la liste T devient [10, 4, 2, 5].

On remarquera qu’on récupère la représentation binaire d’un entier n en partant de la gauche en appliquant successivement les instructions :
b = n%2
n = n//2
répétées autant que nécessaire.

Une solution

def ecriture_binaire_entier_positif(n):
    """
    n - int, entier positif ou nul
    Sortie: list, tableau des bits formant l'écriture binaire de n
    """
    assert isinstance(n, int) and n >= 0, "Le paramètre doit être un entier positif ou nul"
    if n==0:
        return [0]
    else:
        tab = []
        while n > 0:
            tab.append(n%2)
            n = n//2
        tab.reverse()
        return tab


if __name__ == '__main__':
    # Exemples de l'énoncés
    print(ecriture_binaire_entier_positif(0) == [0])
    print(ecriture_binaire_entier_positif(2) == [1, 0])
    print(ecriture_binaire_entier_positif(105) == [1, 1, 0, 1, 0, 0, 1])

    # Exemples supplémentaires
    print(ecriture_binaire_entier_positif(9) == [1, 0, 0, 1])
    print(ecriture_binaire_entier_positif(97) == [1, 1, 0, 0, 0, 0, 1])

Exercice n°2

La fonction tri_bulles prend en paramètre une liste T d’entiers non triés et renvoie la liste triée par ordre croissant.

Commentaires

A nouveau, 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.

Le tri à bulles est un tri en place qui commence par placer le plus grand élément en dernière position en parcourant la liste 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). Le tri place ensuite en avant-dernière position le plus grand élément de la liste privée de son dernier élément en procédant encore à des échanges d’éléments voisins. Ce principe est répété jusqu’à placer le minimum en première position.

Exemple

Pour trier la liste [7, 9, 4, 3] :

• première étape : 7 et 9 ne sont pas échangés, puis 9 et 4 sont échangés, puis 9 et 3 sont échangés, la liste est alors [7, 4, 3, 9] ;
• deuxième étape : 7 et 4 sont échangés, puis 7 et 3 sont échangés, la liste est alors [4, 3, 7, 9] ;
• troisième étape : 4 et 3 sont échangés, la liste est alors [3, 4, 7, 9].

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

def tri_bulles(T): 
    ''' 
    Renvoie le tableau T trié par ordre croissant 
    ''' 
    n = len(T) 
    for i in range(..., ..., -1): 
        for j in range(i): 
            if T[j] > T[...]: 
                ... = T[j] 
                T[j] = T[...] 
                T[j+1] = temp 
    return T

Exemples

>>> tri_bulles([]) 
[]

>>> tri_bulles([7]) 
[7]

>>> tri_bulles([9, 3, 7, 2, 3, 1, 6]) 
[1, 2, 3, 3, 6, 7, 9]

>>> tri_bulles([9, 7, 4, 3]) 
[3, 4, 7, 9]

Commentaires sur le code original

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

Une solution

def tri_bulles(T):
    '''
    Renvoie le tableau T trié par ordre croissant
    '''
    n = len(T)
    for i in range(n-1, 0, -1):
        for j in range(i):
            if T[j] > T[j+1]:
                temp = T[j]
                T[j] = T[j+1]
                T[j+1] = temp
    return T


if __name__ == '__main__':
    # Exemples de l'énoncé
    print(tri_bulles([]) == [] )
    print(tri_bulles([7])  == [7] )
    print(tri_bulles([9, 3, 7, 2, 3, 1, 6]) == [1, 2, 3, 3, 6, 7, 9] )
    print(tri_bulles([9, 7, 4, 3]) == [3, 4, 7, 9] )


    # Exemples supplémentaires
    print(tri_bulles([4, 2, 5, 9, 6, 7, 8]) == [2, 4, 5, 6, 7, 8, 9] )
    print(tri_bulles([8, 5, 1, 7, 6, 9, 1, 4, 2]) == [1, 1, 2, 4, 5, 6, 7, 8, 9] )