Aller au contenu

Sujet n°13

Sujet original

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

Exercice n°1

On s’intéresse au problème du rendu de monnaie. On suppose qu’on dispose d’un nombre infini de billets de 5 euros, de pièces de 2 euros et de pièces de 1 euro.

Le but est d’écrire une fonction nommée rendu dont le paramètre est un entier positif non nul somme_a_rendre et qui retourne une liste de trois entiers n1, n2 et n3 qui correspondent aux nombres de billets de 5 euros (n1), de pièces de 2 euros (n2) et de pièces de 1 euro (n3) à rendre afin que le total rendu soit égal à somme_a_rendre.

On utilisera un algorithme glouton : on commencera par rendre le nombre maximal de billets de 5 euros, puis celui des pièces de 2 euros et enfin celui des pièces de 1 euros.

Exemples

>>> rendu(13)
[2, 1, 1]

>>> rendu(64)
[12, 2, 0]

>>> rendu(89)
[17, 2, 0]
Commentaires

Nommer des variables n1, n2 et n3 sans lien avec leur signification (avec ce qu'elles représentent) n'est vraiment pas un exemple à suivre...

Une solution
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
def rendu(somme_a_rendre):
    """
    somme_a_rendre - int, entier strictement positif
    Sortie: list - tableau d'entiers [n1, n2, n3] tel que
            5*n1 + 2*n2 + n3 = somme_a_rendre,
            n1 étant le plus grand possible puis n2 le plus grand restant
    """
    n1 = somme_a_rendre//5
    reste = somme_a_rendre%5
    n2 = reste//2
    n3 = reste%2
    return [n1, n2, n3]


if __name__ == '__main__':
    print(rendu(13) == [2, 1, 1])
    print(rendu(64) == [12, 2, 0])
    print(rendu(89) == [17, 2, 0])

Exercice n°2

On veut écrire une classe pour gérer une file à l’aide d’une liste chaînée. On dispose d’une classe Maillon permettant la création d’un maillon de la chaîne, celui-ci étant constitué d’une valeur et d’une référence au maillon suivant de la chaîne :

1
2
3
4
class Maillon :
    def __init__(self, v) :
        self.valeur = v
        self.suivant = None

Compléter la classe File suivante où l’attribut dernier_file contient le maillon correspondant à l’élément arrivé en dernier dans la file :

 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class File :
    def __init__(self) :
        self.dernier_file = None

    def enfile(self,element) :
        nouveau_maillon = Maillon(...) 
        nouveau_maillon.suivant = self.dernier_file
        self.dernier_file = ...

    def est_vide(self) :
        return self.dernier_file == None

    def affiche(self) :
        maillon = self.dernier_file
        while maillon != ... :
            print(maillon.valeur)
            maillon = ...

    def defile(self) :
        if not self.est_vide() :
            if self.dernier_file.suivant == None :
                resultat = self.dernier_file.valeur
                self.dernier_file = None
                return resultat
            maillon = ...
            while maillon.suivant.suivant != None :
                maillon = maillon.suivant
            resultat = ...
            maillon.suivant = None
            return resultat
        return None 
Commentaires sur le code original
  1. Pour télécharger l'original du fichier à compléter, cliquer ici.

  2. Pour tester si une valeur correspond à None, il est préférable d'utiliser l'instruction is plutôt que le test d'égalité ==.

  3. La structure de File est une référence du programme de Terminale. L'implémentation objet proposée dans cet exercice est « lourde » et peu naturelle au regard des usages.

On pourra tester le fonctionnement de la classe en utilisant les commandes suivantes dans la console Python :

>>> F = File()
>>> F.est_vide()
True
>>> F.enfile(2)
>>> F.affiche()
2
>>> F.est_vide()
False
>>> F.enfile(5)
>>> F.enfile(7)
>>> F.affiche()
7
5
2
>>> F.defile()
2
>>> F.defile()
5
>>> F.affiche()
7
Une solution

Attention à la dénomination des attributs, il ne faut pas se « mélanger » entre ceux de la classe Maillon et ceux de la classe File.

class Maillon :
    def __init__(self, v) :
        self.valeur = v
        self.suivant = None

class File :
    def __init__(self) :
        self.dernier_file = None

    def enfile(self,element) :
        nouveau_maillon = Maillon(element) 
        nouveau_maillon.suivant = self.dernier_file
        self.dernier_file = nouveau_maillon

    def est_vide(self) :
        return self.dernier_file == None

    def affiche(self) :
        maillon = self.dernier_file
        while maillon != None :
            print(maillon.valeur)
            maillon = maillon.suivant

    def defile(self) :
        if not self.est_vide() :
            if self.dernier_file.suivant == None :
                resultat = self.dernier_file.valeur
                self.dernier_file = None
                return resultat
            maillon = self.dernier_file
            while maillon.suivant.suivant != None :
                maillon = maillon.suivant
            resultat = maillon.suivant.valeur
            maillon.suivant = None
            return resultat
        return None 


if __name__ == '__main__':
    F = File()
    print(F.est_vide() == True)
    F.enfile(2)
    F.affiche()
    print(F.est_vide() == False)
    F.enfile(5)
    F.enfile(7)
    print("\nOn doit avoir 7 puis 5 puis 2 :")
    F.affiche()
    F.defile()
    F.defile()
    print("\nOn doit avoir 7 :")
    F.affiche()