Ep 43

▶ Télécharger le sujet en pdf.

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

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

Exemples :

🐍 Script Python

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

Réponse

Complétez le code ci-dessous

###

Lancer Télécharger Téléverser Recharger Sauvegarder

# Mettre votre code icibksl-nlbksl-nl

---

---

Solution

###

Lancer Télécharger Téléverser Recharger Sauvegarder

def ecriturepy-undbinairepy-undentierpy-undpositif(n):bksl-nl # cas particulier pour n = 0bksl-nl if n == 0:bksl-nl return [0]bksl-nl # cas généralbksl-nl b = []bksl-nl while n != 0:bksl-nl b.append(n % 2)bksl-nl n = n // 2bksl-nl b.reverse()bksl-nl return bbksl-nlbksl-nl

---

---

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

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.

Réponse

Complétez le code ci-dessous

###

Lancer Télécharger Téléverser Recharger Sauvegarder

def tripy-undbulles(T):bksl-nl '''bksl-nl Renvoie le tableau T trié par ordre croissantbksl-nl '''bksl-nl n = len(T)bksl-nl for i in range(...,...,-1):bksl-nl for j in range(i):bksl-nl if T[j] > T[...]:bksl-nl ... = T[j]bksl-nl T[j] = T[...]bksl-nl T[j+1] = tempbksl-nl return Tbksl-nlbksl-nl

---

---

Solution

###

Lancer Télécharger Téléverser Recharger Sauvegarder

def tripy-undbulles(T):bksl-nl '''bksl-nl Renvoie le tableau T trié par ordre croissantbksl-nl '''bksl-nl n = len(T)bksl-nl for i in range(n-1,-1,-1):bksl-nl for j in range(i):bksl-nl if T[j] > T[j+1]:bksl-nl temp = T[j]bksl-nl T[j] = T[j+1]bksl-nl T[j+1] = tempbksl-nl return Tbksl-nlbksl-nl

---

---

Exemple :

🐍 Script Python

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