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 !
Pour faciliter vos recherches, en entrée de challenge vous avez :
pile
, récursivité
, etc .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}
.
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.
Dictionnaire, tuple
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)}
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.
Ajouter une précondition afin de vérifier que character1 et character2 sont dans le dictionnaire characters.
Bonus : proposer d'autres personnages pour nourrir le dictionnaire et rendre la suite plus distrayante.
Dictionnaire, liste, papier
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]}
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.
Bonus : proposer d'autres personnages pour nourrir le dictionnaire et rendre la suite plus distrayante.
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") == ""
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("") == {}
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.
est_trie(l)
à compléterComplé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
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]
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.
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
Quel script écrire pour instancier un personnage nommé Galadriel, de genre féminin, d'âge 600 ans, disposant de 40 points de vie?
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.
Tester cette méthode sur Galadriel.
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
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"])
distAge(individu1,individu2)
qui donne la différence d'âge entre deux individus. Rappel valeur absolue : abs(val1,val2)
.nb_hobby(individu)
qui renvoie le nombre de hobby de individu
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.
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")))
a = Noeud (5,Noeud(12,Noeud(4),Noeud(3)),Noeud(13,None,Noeud(29)))
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
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)
objet
Arbre
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]]]]]
abr2
.Donner ou calculer les éléments suivants :
arbre binaire de recharche
, parcours
On propose cet arbre binaire :
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 :
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é.
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)
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.
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