Exercice 1 (0_1) : Récursivité
Cet exercice traite du thème «programmation», et principalement de la récursivité.
On rappelle qu'une chaîne de caractères peut être représentée en Python par un texte
entre guillemets "" et que :
- la fonction len renvoie la longueur de la chaîne de caractères passée en
paramètre ; - si une variable ch désigne une chaîne de caractères, alors ch[0] renvoie son
premier caractère, ch[1] le deuxième, etc. ; - l'opérateur + permet de concaténer deux chaînes de caractères.
Exemples :
>>> texte = "bricot"
>>> len(texte)
6
>>> texte[0]
"b"
>>> texte[1]
"r"
>>> "a" + texte
"abricot"
On s'intéresse dans cet exercice à la construction de chaînes de caractères suivant
certaines règles de construction.
Règle A : une chaîne est construite suivant la règle A dans les deux cas suivants:
- soit elle est égale à "a" ;
- soit elle est de la forme "a"+chaine+"a", où chaine est une chaîne de
caractères construite suivant la règle A.
Règle B : une chaîne est construite suivant la règle B dans les deux cas suivants :
- soit elle est de la forme "b"+chaine+"b", où chaine est une chaîne de
caractères construite suivant la règle A ; - soit elle est de la forme "b"+chaine+"b", où chaine est une chaîne de
caractères construite suivant la règle B.
On a reproduit ci-dessous l'aide de la fonction choice du module random.
>>>from random import choice
>>>help(choice)
Help on method choice in module random:
choice(seq) method of random.Random instance
Choose a random element from a non-empty sequence.
La fonction A() ci-dessous renvoie une chaîne de caractères construite suivant la règle
A, en choisissant aléatoirement entre les deux cas de figure de cette règle.
def A():
if choice([True, False]):
return "a"
else:
return "a" + A() + "a"
1.1. a. Cette fonction est-elle récursive ? Justifier.
b. La fonction choice([True, False]) peut renvoyer False un très grand
nombre de fois consécutives. Expliquer pourquoi ce cas de figure amènerait à
une erreur d'exécution.
Dans la suite, on considère une deuxième version de la fonction A. À présent, la fonction
prend en paramètre un entier n tel que, si la valeur de n est négative ou nulle, la
fonction renvoie "a". Si la valeur de n est strictement positive, elle renvoie une chaîne
de caractères construite suivant la règle A avec un n décrémenté de 1, en choisissant
aléatoirement entre les deux cas de figure de cette règle.
def A(n):
if ... or choice([True, False]) :
return "a"
else:
return "a" + ... + "a"
1.2. a. Recopier sur la copie et compléter aux emplacements des points de
suspension ... le code de cette nouvelle fonction A.
b. Justifier le fait qu'un appel de la forme A(n) avec n un nombre entier positif
inférieur à 50, termine toujours.
On donne ci-après le code de la fonction récursive B qui prend en paramètre un entier n
et qui renvoie une chaîne de caractères construite suivant la règle B.
def B(n):
if n <= 0 or choice([True, False]):
return "b" + A(n-1) + "b"
else:
return "b" + B(n-1) + "b"
On admet que :
- les appels A(-1)et A(0) renvoient la chaîne "a";
- l’appel A(1) renvoie la chaîne "a" ou la chaîne "aaa";
- l’appel A(2) renvoie la chaîne "a", la chaîne "aaa" ou la chaîne "aaaaa".
1.3. Donner toutes les chaînes possibles renvoyées par les appels B(0), B(1)
et B(2).
On suppose maintenant qu'on dispose d'une fonction raccourcir qui prend comme
paramètre une chaîne de caractères de longueur supérieure ou égale à 2, et renvoie la
chaîne de caractères obtenue à partir de la chaîne initiale en lui ôtant le premier et le
dernier caractère.
Par exemple :
>>> raccourcir("abricot")
"brico"
>>> raccourcir("ab")
""
1.4. a. Recopier sur la copie et compléter les points de suspension ... du code de la
fonction regleA ci-dessous pour qu'elle renvoie True si la chaîne passée en
paramètre est construite suivant la règle A, et False sinon.
def regleA(chaine):
n = len(chaine)
if n >= 2:
return chaine[0] == "a" and chaine[n-1] == "a" and.regleA(...)
else:
return chaine == ...
b. Écrire le code d’une fonction regleB, prenant en paramètre une chaîne de
caractères et renvoyant True si la chaîne est construite suivant la règle B,
et False sinon.
Exercice 2 : Modularité
Nous avons le programme suivant :
def conv_10_to_2(number):#sur 15 bits
number2 = ""
while number>0 :
if number%2 == 0 :
number2 = "0" + number2
else : #number10%2 == 1
number2 = "1" + number2
number = number//2
#ajoute des 0 à gauche pour le mettre sur 15 bits
lg_number2 = 15 - len(number2)
for __ in range(lg_number2):
number2 = "0" + number2
return number2
number10 = -128
if number10 >= 0 :
signe = "0"
else :
signe = "1"
#Etape 1: Convertir en binaire le nombre en valeur absolue
if number10 > 0 :
number2 = conv_10_to_2(number10)
else :
number2 = conv_10_to_2(-number10)
print("conve",number2)
#Etape 2: Inverse le nombre binaire
if number10 < 0 :
inversion2 = ""
for c in number2 :
if c == "0":
inversion2 += "1"
else :
inversion2 += "0"
print("inver",inversion2)
#Etape 3: Ajoute 1 à inversion
if number10 < 0 :
posi = len(inversion2)-1
retenue = 1
relatif2 = ""
while posi>=0 :
if inversion2[posi] == "0" and retenue == 1 :
relatif2 = "1" + relatif2
retenue = 0
elif inversion2[posi] == "1" and retenue == 1 :
relatif2 = "0" + relatif2
retenue = 1
else :
relatif2 = inversion2[posi] + relatif2
posi -= 1
relatif2 = signe + relatif2
else:
relatif2 = signe + number2
print("rela",relatif2)
Ce programme permet de convertir un nombre relatif (125, -128, 4, -9, ...) en binire. Pour ce faire, il faut réaliser les 3 étapes suivantes :
Etape 1 : Convertir en binaire;
Etape 2 : Inverser en binaire, si négatif;
Etape 3 : Ajouter un, si négatif.
2.1. Copier et tester le code. Vous devez obtenir :
conve 000000010000000
inver 111111101111111
rela 1111111110000000
Nous souhaitons créer des fonctions pour simplifier et réutiliser ce code dans d'autres modules.
2.2. En vous aidant du code dans l'étape 2, écrire la fonction inverse() qui prend comme argument un binaire (string) et qui retourne l'inverse.
Exemple :
inver 0000000
inver 1111111
2.3. En vous aidant du code dans l'étape 3, écrire la fonction addition() qui prend comme argument un binaire (string) et qui retourne l'addition de 1.
Exemple :
addi 000001
addi 000010
2.4. En vous aidant des fonctions que vous avez créé et du code, écrire la fonction conv_rela() qui prend comme argument un entier relatif et qui retourne sa conversion en binaire
Exemple :
conv_rela 1111111110000000
conv_rela 1111111111111111
Exercice 3 (1_5) : Poo
Les participants à un jeu de LaserGame sont répartis en équipes et s’affrontent dans
ce jeu de tir, revêtus d’une veste à capteurs et munis d’une arme factice émettant
des infrarouges.
Les ordinateurs embarqués dans ces vestes utilisent la programmation orientée objet
pour modéliser les joueurs. La classe Joueur est définie comme suit :
class Joueur:
def __init__(self, pseudo, identifiant, equipe):
’’’ constructeur ’’’
self.pseudo = pseudo
self.equipe = equipe
self.id = identifiant
self.nb_de_tirs_emis = 0
self.liste_id_tirs_recus = []
self.est_actif = True
def tire(self):
’’’méthode déclenchée par l'appui sur la gachette’’’
if self.est_actif == True:
self.nb_de_tirs_emis = self.nb_de_tirs_emis + 1
def est_determine(self):
’’’methode qui renvoie True si le joueur réalise un
grand nombre de tirs’’’
return self.nb_de_tirs_emis > 500
def subit_un_tir(self, id_recu):
’’’méthode déclenchée par les capteurs de la
veste’’’
if self.est_actif == True:
self.est_actif = False
self.liste_id_tirs_recus.append(id_recu)
3.1. Parmi les instructions suivantes, recopier celle qui permet de déclarer un objet
joueur1, instance de la classe Joueur, correspondant à un joueur dont le
pseudo est “Sniper”, dont l’identifiant est 319 et qui est intégré à l’équipe “A”:
Instruction 1 : joueur1 = ["Sniper", 319, "A"]
Instruction 2 : joueur1 = new Joueur["Sniper", 319, "A"]
Instruction 3 : joueur1 = Joueur("Sniper", 319, "A")
Instruction 4 : joueur1 = Joueur{"pseudo":"Sniper",
"id":319, "equipe":"A"}
3.2. La méthode subit_un_tir réalise les actions suivantes :
Lorsqu’un joueur actif subit un tir capté par sa veste, l’identifiant du tireur est
ajouté à l’attribut liste_id_tirs_recus et l’attribut est_actif prend la
valeur False (le joueur est désactivé). Il doit alors revenir à son camp de base
pour être de nouveau actif.
a. Écrire la méthode redevenir_actif qui rend à nouveau le joueur actif
uniquement s’il était précédemment désactivé.
b. Écrire la méthode nb_de_tirs_recus qui renvoie le nombre de tirs reçus
par un joueur en utilisant son attribut liste_id_tirs_recus.
3.3. Lorsque la partie est terminée, les participants rejoignent leur camp de base
respectif où un ordinateur, qui utilise la classe Base, récupère les données.
La classe Base est définie par :
- ses attributs :
– equipe : nom de l’équipe (str). Par exemple, “A” ,
– liste_des_id_de_l_equipe qui correspond à la liste (list) des
identifiants connus des joueurs de l’équipe,
– score : score (int) de l’équipe, dont la valeur initiale est 1000 ;
- ses méthodes :
– est_un_id_allie qui renvoie True si l’identifiant passé en paramètre
est un identifiant d’un joueur de l’équipe, False sinon,
– incremente_score qui fait varier l’attribut score du nombre passé en
paramètre,
– collecte_information qui récupère les statistiques d’un participant
passé en paramètre (instance de la classe Joueur) pour calculer le score
de l’équipe .
def collecte_information(self,participant):
if participant.equipe == self.equipe : # test 1
for id in participant.liste_id_tirs_recus:
if self.est_un_id_allie(id): # test 2
self.incremente_score(-20)
else:
self.incremente_score(-10)
a. Indiquer le numéro du test (test 1 ou test 2) qui permet de vérifier qu’en fin de
partie un participant égaré n’a pas rejoint par erreur la base adverse.
b. Décrire comment varie quantitativement le score de la base lorsqu’un joueur
de cette équipe a été touché par le tir d’un coéquipier.
On souhaite accorder à la base un bonus de 40 points pour chaque joueur
particulièrement déterminé (qui réalise un grand nombre de tirs).
3.4. Recopier et compléter, en utilisant les méthodes des classes Joueur et Base,
les 2 lignes de codes suivantes qu’il faut ajouter à la fin de la méthode
collecte_information :
........ #si le participant réalise un grand nombre de tirs
......... #le score de la Base augmente de 40
Exercice 4 (6_5) : Exécution de programmes, recherche et corrections de bugs
Les questions proposées sont indépendantes les unes des autres.
4.1. On considère la fonction somme(n) qui reçoit en paramètre un entier n
strictement positif et renvoie le résultat du calcul 1 +
def somme(n) :
total = 0
for i in range(n) :
total = total + 1/i
return total
Lors de l’exécution de somme(10), le message d’erreur "ZeroDivisionError:
division by zero" apparait. Identifier le problème et corriger la fonction pour
qu’elle effectue le calcul demandé.
4.2. On considère la fonction maxi(L) qui prend comme paramètre une liste L de
nombres et renvoie le plus grand nombre de cette liste :
def maxi(L) :
indice = 0
maximum = 0
while indice <= len(L) :
if L[indice] > maximum :
maximum = L[indice]
indice = indice + 1
return maximum
a. Lors de l’exécution de maxi([2, 4, 9, 1]) une erreur est déclenchée.
Identifier et corriger le problème.
b. Le bug précédent est maintenant corrigé. Que renvoie à présent
l’exécution de maxi([-2, -7, -3]) ? Modifier la fonction pour qu’elle
renvoie le bon résultat.
4.3. On souhaite réaliser une fonction qui génère une liste de n joueurs identifiés
par leur numéro. Par exemple on souhaite que l’appel genere(3) renvoie la
liste [‘Joueur 1’, ‘Joueur 2’, ‘Joueur 3’].
def genere(n) :
L = []
for i in range(1, n+1) :
L.append('Joueur '+i)
return L
L’appel genere(3) déclenche l’erreur suivante : TypeError: can only
concatenate str (not "int") to str.
Expliquer ce message d’erreur et corriger la fonction afin de régler le problème.
4.4. On considère la fonction suite(n) qui reçoit un entier positif et renvoie un
entier.
def suite(n) :
if n == 0 :
return 0
else :
return 3+2*suite(n-2)
a. Quelle valeur renvoie l’appel de suite(6) ?
b. Que se passe-t-il si on exécute suite(7) ?
4.5. On considère le code Python ci-dessous :
x = 4
L = []
def modif(x, L) :
x = x + 1
L.append(2*x)
return x, L
print(modif(x, L))
print(x, L)
a. Qu’affiche le premier print ?
b. Qu’affiche le second print ?