1. Liste - Dictionnaire
  2. Récursivité
  3. sd1 : interface, pile, file
  4. sd2 : POO
  5. BDD : base de données
  6. sd4 : arbres

Page en évolution constante !

Cette page est dédiée aux exercices de début de séances : des exercices ciblés, assez courts, visant à installer des automatismes.

Vous retrouvez l'équivalent en première dans la section avant propos : Warmup - Automatismes .

Cette page est utile pour vous préparer à l'exercice 1 de l'épreuve pratique du baccalauréat. A travailler et retravailler sans modération.

Bon codage à vous !

Liste - Dictionnaire

fonction dico_lettres(phrase) dictionnaire type str

Ecrire une fonction dico_lettres(phrase) qui prend une variable typée str phrase en argument et renvoie le dictionnaire des occurrences des lettres de phrase.

Par exemple, dico_lettres('bob') renvoie {'b':2,'o':1} .

Code de déblocage de la correction :

Ecrire une fonction est_trie_croissant(l) qui prend une variable typée list l en argument et renvoie un booléen qui indique si la liste est triée.

Par exemple, est_trie_croissant([1,2,3]) renvoie True .

Par exemple, est_trie_croissant([]) renvoie True .

Par exemple, est_trie_croissant([2,1,3,4]) renvoie False .

vous pouvez compliquer votre code en traitant les cas où les nombres sont dans l'ordre croissant ou décroissant.

Code de déblocage de la correction :

Dictionnaire, tuple

Baston! Partie 1

On dispose d'un dictionnaire constitué de chaînes de caractères pour clés représentant le nom de personnages et de tuple constituant les valeurs. Les tuples sont constitués de trois entiers : le premier qui représente l'initiative du personnage, le second l'attaque du personnage et le dernier la défense.

characters ={'Conan' : (5, 123, 25), 'Galadriel' : (5, 60, 60), 'Rey' : (6, 100,25), 'Bob l’éponge' : (1, 12, 12), 'Passe kal T rez' : (12, 1200, 1200)} 

  1. Ecrire une fonction firstAttack(characters, character1, character2) qui prend en argument un dictionnaire du type décrit ci-dessus et deux chaînes de caractères qui renvoie le personnage avec le plus d'initiative.

  2. Ajouter une précondition afin de vérifier que character1 et character2 sont dans le dictionnaire characters.

  3. Bonus : proposer d'autres personnages pour nourrir le dictionnaire et rendre la suite plus distrayante.

Code de déblocage de la correction :

Dictionnaire, liste, papier

Baston! Partie 2

On dispose d'un dictionnaire constitué de chaînes de caractères pour clés représentant le nom de personnages et de tuple constituant les valeurs. Les listes sont constitués de trois entiers : le premier qui représente l'initiative du personnage, le second l'attaque du personnage et le dernier la défense.

characters ={'Conan' : [5, 123, 25], 'Galadriel' : [5, 60, 60], 'Rey' : [6, 100,25], 'Bob l’éponge' : [1, 12, 12], 'Passe kal T rez' : [12, 1200, 1200]} 

  1. Ecrire une fonction battle(characters, character1, character2) qui prend en arguments un dictionnaire du type décrit ci-dessus et deux chaînes de caractères qui modifie le dictionnaire conséquement au combat. Le personnage avec plus d'initiative frappe en premier, si le second survie, il frappe à son tour. La fonction renverra l'état des deux combatants. Dans cette question, l'attaque agit sur la défense du personnage attaqué.

    En cas d'égalité d'initiative, les deux attaques portent.

  2. Bonus : proposer d'autres personnages pour nourrir le dictionnaire et rendre la suite plus distrayante.

Code de déblocage de la correction :

chaîne de caractères

Ecrire une fonction supp_lettre(phrase,car) qui prend en arguments phrase et car qui sont de type str

Cette fonction renvoie phrase dans laquelle car a été supprimé.

Liste des tests :


assert supp_lettre("élémentaire","e")=="élémntair"
assert supp_lettre("","i") == ""
        

Code de déblocage de la correction :

Chaîne de caractères, dictionnaires

Ecrire une fonction dico_lettre(phrase) qui prend en argument phrase qui est de type str

Cette fonction renvoie un dictionnaire dont les clés sont les caractères de phrase et les valeurs les occurrences de ces caractères.

Liste des tests :


        assert dico_lettre("Hello world !") == {'H': 1, 'e': 1, 'l': 3, 'o': 2, ' ': 2, 'w': 1, 'r': 1, 'd': 1, '!': 1}
        assert dico_lettre("") == {}
        

Code de déblocage de la correction :

Récursivité

fonction récursive nombre_de_chiffres(n)

Ecrire une fonction récursive nombre_de_chiffres(n) qui prend un entier positif ou nul n en argument et renvoie son nombre de chiffres.

Par exemple, nombre_de_chiffres(12568) renvoie 5.

Code de déblocage de la correction :

fonction récursive est_trie(l) à compléter

Compléter la fonction récursive est_trie(l) qui prend une variable code typée list l en argument et renvoie un booléen qui indique si la liste est triée.


def est_croissant(l):
    if len(l)<=1 : 
        return ...
    elif .... :
        l = l[1:]
        return ........
    else :
        return False


def est_decroissant(l):
    if len(l)<=1 : 
        return True
    elif l[0] >=l[1] :
        l = l[1:]
        return .....
    else :
        return False
        
def est_trie(l):
    if len(l)<=1 : 
        return .....
    elif l[0] <=l[1] :
        l = l[1:]
        return .....
    elif l[0] >=l[1] :
        l = l[1:]
        return .....
    else :
        return .....

    
# La batterie de tests   
def test() :
    assert est_croissant([])==True , 'Erreur test vide'
    assert est_croissant([1])==True , 'Erreur test [1]'
    assert est_croissant([1,2])==True , 'Erreur test [1,2]'
    assert est_croissant([1,2,1])==False , 'Erreur test [1,2,1]'
    assert est_decroissant([])==True , 'Erreur test vide'
    assert est_decroissant([1])==True , 'Erreur test [1]'
    assert est_decroissant([1,1])==True , 'Erreur test [1,1]'
    assert est_decroissant([1,2,1])==False , 'Erreur test [1,2,1]'
    assert est_decroissant([13,2,1])==True , 'Erreur test [13,2,1]'
    assert est_trie([])==True , 'Erreur test vide'
    assert est_trie([1])==True , 'Erreur test [1]'
    assert est_trie([1,2])==True , 'Erreur test [1,2]'
    assert est_trie([1,2,1])==False , 'Erreur test [1,2,1]'
    assert est_trie([1,1])==True , 'Erreur test [1,1]'
    assert est_trie([13,2,1])==True , 'Erreur test [13,2,1]'
    
test()


Code de déblocage de la correction :

Tri insertion récursive

fonction récursive, tri, insertion
  1. Ecrire une fonction récursive insertion(lst, x, i) qui insère correctement x dans lsti est l'index de x. On lancement de la fonction les éléments d'index 0 à i-1 de lst sont triés.

    insertion([2,25,32,5,6,21],5,3) renvoie [2,5,25,32,6,21]

    Code de déblocage de la correction :

  2. Ecrire une fonction récursive tri_insertion_rec(lst,n) qui renvoie lst triée, n-1 est l'indice du dernier terme de la liste.

    Code de déblocage de la correction :

Interface, pile, file

fonction, papier, file

Ecrire une fonction en pseudo code qui permet de supprimer le troisième élément d'une file

Code de déblocage de la correction :

Structures de données, pile , papier , BAC , récursivité

Vu au bac.

Code de déblocage de la correction :

POO

POO

On considère la classe suivante :

class Personnage:                             
    """
    Un personnage du jeu vidéo              
    """

    def __init__(self, genre, name, age=0, pdv = 10, life=True):
        self.genre = genre                 
        self.name = name
        self.age = age
        self.pdv = pdv
        self.life = life
    
    
  1. Quel script écrire pour instancier un personnage nommé Galadriel, de genre féminin, d'âge 600 ans, disposant de 40 points de vie?

  2. Ecrire une méthode in_life(self) qui vérifie si un personnage est en vie en testant si ses points de vie sont au dessus de 0. La méthode définira le statut du personnage.

  3. Tester cette méthode sur Galadriel.

Code de déblocage de la correction :

Ecrire une classe Personnage qui possède trois attributs :

Instancier deux personnages de la classe Personnage :

Créer une fonction combat(perso1,perso2) qui renvoie le vainqueur entre perso1 et perso2 et qui modifie les pdv de chaque joueur

POO

On définit une classe Individu possédant plusieurs attributs : sexe, âge, hobby


class Individu:
    def __init__(self,sexe,age,ho):
        """
        sexe : str "M" ou "F" ou "autre"
        age:int
        ho:list
        """
        self.s=sexe
        self.a=age
        self.h=ho
    
    def estMasculin(self):
        """
        renvoie le booléen True si la méthode s'applique sur un individu féminin et False sinon.
        """
        return self.s=="M"
    
Lucie=Individu("F",17,["course à pied","foot","lecture"])

# Les tests à passer 
assert diffAge(Lucie,Bob) == 2
assert Lucie.estMasculin() == False
assert Lucie.nbHobby()==3
assert nb_Hobby(Lucie)==3

Code de déblocage de la correction :

Base de données

BDD , papier , BAC

Vu au bac.

Identifier le vocabulaire du cours sur les bases de données dans ce schéma relationnel

BDD , papier , BAC

Vu au bac.

BDD , papier , BAC

Vu au bac.

Pour vous aider et en guise de correction: Séance Capytale dédiée

Code de déblocage de la correction :

Arbres

arbre binaire , poo

On considère l’arbre binaire suivant :

Une implémentation de l’arbre binaire ci-dessus en langage Python a été réalisée à l’aide de la classe Nœud ci-dessous :

class Noeud:
    """ Noeud d'un arbre binaire"""
    def __init__(self,v,g=None,d=None):
        self.valeur=v
        self.gauche=g
        self.droite=d

L’objet représentant cet arbre binaire a été déclaré de la manière suivante :

mon_arbre = Noeud("B",Noeud("A"),Noeud("C",Noeud("D"),Noeud("E")))
  1. Que renvoie l’instruction mon_arbre.gauche.valeur ?
  2. Quelle instruction permet d’afficher la valeur de la feuille "D" de cet arbre ?
  3. Dessiner l’arbre a correspondant à la déclaration suivante :
    a = Noeud (5,Noeud(12,Noeud(4),Noeud(3)),Noeud(13,None,Noeud(29)))

Code de déblocage de la correction :

arbre binaire , poo

Le but de cet exercice est d’implémenter un arbre binaire en programmation objet.

Vous devez pour cela compléter la classe Noeud ci-dessous en respectant les contraintes suivantes :

Le construction __init__ est tel qu’un objet Noeud qui aura 3 attributs :

Si il n’y a pas de sous-arbre gauche ou droit, on indiquera la valeur None dans les attributs correspondants.

Dans la classe Noeud, vous devez compléter les trois méthodes suivante :

Exemple d’utilisation de la classe Noeud

En supposant la classe Noeud créée, voici comment l’arbre ci-dessus peut être implémenté :

Compléter le programme ci-dessous

class Noeud():
    """
    Implémentation d'un arbre binaire
    """
    def __init__(self,valeur):
        """
        Constructeur :
        valeur est une chaîne de caractères ou un nombre entier.
        """
        self.valeur = # À compléter
        self.gauche = # À compléter
        self.droit = # À compléter
    def cree_fils_gauche(self,fils_gauche):
        """
        fils_gauche est une chaîne de caractères ou un nombre entier qui sera rajouté comme fils gauche
        au noeud de l'arbre binaire sur lequel s'applique cette méthode.
        La valeur de ce fils rajouté est renvoyée par la méthode.
        """
        self.gauche = # À compléter
        return self.gauche
    def cree_fils_droit(self,fils_droit):
        self.droit = # À compléter
        return self.droit
    def est_feuille(self):
        """
        méthode renvoyant True si le noeud sur lequel s'applique la méthode est une feuille de l'arbre
        et False sinon.
        """
        # À compléter

Code de déblocage de la correction :

arbre binaire , poo

On considère l'implémentation suivante :

class Arbre:
    def __init__(self,valeur):
        self.v=valeur
        self.fg=None
        self.fd=None
    def ajout_gauche(self,val):
        self.fg=Arbre(val)
    
    def ajout_droit(self,val):
        self.fd=Arbre(val)
        
    def affiche(self):
        """permet d'afficher un arbre"""
        if self==None:
            return None
        else :
            return [self.v,Arbre.affiche(self.fg),Arbre.affiche(self.fd)]
    def taille(self):
        if self==None:
            return 0
        else :
            return 1+Arbre.taille(self.fg)+Arbre.taille(self.fd)
    def hauteur(self):
        # Voir la hauteur d'un arbre vide
        if self==None:
            return 0
        elif self.fg == None and self.fd==None :
            return 0
        else : 
            return 1+max(Arbre.hauteur(self.fg),Arbre.hauteur(self.fd))
        
    def get_valeur(self):
        if self==None:
            return None
        else:
            return print(self.v)
        
    
    def racine(self):
        if self==None : return None
        else : return self.v
        
    def est_feuille(self,noeud):
        if self == None : return False
        elif self.fg ==None and self.fd==None and self.v==noeud : return True
        else : return Arbre.est_feuille(self.fg, noeud) or Arbre.est_feuille(self.fd, noeud)
    
    def noeuds(self):
        if self ==None : return []
        else : return [self.v]+Arbre.noeuds(self.fg)+Arbre.noeuds(self.fd)   
        
    

Le but est de calculer ou de lister :

Vous pouvez tester votre code sur cet objet :

abr=Arbre(43)
abr.ajout_gauche(16)
abr.fg.ajout_gauche(8)
abr.fg.ajout_droit(5)
abr.fg.fg.ajout_gauche(99)
abr.fg.fg.fg.ajout_gauche(1)



abr.ajout_droit(36)
abr.fd.ajout_gauche(999)
abr.fd.fg.ajout_gauche(0)

abr.fd.ajout_droit(4)
abr.fd.fd.ajout_droit(6)
abr.fd.fd.fd.ajout_droit(12)
abr.fd.fd.fd.fd.ajout_gauche(9)
abr.fd.fd.fd.fd.ajout_droit(35)
abr.fd.fd.fd.fd.fd.ajout_droit(7)

Code de déblocage de la correction :

arbre binaire , poo

L'implémentation de l'exercice précédent permet d'instancier l'arbre suivant :

abr2=Arbre(13)
abr2.ajout_gauche(10)
abr2.fg.ajout_gauche(5)
abr2.fg.ajout_droit(15)
abr2.fg.fg.ajout_gauche(4)
abr2.fg.fg.fg.ajout_gauche(3)

abr2.ajout_droit(36)
abr2.fd.ajout_gauche(999)
abr2.fd.fg.ajout_gauche(0)
abr2.fd.ajout_droit(14)
abr2.fd.fd.ajout_droit(6)
abr2.fd.fd.fd.ajout_droit(12)
abr2.fd.fd.fd.fd.ajout_gauche(9)
    

Ce qui donne l'affichage suivant :


[13, [10, [5, [4, [3, None, None], None], None], [15, None, None]], [36, [999, [0, None, None], None], [14, None, [6, None, [12, [9, None, None], None]]]]]
  1. Représenter sur un feuille de papier l'arbre abr2.
  2. Donner ou calculer les éléments suivants :

    • La racine
    • La liste des noeuds
    • La liste des feuilles
    • la liste des noeuds internes
    • le nombre de feuilles
    • le nombre de branches
    • sa taille
    • La hauteur
    • LC
    • LCE
    • LCI
    • PM
    • PME
    • PMI

Code de déblocage de la correction :

arbre binaire de recharche , parcours

On propose cet arbre binaire :

  1. Cet arbre est-il un ABR?
  2. Donner la succession des noeuds visités lors d'un parcours infixe.
  3. Donner la succession des noeuds visités lors d'un parcours suffixe.
  4. Donner la succession des noeuds visités lors d'un parcours prefixe.

Code de déblocage de la correction :

arbre binaire de recherche , poo

Un arbre binaire de recherche est un arbre binaire pour lequel chaque nœud possède une étiquette dont la valeur est supérieure ou égale à toutes les étiquettes des nœuds de son fils gauche et strictement inférieure à celles des nœuds de son fils droit. On rappelle que :

Un éditeur réédite des ouvrages. Il doit gérer un nombre important d'auteurs de la littérature. Pour stocker le nom des auteurs, il utilise un programme informatique qui les enregistre dans un arbre binaire de recherche.

L'arbre vide sera noté Null pour les algorithmes de cet exercice.

Si A est un nœud non vide, valeur(A) renvoie le nom de l'auteur ; fils_gauche(A) renvoie le fils gauche du nœud A et fils_droit(A) renvoie le fils droit du nœud A.

L'ordre alphabétique est utilisé pour classer le nom des auteurs.

Par exemple, on a APOLLINAIRE < BAUDELAIRE

Ainsi, pour tout nœud A, si fils_gauche(A) et fils_droit(A) ne sont pas Null, on a :

valeur(fils_gauche(A)) < valeur(A) < valeur(fils_droit(A)).

Par exemple, l'arbre binaire suivant A1 est un arbre binaire de recherche :

    1. Recopier et compléter l'arbre binaire de recherche précédent en insérant successivement dans cet ordre les noms suivants : DUMAS ; HUGO ; ZWEIG ; ZOLA
    2. Quelle est la taille de l'arbre obtenu ? Quelle est la hauteur de cet arbre ?
    3. Plus généralement, si l'arbre est de hauteur $h$, quel est le nombre maximal d'auteurs enregistrés dans cet arbre en fonction de $h$ ?
  1. On définit ici l'équilibre d'un arbre binaire : il s'agit d'un nombre entier positif ou négatif. Il vaut 0 si l'arbre est vide. Sinon il vaut la différence des hauteurs des sous-arbres gauche et droit de l'arbre. Par exemple, si on considère l'arbre suivant que l'on nommera A2.

    Son équilibre vaut -1 car la hauteur de son sous-arbre gauche vaut 1, la hauteur de son sous-arbre droit vaut 2 et $1 - 2 = -1$ Un arbre est dit équilibré si son équilibre vaut -1, 0 ou 1. L'arbre précédent est donc équilibré.

  2. Recopier et compléter l'arbre de ce dernier exemple avec les noms FLAUBERT, BALZAC, PROUST, SAND, WOOLF, COLETTE, CHRISTIE et AUDIARD quitte à modifier l'ordre d'insertion de manière à ce que cet arbre reste équilibré.

  3. L'éditeur souhaite utiliser une fonction récursiverecherche_auteur(ABR, NOM) qui prend en paramètres ABR un arbre binaire de recherche et NOM un nom d'auteur. La fonction renvoie TRUE si NOM est une étiquette de l'arbre ABR et FALSE dans le cas contraire.

    On donne la fonction suivante :

    
    Fonction mystere(ABR, t) :
      SI ABR = NULL :
           RENVOYER FAUX
      SINON SI valeur(ABR) = t :
           RENVOYER VRAI  
      SINON :     
           RENVOYER mystere(fils_gauche(ABR),t) OU mystere(fils_droit(ABR),t) 
  4. Que renvoie l'appel mystere(A2,'SIMENON') ? Justifier la réponse
  5. L'éditeur souhaite utiliser une fonction récursive hauteur(ABR) qui prend en paramètre un arbre binaire ABR et renvoie la hauteur de cet arbre.

  6. Ecrire un algorithme de la fonction hauteur(ABR) qui prend en entrée ABRun arbre binaire de recherche et renvoie sa hauteur. On pourra avoir recours aux fonctions MIN(val1, val2) et MAX(val1, val2) qui renvoient respectivement la plus petite et la plus grande valeur entre val1 et val2.

Code de déblocage de la correction :

Licence Creative Commons
Les différents auteurs mettent l'ensemble du site à disposition selon les termes de la licence Creative Commons Attribution - Pas d’Utilisation Commerciale - Partage dans les Mêmes Conditions 4.0 International