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

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.

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.

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.

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") == ""
        

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("") == {}
        

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.

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()

Tri insertion récursive

1. Ecrire une fonction récursive insertion(lst, x, i) qui insère correctement x dans lst où i 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 :

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

Vu au bac.

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.

Ecrire une classe Personnage qui possède trois attributs :

• nom de type str
• pdv de type int
• qualification de type str

Instancier deux personnages de la classe Personnage :

• personnage1 avec nom ='Bob', pdv = 50 et qualification = 'fantassin'
• personnage2 avec nom ='Pascual', pdv = 20 et qualification = 'chevalier'

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

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

• Instancier l'individu Bob agé de 15 ans, de sexe Masculin, et de hobby: tennis, théâtre et couture.
• Indiquer le script Python pour obtenir la liste des hobbies de Lucie.
• Ecrire une fonction distAge(individu1,individu2) qui donne la différence d'âge entre deux individus. Rappel valeur absolue : abs(val1,val2).
• Indiquer le script Python pour obtenir la différence d'âge en Lucie et Bob
• Ecrire une fonction nb_hobby(individu) qui renvoie le nombre de hobby de individu
• Transformer la fonction nb_hobby en une méthode nbHobby

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

Vu au bac.

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

Vu au bac.

Vu au bac.

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

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

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 :

• L’attribut valeur contiendra la valeur (ou étiquette) associée au nœud.
• L’attribut gauche contiendra le sous-arbre gauche.
• L’attribut droit seront le sous-arbre droit.

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 :

La méthode est_feuille() renverra un booléen selon que l’objet est une feuille de l’arbre ou non.
• La méthode cree_fils_gauche() prend en paramètre une valeur et crée une feuille à gauche dont la valeur est passée en paramètres. De plus, elle renvoie le nœud fils.
• La méthode cree_fils_droit() est construite sur le même modèle que cree_fils_gauche(). De même, elle renvoie le nœud fils.

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

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 :

• La racine
• La liste des noeuds
• La liste des feuilles
• la liste des noeuds internes
• le nombre de feuilles
• le nombre de branches
• l'arité
• sa taille T(B)
• La hauteur de B, H(B)
• LC(B)
• LCE(B)
• LCI(B)
• PM(B)
• PME(B)
• PMI(B)

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)

• Représenter cet arbre
• Choisir quelques éléments dans la liste des données à traiter sur cet arbre. A vous d'écrire les méthodes et/ou fonctions supplémentaires pour cet objet Arbre

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

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.

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 :

• sa taille est son nombre de nœuds
• sa hauteur est le nombre de niveaux qu'il contient.

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

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

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) 

3. Que renvoie l'appel mystere(A2,'SIMENON') ? Justifier la réponse

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.

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