BNS 2022
En fonction des commentaires et des avis des différents correcteurs, on pourra avoir sur les sujets :
- une marque
pour signifier qu'il peut être donné aux élèves, en l'état - une
: le sujet peut-être donné après quelques modifications mineures. - une
qui conseille de ne pas le proposer aux élèves, à moins d'une refonte assez conséquente.
Sujet 01 ⚓︎
Exercice 01.1
Écrire une fonction recherche qui prend en paramètres caractere, un caractère, et
mot, une chaîne de caractères, et qui renvoie le nombre d’occurrences de caractere
dans mot, c’est-à-dire le nombre de fois où caractere apparaît dans mot.
Exemples :
>>> recherche('e', "sciences")
2
>>> recherche('i',"mississippi")
4
>>> recherche('a',"mississippi")
0
G.Connan s'est chargé de la relecture du sujet 01. Voici son verdict :
Pas grand chose mis à part cette distinction caractère/chaîne de caractères qui n'existe pas en Python. La personne qui a rédigé est sûrement une habituée d'Ocaml en prépa :) Il y a aussi cette espace après la virgule des appels de recherche plus ou moins existante... Enfin le choix du nom
rechercheest discutable car cela ferait plus penser à un test renvoyant un booléen (je rechercheidansmississippi). On aurait pu choisircompte_lettres,nb_occurrences,compte_occurrences, etc.
(source : commentaires à propos du 01.1)
Je le rejoins sur l'ensemble des points.
Écrire une fonction nb_occurrences qui prend en paramètres caractere, un caractère (ie une chaîne de caractères de longueur 1), et
mot, une chaîne de caractères, et qui renvoie le nombre d’occurrences de caractere
dans mot, c’est-à-dire le nombre de fois où caractere apparaît dans mot.
Exemples :
>>> nb_occurrences('e', 'sciences')
2
>>> nb_occurrences('i', 'mississippi')
4
>>> nb_occurrences('a', 'mississippi')
0
Dans ce corrigé on adopte le nom de l'énoncé corrigé :
1 2 3 4 5 6 | |
Version avec parcourt par les indices, qui n'a aucun intérêt :
1 2 3 4 5 6 | |
Version hors programme qui utilise le cast automatique de booléen vers int
1 2 | |
Écrire une fonction `recherche` qui prend en paramètres `caractere`, un caractère, et
`mot`, une chaîne de caractères, et qui renvoie le nombre d’occurrences de `caractere`
dans `mot`, c’est-à-dire le nombre de fois où `caractere` apparaît dans `mot`.
Exemples :
```python
>>> recherche('e', "sciences")
2
>>> recherche('i',"mississippi")
4
>>> recherche('a',"mississippi")
0
```
Exercice 01.2
On s’intéresse à un algorithme récursif qui permet de rendre la monnaie à partir d’une liste donnée de valeurs de pièces et de billets.
Le système monétaire est donné sous
forme d’une liste pieces=[100, 50, 20, 10, 5, 2, 1].
(on supposera qu’il n’y a
pas de limitation quant à leur nombre).
On cherche à donner la liste de pièces à rendre
pour une somme donnée en argument.
Compléter le code Python ci-dessous de la fonction rendu_glouton qui implémente cet
algorithme et renvoie la liste des pièces à rendre.
1 2 3 4 5 6 7 8 9 10 11 | |
>>>rendu_glouton_r(68,[],0)
[50, 10, 5, 2, 1]
>>>rendu_glouton_r(291,[],0)
[100, 100, 50, 20, 20, 1]
Là encore, je vous laisse apprécier le verdict de G. Connan : commentaires à propos du 01.2
Je rajouterais bien un trou dans le texte de la fonction, au niveau des appels récursifs. On pourrait aussi passer la liste des pièces en paramètre de la fonction et traiter le cas où le rendu n'est pas possible (renvoie de None).
On s’intéresse à un algorithme récursif qui permet de rendre la monnaie à partir d’une liste donnée de valeurs de pièces et de billets.
Le système monétaire est donné sous forme d’une liste :
pieces = [100, 50, 20, 10, 5, 2, 1]
On supposera qu’il n’y a pas de limitation quant à leur nombre.
On cherche à donner la liste de pièces à rendre pour une somme donnée en argument. Compléter le code Python ci-dessous de la fonction rendu_glouton qui implémente cet
algorithme et renvoie la liste des pièces à rendre.
1 2 3 4 5 6 7 8 9 10 11 | |
On devra obtenir :
>>> rendu_glouton(68, [], 0)
[50, 10, 5, 2, 1]
>>> rendu_glouton(291, [], 0)
[100, 100, 50, 20, 20, 1]
G. Connan propose un certain nombre de corrections sur sa page.
La version attendue (sans la valeur par défaut) et en mettant les espaces correctement :
1 2 3 4 5 6 7 8 9 10 11 | |
Sachant que cette fonction s'appelle toujours avec la liste vide en deuxième paramètre et 0 a priori en 3e... sauf si on sait qu'on n'a plus de billets de 100.
G. Connan ne détaille pas celle avec la fonction auxiliaire , et pour cause : la fonction en question n'a aucun sens hors la fonction principale et devrait donc être définie à l'intérieur de cette-dernière ce qui fait un code complètement hors-programme :
def rendu_glouton(a_rendre):
def rendu_glouton_aux(a_rendre, solution, i):
if a_rendre == 0:
return solution
piece = pieces[i]
if piece <= a_rendre:
solution.append(piece)
return rendu_glouton_aux(a_rendre - piece, solution, i)
else:
return rendu_glouton_aux(a_rendre, solution, i+1)
pieces = [100, 50, 20, 10, 5, 2, 1]
return rendu_glouton_aux(a_rendre, [], 0)
Version plus générique, avec la liste des pièces en paramètre :
def rendu_glouton(a_rendre, pieces):
def rendu_glouton_aux(a_rendre, solution, i):
if a_rendre == 0:
return solution
elif i >= len(pieces):
return None
else:
piece = pieces[i]
if piece <= a_rendre:
solution.append(piece)
return rendu_glouton_aux(a_rendre - piece, solution, i)
else:
return rendu_glouton_aux(a_rendre, solution, i+1)
return rendu_glouton_aux(a_rendre, [], 0)
Exemples :
>>> rendu_glouton(291, [100, 50, 20, 10, 5, 2, 1])
[100, 100, 50, 20, 20, 1]
>>> rendu_glouton(291, [50, 20, 10, 2, 1])
[50, 50, 50, 50, 50, 20, 20, 1]
>>> rendu_glouton(291, [50, 20, 10, 2])
None
On s’intéresse à un algorithme récursif qui permet de rendre la monnaie à partir d’une
liste donnée de valeurs de pièces et de billets.
Le système monétaire est donné sous
forme d’une liste `pieces=[100, 50, 20, 10, 5, 2, 1]`.
(on supposera qu’il n’y a
pas de limitation quant à leur nombre).
On cherche à donner la liste de pièces à rendre
pour une somme donnée en argument.
Compléter le code Python ci-dessous de la fonction `rendu_glouton` qui implémente cet
algorithme et renvoie la liste des pièces à rendre.
```python linenums='1'
pieces = [100,50,20,10,5,2,1]
def rendu_glouton(arendre, solution=[], i=0):
if arendre == 0:
return ...
p = pieces[i]
if p <= ... :
solution.append(...)
return rendu_glouton(arendre - p, solution, i)
else :
return rendu_glouton(arendre, solution, ...)
```
On devra obtenir :
```python
>>>rendu_glouton_r(68,[],0)
[50, 10, 5, 2, 1]
>>>rendu_glouton_r(291,[],0)
[100, 100, 50, 20, 20, 1]
```
Sujet 02 ⚓︎
Attention sujet très mathématique (trop ?) ! Pourrait lui valoir une
Exercice 02.1
Soit le couple (note,coefficient):
noteest un nombre de type flottant (float) compris entre 0 et 20 ;coefficientest un nombre entier positif.
Les résultats aux évaluations d'un élève sont regroupés dans une liste composée de
couples (note,coefficient).
Écrire une fonction moyenne qui renvoie la moyenne pondérée de cette liste donnée en
paramètre.
Par exemple, l’expression moyenne([(15,2),(9,1),(12,3)]) devra renvoyer le
résultat du calcul suivant :
Pas grand chose à dire sur cet exercice. Je ne sais pas si une moyenne pondérée fait vraiment partie des algorithmes classiques censé avoir été étudié en classe... de NSI, pas de matématiques ;-).
G. Connan qui a relu ce sujet s'interroge sur les attendus :
Pas grand chose à dire, à part que c'est plus facile à écrire qu'un tri ou un algo glouton comme on en demande dans d'autres sujets. Attend-on une gestion de la liste vide, des coefficients négatifs ?
Source : commentaires à propos du 02.1
Il a été suggéré de préciser strictement positif pour les coefficients.
Soit le couple (note, coefficient):
noteest un nombre de type flottant (float) compris entre 0 et 20 ;coefficientest un nombre entier strictement positif.
Les résultats aux évaluations d'un élève sont regroupés dans une liste composée de
couples (note, coefficient).
Écrire une fonction moyenne qui renvoie la moyenne pondérée de cette liste donnée en
paramètre.
Par exemple, l’expression moyenne([(15, 2), (9, 1), (12, 3)]) devra renvoyer le
résultat du calcul suivant :
1 2 3 4 5 6 7 8 9 | |
Une version plus pythonesque mais probablement inconnue de la plupart des élèves de NSI :
1 2 3 4 5 6 7 | |
Soit le couple (`note`,`coefficient`):
- `note` est un nombre de type flottant (`float`) compris entre 0 et 20 ;
- `coefficient` est un nombre entier positif.
Les résultats aux évaluations d'un élève sont regroupés dans une liste composée de
couples (`note`,`coefficient`).
Écrire une fonction `moyenne` qui renvoie la moyenne pondérée de cette liste donnée en
paramètre.
Par exemple, l’expression `moyenne([(15,2),(9,1),(12,3)])` devra renvoyer le
résultat du calcul suivant :
\[\dfrac{2 \times 15 + 1 \times 9 + 3 \times 12 }{2+1+3}=12,5\]
Exercice 02.2
On cherche à déterminer les valeurs du triangle de Pascal. Dans ce tableau de forme triangulaire, chaque ligne commence et se termine par le nombre 1. Par ailleurs, la valeur qui occupe une case située à l’intérieur du tableau s’obtient en ajoutant les valeurs des deux cases situées juste au-dessus, comme l’indique la figure suivante :
Compléter la fonction pascal ci-après. Elle doit renvoyer une liste correspondant au
triangle de Pascal de la ligne 1 à la ligne n où n est un nombre entier supérieur ou égal à
2 (le tableau sera contenu dans la variable C). La variable Ck doit, quant à elle, contenir,
à l’étape numéro k, la k-ième ligne du tableau.
1 2 3 4 5 6 7 8 9 | |
Pour n = 4, voici ce qu'on devra obtenir :
>>> pascal(4)
[[1], [1, 1], [1, 2, 1], [1, 3, 3, 1], [1, 4, 6, 4, 1]]
n = 5, voici ce qu'on devra obtenir :
>>> pascal(5)
[[1], [1, 1], [1, 2, 1], [1, 3, 3, 1], [1, 4, 6, 4, 1], [1, 5, 10, 10, 5, 1]]
G. Connan note que :
- ce deuxième exercice est bien trop mathématique, complétant ainsi après la moyenne pondérée un sujet vraiment orienté maths ;
- des libertés encore sur les espaces
- le schéma en triangle des valeurs ne facilite pas la lecture (le traditionnel triangle rectangle aurait été préférable)
Source : commentaires à propos du 02.2
On cherche à déterminer les valeurs du triangle de Pascal. Dans ce tableau de forme triangulaire, chaque ligne commence et se termine par le nombre 1. Par ailleurs, la valeur qui occupe une case située à l’intérieur du tableau s’obtient en ajoutant les valeurs des deux cases situées juste au-dessus et au-dessus à gauche, comme l’indique la figure suivante :
Compléter la fonction pascal ci-après. Elle doit renvoyer une liste correspondant au
triangle de Pascal de la ligne 1 à la ligne n où n est un nombre entier supérieur ou égal à
2 (le tableau sera référencé par la variable triangle). La variable tab_k doit, quant à elle, référencer, à l’étape numéro k, la k-ième ligne du tableau. Ne pas oublier le dernier 1 sur la ligne.
1 2 3 4 5 6 7 8 9 | |
Pour n = 4, voici ce qu'on devra obtenir :
>>> pascal(4)
[[1], [1, 1], [1, 2, 1], [1, 3, 3, 1], [1, 4, 6, 4, 1]]
n = 5, voici ce qu'on devra obtenir :
>>> pascal(5)
[[1], [1, 1], [1, 2, 1], [1, 3, 3, 1], [1, 4, 6, 4, 1], [1, 5, 10, 10, 5, 1]]
Avec les notations de l'énoncé corrigé :
1 2 3 4 5 6 7 8 9 | |
On cherche à déterminer les valeurs du triangle de Pascal. Dans ce tableau de forme
triangulaire, chaque ligne commence et se termine par le nombre 1. Par ailleurs, la valeur
qui occupe une case située à l’intérieur du tableau s’obtient en ajoutant les valeurs des
deux cases situées juste au-dessus, comme l’indique la figure suivante :
{: .centrer width=60%}
Compléter la fonction `pascal` ci-après. Elle doit renvoyer une liste correspondant au
triangle de Pascal de la ligne `1` à la ligne `n` où `n` est un nombre entier supérieur ou égal à
`2` (le tableau sera contenu dans la variable `C`). La variable `Ck` doit, quant à elle, contenir,
à l’étape numéro `k`, la `k`-ième ligne du tableau.
```python linenums='1'
def pascal(n):
C= [[1]]
for k in range(1,...):
Ck = [...]
for i in range(1,k):
Ck.append(C[...][i-1]+C[...][...] )
Ck.append(...)
C.append(Ck)
return C
Pour n = 4, voici ce qu'on devra obtenir :
>>> pascal(4)
[[1], [1, 1], [1, 2, 1], [1, 3, 3, 1], [1, 4, 6, 4, 1]]
n = 5, voici ce qu'on devra obtenir :
>>> pascal(5)
[[1], [1, 1], [1, 2, 1], [1, 3, 3, 1], [1, 4, 6, 4, 1], [1, 5, 10, 10, 5, 1]]
Sujet 03 ⚓︎
Exercice 03.1
Le codage par différence (delta encoding en anglais) permet de compresser un tableau de données en indiquant pour chaque donnée, sa différence avec la précédente (plutôt que la donnée elle-même). On se retrouve alors avec un tableau de données assez petites nécessitant moins de place en mémoire. Cette méthode se révèle efficace lorsque les valeurs consécutives sont proches.
Programmer la fonction delta qui prend en paramètre un tableau non vide de nombres entiers
et qui renvoie un tableau contenant les valeurs entières compressées à l’aide cette technique.
Exemples :
>>> delta([1000, 800, 802, 1000, 1003])
[1000, -200, 2, 198, 3]
>>> delta([42])
42
Exercice délicat nous révèle G.Connan :
- une coquille dans le résultat du deuxième exemple : la réponse est
[42]et non42. - il s'agit de créer une liste à partir des éléments de la liste initiale ; si on ne s'y prend pas comme il faut, les modifications en place par exemple vont conduire à des désastres.
Source : commentaires à propos du 03.1
Le codage par différence (delta encoding en anglais) permet de compresser un tableau de données en indiquant pour chaque donnée, sa différence avec la précédente (plutôt que la donnée elle-même). On se retrouve alors avec un tableau de données assez petites nécessitant moins de place en mémoire. Cette méthode se révèle efficace lorsque les valeurs consécutives sont proches.
Programmer la fonction delta qui prend en paramètre un tableau non vide de nombres entiers
et qui renvoie un tableau contenant les valeurs entières compressées à l’aide de cette technique.
Exemples :
>>> delta([1000, 800, 802, 1000, 1003])
[1000, -200, 2, 198, 3]
>>> delta([42])
[42]
La version attendue est probablement quelque chose comme :
def delta(tab):
assert len(tab) > 0, "liste vide !"
tab_compresse = [tab[0]]
for i in range(1, len(tab)):
tab_compresse.append(tab[i] - tab[i-1])
return tab_compresse
On peut essayer une version en compréhension :
def delta(tab):
assert len(tab) > 0, "liste vide !"
return [tab[0]] + [tab[i] - tab[i-1] for i in range(1, len(tab))]
La même mais en utilisant l'opéateur ternaire pour éviter la concaténation de listes (hors-programme) :
def delta(tab):
assert len(tab) > 0, "liste vide !"
return [tab[i] - tab[i-1] if i != 0 else tab[0] for i in range(len(tab))]
Le codage par différence (_delta encoding_ en anglais) permet de compresser un tableau de
données en indiquant pour chaque donnée, sa différence avec la précédente (plutôt que la
donnée elle-même). On se retrouve alors avec un tableau de données assez petites nécessitant
moins de place en mémoire. Cette méthode se révèle efficace lorsque les valeurs consécutives
sont proches.
Programmer la fonction `delta` qui prend en paramètre un tableau non vide de nombres entiers
et qui renvoie un tableau contenant les valeurs entières compressées à l’aide cette technique.
Exemples :
```python
>>> delta([1000, 800, 802, 1000, 1003])
[1000, -200, 2, 198, 3]
>>> delta([42])
42
```
Exercice 03.2
Une expression arithmétique ne comportant que les quatre opérations +, −,×,÷ peut être représentée sous forme d’arbre binaire. Les nœuds internes sont des opérateurs et les feuilles sont des nombres. Dans un tel arbre, la disposition des nœuds joue le rôle des parenthèses que nous connaissons bien.
En parcourant en profondeur infixe l’arbre binaire ci-dessus, on retrouve l’expression notée habituellement :
La classe Noeud ci-après permet d’implémenter une structure
d’arbre binaire.
Compléter la fonction récursive expression_infixe qui prend
en paramètre un objet de la classe Noeud et qui renvoie
l’expression arithmétique représentée par l’arbre binaire passé
en paramètre, sous forme d’une chaîne de caractères contenant
des parenthèses.
Résultat attendu avec l’arbre ci-dessus :
>>> e = Noeud(Noeud(Noeud(None, 3, None), '*', Noeud(Noeud(None, 8, None),
'+', Noeud(None, 7, None))), '-', Noeud(Noeud(None, 2, None), '+',
Noeud(None, 1, None)))
>>> expression_infixe(e)
'((3*(8+7))-(2+1))'
class Noeud:
def __init__(self, g, v, d):
self.gauche = g
self.valeur = v
self.droit = d
def __str__(self):
return str(self.valeur)
def est_une_feuille(self):
'''Renvoie True si et seulement si le noeud est une feuille'''
return self.gauche is None and self.droit is None
def expression_infixe(e):
s = ...
if e.gauche is not None:
s = s + expression_infixe(...)
s = s + ...
if ... is not None:
s = s + ...
if ...:
return s
return '('+ s +')'
Le principal grief à faire à ce sujet c'est que le code à compléter est inutilement compliqué puisque l'énoncé nous dit qu'on ne traite que des quatre opérations binaires, le noeuds sont soient des feuilles avec 0 descendants (les valeurs sont alors les nombres), soient des noeuds avec deux fils, la valeur étant alors le caractère de l'opération.
Une expression arithmétique ne comportant que les quatre opérations +, −,×,÷ peut être représentée sous forme d’arbre binaire. Les nœuds internes sont des opérateurs et les feuilles sont des nombres. Dans un tel arbre, la disposition des nœuds joue le rôle des parenthèses que nous connaissons bien.
En réalisant un parcourt en profondeur infixé de l’arbre binaire ci-dessus, on retrouve l’expression notée habituellement :
La classe Noeud ci-après permet d’implémenter une structure
d’arbre binaire.
Compléter la fonction récursive expression_infixe qui prend
en paramètre un objet de la classe Noeud et qui renvoie
l’expression arithmétique représentée par l’arbre binaire passé
en paramètre, sous forme d’une chaîne de caractères complètement parenthésée (ie avec toutes les parenthèses).
Résultat attendu avec l’arbre ci-dessus :
>>> somme_1 = Noeud(Noeud(None, 8, None), '+', Noeud(None, 7, None))
>>> somme_2 = Noeud(Noeud(None, 2, None), '+', Noeud(None, 1, None))
>>> produit_1 = Noeud(Noeud(None, 3, None), '*', somme_1)
>>> expression = Noeud(produit_1, '-', somme_2)
>>> representation_infixe(expression)
'((3*(8+7))-(2+1))'
class Noeud:
def __init__(self, g, v, d):
self.gauche = g
self.valeur = v
self.droit = d
def __str__(self):
return str(self.valeur)
def est_une_feuille(self):
'''Renvoie True si et seulement si le noeud est une feuille'''
return self.gauche is None and self.droit is None
def expression_infixe(e):
if ...:
return str(e)
else:
return '(' + expression_infixe(...) + ...
def expression_infixe(e):
if e.est_une_feuille():
return str(e)
else:
return '(' + expression_infixe(e.gauche) + e.valeur + expression_infixe(e.droit) + ')'
La version avec une f-string est nettement mieux :
def expression_infixe(e):
if e.est_une_feuille():
return str(e)
else:
return f'({expression_infixe(e.gauche)}{e.valeur}{expression_infixe(e.droit)})'
Une expression arithmétique ne comportant que les quatre opérations +, −,×,÷ peut être
représentée sous forme d’arbre binaire. Les nœuds internes sont des opérateurs et les feuilles
sont des nombres. Dans un tel arbre, la disposition des nœuds joue le rôle des parenthèses que
nous connaissons bien.
{: .center width=30%}
En parcourant en profondeur infixe l’arbre binaire ci-dessus, on
retrouve l’expression notée habituellement :
$$3 \times (8 + 7) − (2 + 1)$$
La classe `Noeud` ci-après permet d’implémenter une structure
d’arbre binaire.
Compléter la fonction récursive `expression_infixe` qui prend
en paramètre un objet de la classe `Noeud` et qui renvoie
l’expression arithmétique représentée par l’arbre binaire passé
en paramètre, sous forme d’une chaîne de caractères contenant
des parenthèses.
Résultat attendu avec l’arbre ci-dessus :
```python
>>> e = Noeud(Noeud(Noeud(None, 3, None), '*', Noeud(Noeud(None, 8, None),
'+', Noeud(None, 7, None))), '-', Noeud(Noeud(None, 2, None), '+',
Noeud(None, 1, None)))
>>> expression_infixe(e)
'((3*(8+7))-(2+1))'
class Noeud:
def __init__(self, g, v, d):
self.gauche = g
self.valeur = v
self.droit = d
def __str__(self):
return str(self.valeur)
def est_une_feuille(self):
'''Renvoie True si et seulement si le noeud est une feuille'''
return self.gauche is None and self.droit is None
def expression_infixe(e):
s = ...
if e.gauche is not None:
s = s + expression_infixe(...)
s = s + ...
if ... is not None:
s = s + ...
if ...:
return s
return '('+ s +')'
Sujet 04 ⚓︎
Exercice 04.1
Écrire une fonction recherche qui prend en paramètre un tableau de nombres entiers
tab, et qui renvoie la liste (éventuellement vide) des couples d'entiers consécutifs
successifs qu'il peut y avoir dans tab.
Exemples :
>>> recherche([1, 4, 3, 5])
[]
>>> recherche([1, 4, 5, 3])
[(4, 5)]
>>> recherche([7, 1, 2, 5, 3, 4])
[(1, 2), (3, 4)]
>>> recherche([5, 1, 2, 3, 8, -5, -4, 7])
[(1, 2), (2, 3), (-5, -4)]
G. Connan semble décontenancé par cet énoncé, dès le nom de la fonction, qui cache ce qu'elle réalise vraiment :
Tiens, encore une recherche...Sauf que c'est une toute autre recherche que dans le sujet 1. On peut donc l'appeler recherche_consecutifs peut-être. Ensuite la liste en paramètre est désignée comme étant un tableau et la liste renvoyée est désignée comme étant une liste. Comme M. Preskovic, je suis dans toutes mes confuses avec un tel énoncé.
Source : commentaires à propos du 04.1
Écrire une fonction consecutifs_successifs qui prend en paramètre un tableau de nombres entiers
tab, et qui renvoie la liste (éventuellement vide) des couples d'entiers consécutifs
successifs qu'il peut y avoir dans tab.
Exemples :
>>> consecutifs_successifs([1, 4, 3, 5])
[]
>>> consecutifs_successifs([1, 4, 5, 3])
[(4, 5)]
>>> consecutifs_successifs([7, 1, 2, 5, 3, 4])
[(1, 2), (3, 4)]
>>> consecutifs_successifs([5, 1, 2, 3, 8, -5, -4, 7])
[(1, 2), (2, 3), (-5, -4)]
G. Connan nous propose la fonction probablement attendue :
1 2 3 4 5 6 | |
Peut-être certain-es feront une version en compréhension :
def consecutifs_successifs(tab):
return [(tab[i], tab[i+1]) for i in range(len(tab) - 1) if tab[i+1] - tab[i] == 1]
Écrire une fonction `recherche` qui prend en paramètre un tableau de nombres entiers
`tab`, et qui renvoie la liste (éventuellement vide) des couples d'entiers consécutifs
successifs qu'il peut y avoir dans `tab`.
Exemples :
```python
>>> recherche([1, 4, 3, 5])
[]
>>> recherche([1, 4, 5, 3])
[(4, 5)]
>>> recherche([7, 1, 2, 5, 3, 4])
[(1, 2), (3, 4)]
>>> recherche([5, 1, 2, 3, 8, -5, -4, 7])
[(1, 2), (2, 3), (-5, -4)]
```
Exercice 04.2
Soit une image binaire représentée dans un tableau à 2 dimensions. Les éléments
M[i][j], appelés pixels, sont égaux soit à 0 soit à 1.
Une composante d’une image est un sous-ensemble de l’image constitué uniquement de
1 et de 0 qui sont côte à côte, soit horizontalement soit verticalement.
Par exemple, les composantes de
sont
On souhaite, à partir d’un pixel égal à 1 dans une image M, donner la valeur val à tous
les pixels de la composante à laquelle appartient ce pixel.
La fonction propager prend pour paramètre une image M, deux entiers i et j et une
valeur entière val. Elle met à la valeur val tous les pixels de la composante du pixel
M[i][j] s’il vaut 1 et ne fait rien s’il vaut 0.
Par exemple, propager(M,2,1,3) donne
Compléter le code récursif de la fonction propager donné ci-dessous :
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 | |
>>> M = [[0,0,1,0],[0,1,0,1],[1,1,1,0],[0,1,1,0]]
>>> propager(M,2,1,3)
>>> M
[[0, 0, 1, 0], [0, 3, 0, 1], [3, 3, 3, 0], [0, 3, 3, 0]]
G. Connan est assez dur avec cet exercice : commentaires à propos du 04.2.
Je suis plus nuancé. J'imagine que l'intérêt est essentiellement de manipuler la récursivité sur un exemple non trivial, et que cette propagation sur un bloc peut se retrouver dans certaines opérations sur les images.
Par contre ce que je changerai dans l'énoncé c'est le code de la fonction :
- ajouter un peu plus de trous progressivement tout au long des 4 appels récursifs qui se ressemblent énormément
- revoir le début : pourquoi ce test avec un
return Nonequi ne rime à rien - on peut aussi retirer tout ce paranthésage qui alourdit le texte
Soit une image binaire représentée dans un tableau à 2 dimensions. Les éléments
M[i][j], appelés pixels, sont égaux soit à 0 soit à 1.
Une composante d’une image est un sous-ensemble de l’image constitué uniquement de
1 ou constitué uniquement de 0 qui sont côte à côte, soit horizontalement soit verticalement.
Par exemple, les composantes de
sont
On souhaite, à partir d’un pixel égal à 1 dans une image M, donner la valeur val à tous
les pixels de la composante à laquelle appartient ce pixel.
La fonction propager prend pour paramètre une image M, deux entiers i et j et une
valeur entière val. Elle met à la valeur de val tous les pixels de la composante du pixel
M[i][j] s’il vaut 1 et ne fait rien s’il vaut 0.
Par exemple, propager(M,2,1,3) donne
Compléter le code récursif de la fonction propager donné ci-dessous :
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 | |
Exemple :
>>> M = [[0, 0, 1, 0], [0, 1, 0, 1], [1, 1, 1, 0], [0, 1, 1, 0]]
>>> propager(M, 2, 1, 3)
>>> M
[[0, 0, 1, 0], [0, 3, 0, 1], [3, 3, 3, 0], [0, 3, 3, 0]]
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 | |
Soit une image binaire représentée dans un tableau à 2 dimensions. Les éléments
`M[i][j]`, appelés pixels, sont égaux soit à `0` soit à `1`.
Une composante d’une image est un sous-ensemble de l’image constitué uniquement de
`1` et de `0` qui sont côte à côte, soit horizontalement soit verticalement.
Par exemple, les composantes de
{: .centrer width=30%}
sont
{: .centrer width=30%}
On souhaite, à partir d’un pixel égal à `1` dans une image `M`, donner la valeur `val` à tous
les pixels de la composante à laquelle appartient ce pixel.
La fonction `propager` prend pour paramètre une image `M`, deux entiers `i` et `j` et une
valeur entière `val`. Elle met à la valeur `val` tous les pixels de la composante du pixel
`M[i][j]` s’il vaut `1` et ne fait rien s’il vaut `0`.
Par exemple, `propager(M,2,1,3)` donne
{: .centrer width=30%}
Compléter le code récursif de la fonction `propager` donné ci-dessous :
```python linenums='1'
def propager(M, i, j, val):
if M[i][j]== ...:
return None
M[i][j] = val
# l'élément en haut fait partie de la composante
if ((i-1) >= 0 and M[i-1][j] == ...):
propager(M, i-1, j, val)
# l'élément en bas fait partie de la composante
if ((...) < len(M) and M[i+1][j] == 1):
propager(M, ..., j, val)
# l'élément à gauche fait partie de la composante
if ((...) >= 0 and M[i][j-1] == 1):
propager(M, i, ..., val)
# l'élément à droite fait partie de la composante
if ((...) < len(M) and M[i][j+1] == 1):
propager(M, i, ..., val)
>>> M = [[0,0,1,0],[0,1,0,1],[1,1,1,0],[0,1,1,0]]
>>> propager(M,2,1,3)
>>> M
[[0, 0, 1, 0], [0, 3, 0, 1], [3, 3, 3, 0], [0, 3, 3, 0]]
Sujet 05 ⚓︎
Exercice 05.1
Écrire une fonction RechercheMinMax qui prend en paramètre un tableau de nombres
non triés tab, et qui renvoie la plus petite et la plus grande valeur du tableau sous la
forme d’un dictionnaire à deux clés ‘min’ et ‘max’. Les tableaux seront représentés sous
forme de liste Python.
Exemples :
>>> tableau = [0, 1, 4, 2, -2, 9, 3, 1, 7, 1]
>>> resultat = rechercheMinMax(tableau)
>>> resultat
{'min': -2, 'max': 9}
>>> tableau = []
>>> resultat = rechercheMinMax(tableau)
>>> resultat
{'min': None, 'max': None}
G. Connan rappelle qu'il serait bon de choisir le nom des fonctions judicieusement en respectant le PEP8. Jeter un oeil à son commentaire à propos du 05.1.
En boutade, G. Connan fait évidemment référence à l'algorithme du minmax)
F. Nativel attire l'attention sur le fait que dans l'énoncé original la fonction s'appelle RechercheMinMax avec un R majuscule mais lors des appels dans les exemples on a rechercheMinMax.
On pourrait alléger la syntaxe des tests et ajouter un troisième exemple où les deux valeurs recherchées sont confondues.
Écrire une fonction mini_et_maxi qui prend en paramètre un tableau de nombres
non triés tab, et qui renvoie la plus petite et la plus grande valeur du tableau sous la
forme d’un dictionnaire à deux clés 'min' et 'max'. Les tableaux seront représentés sous
forme de liste Python. Dans le cas d'un tableau vide on utilisera l'objet None de Python comme valeur associée aux clés.
Exemples :
>>> mini_et_maxi([0, 1, 4, 2, -2, 9, 3, 1, 7, 1])
{'min': -2, 'max': 9}
>>> mini_et_maxi([42])
{'min': 42, 'max': 42}
>>> mini_et_maxi([])
{'min': None, 'max': None}
G. Connan propose la solution probablement attendue, en nous rappelant de faire attention à l'initialisation avec None dans le cas du tableau vide.
1 2 3 4 5 6 7 8 9 10 | |
On pourrait ne pas aimer le tab[1:] :
1 2 3 4 5 6 7 8 9 10 11 | |
Cela alourdit le code... alors qu'en fait on pourrait commencer au premier élément :
1 2 3 4 5 6 7 8 9 10 | |
Le sujet ne précisant pas de ne pas utiliser les fonctions prédéfinies du langage ;-) :
1 2 3 4 | |
L'opérateur ternaire ? ;-) (est-il utile de dire qu'on est totalement hors-programme ?)
1 2 3 | |
Écrire une fonction `RechercheMinMax` qui prend en paramètre un tableau de nombres
non triés `tab`, et qui renvoie la plus petite et la plus grande valeur du tableau sous la
forme d’un dictionnaire à deux clés ‘min’ et ‘max’. Les tableaux seront représentés sous
forme de liste Python.
Exemples :
```python
>>> tableau = [0, 1, 4, 2, -2, 9, 3, 1, 7, 1]
>>> resultat = rechercheMinMax(tableau)
>>> resultat
{'min': -2, 'max': 9}
>>> tableau = []
>>> resultat = rechercheMinMax(tableau)
>>> resultat
{'min': None, 'max': None}
```
Exercice 05.2
On dispose d’un programme permettant de créer un objet de type PaquetDeCarte,
selon les éléments indiqués dans le code ci-dessous.
Compléter ce code aux endroits indiqués par #A compléter, puis ajouter des
assertions dans l’initialiseur de Carte, ainsi que dans la méthode getCarteAt().
1 2 3 4 5 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 | |
>>> unPaquet = PaquetDeCarte()
>>> unPaquet.remplir()
>>> uneCarte = unPaquet.getCarteAt(20)
>>> print(uneCarte.getNom() + " de " + uneCarte.getCouleur())
6 de coeur
G. Connan pointe du doigt toutes les erreurs du premier sujet utilisant la POO : commentaires à propos du 05.2. Cet exercice est à reprendre en profondeur.
L'exemple donné ne peut être reproduit quelque soit la façon (simple) dont on constitue le paquet. La réponse la plus proche en rangeant par couleur puis par valeur est 8 de pique.
Dans la proposition d'énoncé modifié :
- on corrigera les erreurs PEP8 de nommage et d'espaces,
- on utilisera des constantes pour les noms de valeurs et ceux des couleurs, en insérant dans ces listes un premier élément bidon pour tenir compte des valeurs et couleurs qui commencent à 1,
- on essaiera de rajouter une question pour que l'élève complète la création d'un attribut d'instance, histoire de faire un petit peu de POO.
- on corrigera le test faux et on en ajoutera
On dispose d’un programme permettant de créer un objet de type PaquetDeCarte,
selon les éléments indiqués dans le code ci-dessous.
Compléter ce code aux endroits indiqués par # A compléter, puis vérifier que vous obtenez les bonnes sorties sur les tests proposés.
1 2 3 4 5 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 | |
Exemple :
>>> jeu = PaquetDeCarte()
>>> jeu.remplir()
>>> carte = jeu.get_carte_at(20)
>>> print(carte.get_nom() + " de " + carte.get_couleur())
8 de coeur
>>> autre = jeu.get_carte_at(0)
>>> print(autre.get_nom() + " de " + autre.get_couleur())
As de pique
>>> une_derniere = jeu.get_carte_at(51)
>>> print(une_derniere.get_nom() + " de " + une_derniere.get_couleur())
Roi de trefle
VALEURS = ['', 'As', '2', '3', '4', '5', '6', '7', '8', '9', '10', 'Valet', 'Dame', 'Roi']
COULEURS = ['', 'pique', 'coeur', 'carreau', 'trefle']
class Carte:
"""Initialise couleur (de 1 à 4), et valeur (de 1 à 13)"""
def __init__(self, couleur, valeur):
self.couleur = couleur
self.valeur = valeur
def get_nom(self):
"""Renvoie le nom de la Carte As, 2, ... 10, Valet, Dame, Roi"""
return VALEURS[self.valeur]
def get_couleur(self):
"""Renvoie la couleur de la Carte (parmi pique, coeur, carreau, trefle)"""
return COULEURS[self.couleur]
class PaquetDeCarte:
"""Initialise un paquet de cartes, avec un attribut contenu, de type list, vide"""
def __init__(self):
self.contenu = []
def remplir(self):
"""Remplit le paquet de cartes : en parcourant les couleurs puis les valeurs"""
self.contenu = [Carte(couleur, valeur) for couleur in range(1, 5) for valeur in range(1, 14)]
def get_carte_at(self, pos):
"""Renvoie la Carte qui se trouve à la position donnée"""
if 0 <= pos < 52:
return self.contenu[pos]
On dispose d’un programme permettant de créer un objet de type `PaquetDeCarte`,
selon les éléments indiqués dans le code ci-dessous.
Compléter ce code aux endroits indiqués par `#A compléter`, puis ajouter des
assertions dans l’initialiseur de `Carte`, ainsi que dans la méthode `getCarteAt()`.
```python linenums='1'
class Carte:
"""Initialise Couleur (entre 1 à 4), et Valeur (entre 1 à 13)"""
def __init__(self, c, v):
self.Couleur = c
self.Valeur = v
"""Renvoie le nom de la Carte As, 2, ... 10, Valet, Dame, Roi"""
def getNom(self):
if ( self.Valeur > 1 and self.Valeur < 11):
return str( self.Valeur)
elif self.Valeur == 11:
return "Valet"
elif self.Valeur == 12:
return "Dame"
elif self.Valeur == 13:
return "Roi"
else:
return "As"
"""Renvoie la couleur de la Carte (parmi pique, coeur, carreau, trefle"""
def getCouleur(self):
return ['pique', 'coeur', 'carreau', 'trefle'][self.Couleur - 1]
class PaquetDeCarte:
def __init__(self):
self.contenu = []
"""Remplit le paquet de cartes"""
def remplir(self):
#A compléter
"""Renvoie la Carte qui se trouve à la position donnée"""
def getCarteAt(self, pos):
#A compléter
>>> unPaquet = PaquetDeCarte()
>>> unPaquet.remplir()
>>> uneCarte = unPaquet.getCarteAt(20)
>>> print(uneCarte.getNom() + " de " + uneCarte.getCouleur())
6 de coeur
Sujet 06 ⚓︎
Difficile de sauver ce sujet. L'exercice 2 pourrait être intéressant (surtout si on le coupe en deux fonctions distinctes) mais il s'agit quand même d'une recherche textuelle, déclarée hors-programme.
Exercice 06.1
Écrire une fonction maxi qui prend en paramètre une liste tab de nombres entiers et renvoie un couple donnant le plus grand élément de cette liste, ainsi que l’indice de la première apparition de ce maximum dans la liste.
Exemple :
>>> maxi([1,5,6,9,1,2,3,7,9,8])
(9,3)
F. Chambon nous livre ses commentaires à propos du 06.1 :
- mauvais nom de fonctions
- le cas de la liste vide n'est pas évoqué
- problème de PEP8 dans l'exemple
Il s'agit du même exercice que le 16.1. On y appliquera donc les mêmes modifications.
Écrire une fonction valeur_et_indice_max qui prend en paramètre un tableau tab non vide de nombres entiers et renvoie un couple donnant le plus grand élément de cette liste, ainsi que l’indice de la première apparition de ce maximum dans la liste.
Exemples :
>>> valeur_et_indice_max([1, 5, 6, 9, 1, 2, 3, 7, 9, 8])
(9, 3)
>>> valeur_et_indice_max([1, 1, 1, 4, 4])
(4, 3)
>>> valeur_et_indice_max([10])
(10, 0)
1 2 3 4 5 6 7 8 | |
Comme aucune consigne n'existe concernant les fonctions prédéfinies...
1 2 3 | |
Une version avec enumerate (hors-programme) :
1 2 3 4 5 6 7 8 | |
Écrire une fonction `maxi` qui prend en paramètre une liste `tab` de nombres entiers et renvoie un couple donnant le plus grand élément de cette liste, ainsi que l’indice de la première apparition de ce maximum dans la liste.
Exemple :
```python
>>> maxi([1,5,6,9,1,2,3,7,9,8])
(9,3)
```
Exercice 06.2
La fonction recherche prend en paramètres deux chaines de caractères gene et
seq_adn et renvoie True si on retrouve gene dans seq_adn et False sinon.
Compléter le code Python ci-dessous pour qu’il implémente la fonction recherche.
1 2 3 4 5 6 7 8 9 10 11 12 13 | |
Exemples :
>>> recherche("AATC", "GTACAAATCTTGCC")
True
>>> recherche("AGTC", "GTACAAATCTTGCC")
False
F. Chambon trouve le sujet hors-programme (recherche textuelle) et la solution à compléter proposée inutilement compliquée. Il est vrai que la double boucle while n'est pas très avenante.
Il milite aussi pour des noms différents pour les variables et la fonction.
On pourrait essayer de simplifier la fonction principale en la coupant en deux.
Le fonction coincide_a_partir_de prend en paramètres :
- une première chaîne de caractères
chaine - un indice
positionqui représente une position dans la chaîne - une deuxième chaîne
extrait
et qui renvoie True si à partir de la position position on retrouve la chaîne extrait dans chaine.
>>> coincide_a_partir_de("ananas", 0, "an")
True
>>> coincide_a_partir_de("ananas", 2, "an")
True
>>> coincide_a_partir_de("ananas", 4, "an")
False
>>> coincide_a_partir_de("GTACAAATCTTGCC", 5, "AATC")
True
La fonction est_inclus prend en paramètres deux chaines de caractères gene et
brin_adn et renvoie True si on retrouve gene dans brin_adn et False sinon.
L'implémentation de la fonction est_inclus ci-dessous utilise la fonction coincide_a_partir_de.
Compléter les deux fonctions et vérifier avec les exemples proposés.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 | |
Exemples :
>>> est_inclus("AATC", "GTACAAATCTTGCC")
True
>>> est_inclus("AGTC", "GTACAAATCTTGCC")
False
Comme la version originale est complètement différente, voici la correction de cette version :
1 2 3 4 5 6 7 8 9 10 11 12 13 | |
Et la version modifiée :
def coincide_a_partir_de(chaine, position, extrait):
if len(extrait) > len(chaine) - position:
return False
for i in range(len(extrait)):
if chaine[position + i] != extrait[i]:
return False
return True
def est_inclus(gene, brin_adn):
n = len(brin_adn)
g = len(gene)
for i in range(n - g + 1):
if coincide_a_partir_de(brin_adn, i, gene):
return True
return False
La fonction `recherche` prend en paramètres deux chaines de caractères `gene` et
`seq_adn` et renvoie `True` si on retrouve `gene` dans `seq_adn` et `False` sinon.
Compléter le code Python ci-dessous pour qu’il implémente la fonction `recherche`.
```python linenums='1'
def recherche(gene, seq_adn):
n = len(seq_adn)
g = len(gene)
i = ...
trouve = False
while i < ... and trouve == ... :
j = 0
while j < g and gene[j] == seq_adn[i+j]:
...
if j == g:
trouve = True
...
return trouve
Exemples :
>>> recherche("AATC", "GTACAAATCTTGCC")
True
>>> recherche("AGTC", "GTACAAATCTTGCC")
False
Sujet 07 ⚓︎
L'exercice 1 me semble trop pour un exercice 1. Il est d'ailleurs proposé sous une autre forme (on construit une chaîne de caractères au lieu d'une liste) dans l'exercice 15.2. L'exercice 2 est un tri à bulles, hors programme mais qui, si on y ajoute des explications claires pourrait aller.
Exercice 07.1
Écrire une fonction conv_bin qui prend en paramètre un entier positif n et renvoie un
couple (b,bit) où :
best une liste d'entiers correspondant à la représentation binaire den;bitcorrespond aux nombre de bits qui constituentb.
Exemple :
>>> conv_bin(9)
([1,0,0,1],4)
Aide :
- l'opérateur
//donne le quotient de la division euclidienne :5//2donne2; - l'opérateur
%donne le reste de la division euclidienne :5%2donne1; appendest une méthode qui ajoute un élément à une liste existante : SoitT=[5,2,4], alorsT.append(10)ajoute10à la listeT. Ainsi,Tdevient[5,2,4,10].reverseest une méthode qui renverse les éléments d'une liste. SoitT=[5,2,4,10]. AprèsT.reverse(), la liste devient[10,4,2,5].
On remarquera qu’on récupère la représentation binaire d’un entier n en partant de la gauche en appliquant successivement les instructions :
b = n%2
n = n//2
répétées autant que nécessaire.
Beaucoup à reprendre sans cet exercice d'après F. Chambon :
- mauvais nom de fonction et très mauvais noms de variable
- fautes d’orthographe et imprécisions et pourtant sujet trop long
- contournements (contorsionnements) pour éviter d’écrire taille et bits l’un après l’autre
- renvoyer la longueur de la liste n’a aucun intérêt en Python ; on n’est pas en C
- exemple très mal choisi, c’est un palindrome en binaire
Source : commentaires à propos du 07.1.
Les modifications sont directement inspirées de https://ens-fr.gitlab.io/nsi-pratique/ex1/07/sujet/
A noter : l'exercice est très similaire au 15.2. Il est étonnant soit proposé en exercice 1 et l'autre en 2. Une harmonisation s'impose.
Écrire une fonction conversion_binaire qui prend en paramètre un entier positif n et renvoie une liste bits d'entiers égaux à 0 ou 1, la représentation en binaire de n.
Exemple :
>>> conversion_binaire(0)
[0]
>>> conversion_binaire(77)
[1, 0, 0, 1, 1, 0, 1]
Aide :
- l'opérateur
//donne le quotient de la division euclidienne :5 // 2donne2; - l'opérateur
%donne le reste de la division euclidienne :5 % 2donne1; appendest une méthode qui ajoute un élément à une liste existante : SoitT = [5, 2, 4], alorsT.append(10)ajoute10à la listeT. Ainsi,Tdevient[5, 2, 4, 10].reverseest une méthode qui renverse les éléments d'une liste. SoitT = [5, 2, 4, 10]. AprèsT.reverse(), la liste devient[10, 4, 2, 5].
On remarquera qu’on récupère la représentation binaire d’un entier n en partant de la gauche en appliquant successivement les instructions :
b = n % 2
n = n // 2
répétées autant que nécessaire.
1 2 3 4 5 6 7 8 | |
Écrire une fonction `conv_bin` qui prend en paramètre un entier positif `n` et renvoie un
couple (`b,bit)` où :
- `b` est une liste d'entiers correspondant à la représentation binaire de `n`;
- `bit` correspond aux nombre de bits qui constituent `b`.
Exemple :
```python
>>> conv_bin(9)
([1,0,0,1],4)
```
Aide :
- l'opérateur `//` donne le quotient de la division euclidienne : `5//2` donne `2` ;
- l'opérateur `%` donne le reste de la division euclidienne :` 5%2` donne `1` ;
- `append` est une méthode qui ajoute un élément à une liste existante :
Soit `T=[5,2,4]`, alors `T.append(10)` ajoute `10` à la liste `T`. Ainsi, `T` devient
`[5,2,4,10]`.
- `reverse` est une méthode qui renverse les éléments d'une liste.
Soit `T=[5,2,4,10]`. Après `T.reverse()`, la liste devient `[10,4,2,5]`.
On remarquera qu’on récupère la représentation binaire d’un entier `n` en partant de la gauche en appliquant successivement les instructions :
`b = n%2`
`n = n//2`
répétées autant que nécessaire.
Exercice 07.2
La fonction tri_bulles prend en paramètre une liste T d’entiers non triés et renvoie la liste triée par ordre croissant.
Compléter le code Python ci-dessous qui implémente la fonction tri_bulles.
1 2 3 4 5 6 7 8 9 | |
F. Chambon rappelle que le tri à bulles, thème de cet exerice 2 est hors-programme. Ce n'est pas forcément génant en exercice 2 puisqu'une partie du code est fournie. Il faut néanmoins une explication de l'algorithme qu'implémente ce code.
Source commentaires à propos du 07.2
Dans l'énoncé modifié, une tentative d'explication courte... pas sûr que ça aide un élève. Autre modification : lorsqu'on a besoin d'échanger deux valeurs dans un tableau, faire une fonction echange à trois paramètres et laisser le candidat coder son échange (soit avec une affectation multiple soit en utilisant une 3e variable comme certains le font).
La fonction tri_bulles prend en paramètre un tableau tab d’entiers et effectue un tri en place du tableau par ordre croissant de ses éléments suivant le principe suivant :
- on parcourt le tableau de droite à gauche (ie du dernier indice au premier) et on va pousser le plus grand élément à cette position courante :
- on parcourt le tableau de gauche à droite jusqu'à cette position et on compare l'élément courant avec son suivant ; on les échange s'ils sont mal ordonnés
Compléter le code Python ci-dessous qui implémente la fonction tri_bulles (et une fonction echange pour échanger deux valeurs d'un tableau).
1 2 3 4 5 6 7 8 9 | |
Exemples :
>>> tableau = [5, 3, 6, 1, 4, 2]
>>> tri_bulles(tableau)
>>> tableau
[1, 2, 3, 4, 5, 6]
1 2 3 4 5 6 7 8 9 | |
La fonction `tri_bulles` prend en paramètre une liste `T` d’entiers non triés et renvoie la liste triée par ordre croissant.
Compléter le code Python ci-dessous qui implémente la fonction `tri_bulles`.
```python linenums='1'
def tri_bulles(T):
n = len(T)
for i in range(...,...,-1):
for j in range(i):
if T[j] > T[...]:
... = T[j]
T[j] = T[...]
T[j+1] = temp
return T
Sujet 08 ⚓︎
Exercice 08.1
Écrire une fonction recherche qui prend en paramètres elt un nombre entier et tab
un tableau de nombres entiers, et qui renvoie l’indice de la première occurrence de elt
dans tab si elt est dans tab et -1 sinon.
Exemples :
>>> recherche(1, [2, 3, 4])
-1
>>> recherche(1, [10, 12, 1, 56])
2
>>> recherche(50, [1, 50, 1])
1
>>> recherche(15, [8, 9, 10, 15])
3
D'accord avec F. Chambon renvoyer -1 pour une recherche d'indice lorsque l'élément est absent est une mauvaise idée en Python qui autorise les indices négatifs. Et oui même si certaines méthode de Python même le font. Mais d'autres avis existent sur la question : cet exercice pourra donc se faire sur le sujet initial (renvoie de -1 dansle cas d'une valeur absente) ou le modifié (renvoie de None).
Choisir un nom un peu plus spécifique que le recherche rencontré une bonne dizaine de fois.
L'énoncé modifié est directement inspiré de l'exercice 1 du sujet 8 proposé par F. Chambon.
Écrire une fonction indice qui prend en paramètres element un nombre entier, tableau un tableau de nombres entiers, et qui renvoie l'indice de la première occurrence de element dans tableau (et None s'il en est absent).
Exemples :
>>> indice(1, [10, 12, 1, 56])
2
>>> indice(1, [1, 50, 1])
0
>>> indice(15, [8, 9, 10, 15])
3
>>> indice(1, [2, 3, 4]) is None
True
1 2 3 4 5 | |
Écrire une fonction `recherche` qui prend en paramètres `elt` un nombre entier et `tab`
un tableau de nombres entiers, et qui renvoie l’indice de la première occurrence de `elt`
dans `tab` si `elt` est dans `tab` et `-1` sinon.
Exemples :
```python
>>> recherche(1, [2, 3, 4])
-1
>>> recherche(1, [10, 12, 1, 56])
2
>>> recherche(50, [1, 50, 1])
1
>>> recherche(15, [8, 9, 10, 15])
3
```
Exercice 08.2
On considère la fonction insere ci-dessous qui prend en argument un entier a et un
tableau tab d'entiers triés par ordre croissant. Cette fonction insère la valeur a dans le
tableau et renvoie le nouveau tableau. Les tableaux seront représentés sous la forme de
listes python.
1 2 3 4 5 6 7 8 9 | |
Compléter la fonction insere ci-dessus.
Exemples :
>>> insere(3,[1,2,4,5])
[1, 2, 3, 4, 5]
>>> insere(10,[1,2,7,12,14,25])
[1, 2, 7, 10, 12, 14, 25]
>>> insere(1,[2,3,4])
[1, 2, 3, 4]
F. Chambon rappelle cette distinction assez répandue en NSI : en structures de données, le tableau est statique (on ne retire ni on n'ajoute d'élément) quand la liste est dynamique. Et cela est indépendant de l'objet list de Python qui permet d'implémenter les deux structures.
Ainsi l'énoncé commet une erreur en disant qu'on insère dans un tableau.
Source : commentaires à propos du 08.2
Sur les exemples on peut remplacer le deuxième qui est similaire au premier par un exemple où l'insertion se fait en fin de liste. Et ajouter un exemple avec insertion dans la liste vide.
Et les traditionnelles légèretés avec le PEP8 et les espaces.
On considère la fonction insere ci-dessous qui prend en argument un entier a_inserer et une
liste liste d'entiers triés par ordre croissant. Cette fonction crée une nouvelle liste à partir de la liste liste en y insèrant la valeur a_inserer à la bonne position (la liste résultante reste triée). La fonction renvoie la nouvelle liste. Compléter la fonction insere :
1 2 3 4 5 6 7 8 9 | |
Exemples :
>>> insere(3, [1, 2, 4, 5])
[1, 2, 3, 4, 5]
>>> insere(10, [1, 2, 7])
[1, 2, 7, 10]
>>> insere(1, [2, 3, 4])
[1, 2, 3, 4]
>> insere(1, [])
[1]
1 2 3 4 5 6 7 8 9 | |
On considère la fonction `insere` ci-dessous qui prend en argument un entier `a` et un
tableau `tab` d'entiers triés par ordre croissant. Cette fonction insère la valeur `a` dans le
tableau et renvoie le nouveau tableau. Les tableaux seront représentés sous la forme de
listes python.
```python linenums='1'
def insere(a, tab):
l = list(tab) #l contient les mêmes éléments que tab
l.append(a)
i = ...
while a < ... and i >= ...:
l[i+1] = ...
l[i] = a
i = ...
return l
Compléter la fonction insere ci-dessus.
Exemples :
>>> insere(3,[1,2,4,5])
[1, 2, 3, 4, 5]
>>> insere(10,[1,2,7,12,14,25])
[1, 2, 7, 10, 12, 14, 25]
>>> insere(1,[2,3,4])
[1, 2, 3, 4]
Sujet 09 ⚓︎
Encore un sujet très orienté mathématiques. Avec dans l'exercice 1, une définition de suite récurrente à supprimer pour avoir une chance d'ếtre un sujet acceptable.
Exercice 09.1
Soit un nombre entier supérieur ou égal à 1 :
- s'il est pair, on le divise par 2 ;
- s’il est impair, on le multiplie par 3 et on ajoute 1.
Puis on recommence ces étapes avec le nombre entier obtenu, jusqu’à ce que l’on obtienne la valeur 1.
On définit ainsi la suite \((U_n)\) par :
- \(U_0=k\), où \(k\) est un entier choisi initialement;
- \(U_{n+1} = \dfrac{U_n}{2}\) si \(U_n\) est pair;
- \(U_{n+1} = 3 \times U_n + 1\) si \(U_n\) est impair.
On admet que, quel que soit l'entier k choisi au départ, la suite finit toujours sur la valeur 1.
Écrire une fonction calcul prenant en paramètres un entier n strictement positif et qui renvoie la liste des valeurs de la suite, en partant de n et jusqu'à atteindre 1.
Exemple :
>>> calcul(7)
[7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1]
F. Chambon relève quelques imprécisions dans la rédaction : commentaires à propos du 09.1.
Comme relevé dans d'autres sujets, les candidats n'ont pas forcément suivi une spécialité mathématiques et donc une suite récurrente avec un formalisme de mathématiques peut poser quelques difficultés.
Le on admet pour un problème ouvert de plus de 90 ans est un peu osé, on peut trouver une formulation plus neutre.
Soit un nombre entier \(n\) supérieur ou égal à 1 :
- si \(n\) est pair, on le divise par 2 ;
- si \(n\) est impair, on le multiplie par 3 et on ajoute 1.
Puis on recommence ces étapes avec le nombre entier obtenu, jusqu’à ce que l’on obtienne la valeur 1.
La suite des nombres ainsi obtenue se nomme suite de Syracuse de \(n\). Une conjecture dit que cette suite se termine toujours par 1.
Écrire une fonction syracuse prenant en paramètre un entier n strictement positif et qui renvoie la liste des valeurs de la suite, en partant de n et jusqu'à atteindre 1.
Exemple :
>>> syracuse(7)
[7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1]
>>> syracuse(1)
[1]
>>> syracuse(4)
[4, 2, 1]
def syracuse(n):
suite = []
while n > 1:
suite.append(n)
if n % 2 == 0:
n = n // 2
else:
n = 3 * n + 1
suite.append(1)
return suite
Soit un nombre entier supérieur ou égal à 1 :
- s'il est pair, on le divise par 2 ;
- s’il est impair, on le multiplie par 3 et on ajoute 1.
Puis on recommence ces étapes avec le nombre entier obtenu, jusqu’à ce que l’on
obtienne la valeur 1.
On définit ainsi la suite $(U_n)$ par :
- $U_0=k$, où $k$ est un entier choisi initialement;
- $U_{n+1} = \dfrac{U_n}{2}$ si $U_n$ est pair;
- $U_{n+1} = 3 \times U_n + 1$ si $U_n$ est impair.
**On admet que, quel que soit l'entier `k` choisi au départ, la suite finit toujours sur la valeur 1.**
Écrire une fonction ```calcul``` prenant en paramètres un entier ```n``` strictement positif et qui renvoie la liste des valeurs de la suite, en partant de ```n``` et jusqu'à atteindre 1.
Exemple :
```python
>>> calcul(7)
[7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1]
```
Exercice 09.2
On affecte à chaque lettre de l'alphabet un code selon le tableau ci-dessous :
| A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 |
Pour un mot donné, on détermine d’une part son code alphabétique concaténé, obtenu par la juxtaposition des codes de chacun de ses caractères, et d’autre part, son code additionné, qui est la somme des codes de chacun de ses caractères.
Par ailleurs, on dit que ce mot est « parfait » si le code additionné divise le code concaténé.
Exemples :
-
Pour le mot
"PAUL", le code concaténé est la chaîne'1612112', soit l’entier 1 612 112. Son code additionné est l’entier 50 car 16 + 1 + 21 + 12 = 50. 50 ne divise pas l’entier 1 612 112 ; par conséquent, le mot"PAUL"n’est pas parfait. -
Pour le mot
"ALAIN", le code concaténé est la chaîne'1121914', soit l’entier 1 121 914. Le code additionné est l’entier 37 car 1 + 12 + 1 + 9 + 14 = 37. 37 divise l’entier 1 121 914 ; par conséquent, le mot"ALAIN"est parfait.
Compléter la fonction est_parfait ci-dessous qui prend comme argument une chaîne
de caractères mot (en lettres majuscules) et qui renvoie le code alphabétique concaténé,
le code additionné de mot, ainsi qu’un booléen qui indique si mot est parfait ou pas.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 | |
Exemples :
>>> est_parfait("PAUL")
[50, 1612112, False]
>>> est_parfait("ALAIN")
[37, 1121914, True]
F. Chambon relève pas d'améliorations à apporter à l'énoncé vis-à-vis du PEP8 : espaces, noms des variables. Il pense également que le dictionnaire n'est pas nécessaire ici pour coder le décalage, un simple calcul à l'aide de la fonction ord suffit. Je ne sais pas trop pour cette remarque.
Un dictionnaire est plus souple d'utilisation que le calcul via ord. De plsu dans le sujet ça oblige à introduire une nouvelle fonction et donc l'expliquer. Je resterais donc sur le dictionnaire pour le code d'une lettre.
Enfin sa relecture se termine par un cri du coeur sur :
code_c = int(code_c)
Source : commentaires à propos du 09.2
D'un point de vue analyse de code il est certain que changer les types des objets référencés par une variable n'est pas génial. Mais en Python ça n'est pas vraiment génant et surtout, les pratiques de juges en ligne font qu'on a tendance à le faire souvent.
Par exemple quand on récupère des données de type str, str et int :
prenom, nom, age = input().split()
age = int(age)
On n'a pas envie pour chacune des variables entières devoir manipuler le double de variables. Dans le cadre d'une sujet de BAC toutefois, on peut faire attention et proposer :
code_concatene = int(str_code_concatene)
Enfin dernières remarques :
- une fonction retourne plusieurs valeurs grâce à un tuple ; pas besoin d'une liste
- le if est superflu.
On affecte à chaque lettre de l'alphabet un code selon le tableau ci-dessous :
| A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 |
Ce code sera donné par une constante :
CODE_LETTRE = {"A":1, "B":2, "C":3, "D":4, "E":5, "F":6, "G":7,
"H":8, "I":9, "J":10, "K":11, "L":12, "M":13,
"N":14, "O":15, "P":16, "Q":17, "R":18, "S":19,
"T":20, "U":21,"V":22, "W":23, "X":24, "Y":25, "Z":26}
Pour un mot donné, on détermine d’une part son code alphabétique concaténé, obtenu par la juxtaposition des codes de chacun de ses caractères, et d’autre part, son code additionné, qui est la somme des codes de chacun de ses caractères.
Par ailleurs, on dit que ce mot est « parfait » si le code additionné divise le code concaténé.
Exemples :
-
Pour le mot
"PAUL", le code concaténé est la chaîne'1612112', soit l’entier 1 612 112. Son code additionné est l’entier 50 car 16 + 1 + 21 + 12 = 50. 50 ne divise pas l’entier 1 612 112 ; par conséquent, le mot"PAUL"n’est pas parfait. -
Pour le mot
"ALAIN", le code concaténé est la chaîne'1121914', soit l’entier 1 121 914. Le code additionné est l’entier 37 car 1 + 12 + 1 + 9 + 14 = 37. 37 divise l’entier 1 121 914 ; par conséquent, le mot"ALAIN"est parfait.
Compléter la fonction est_parfait ci-dessous qui prend comme argument une chaîne
de caractères mot (en lettres majuscules) et qui renvoie le code alphabétique concaténé,
le code additionné de mot, ainsi qu’un booléen qui indique si mot est parfait ou pas.
1 2 3 4 5 6 7 8 9 10 11 12 | |
Exemples :
>>> est_parfait("PAUL")
(50, 1612112, False)
>>> est_parfait("ALAIN")
(37, 1121914, True)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 | |
On affecte à chaque lettre de l'alphabet un code selon le tableau ci-dessous :
| A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z |
|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 |
Pour un mot donné, on détermine d’une part son *code alphabétique concaténé*, obtenu
par la juxtaposition des codes de chacun de ses caractères, et d’autre part, *son code
additionné*, qui est la somme des codes de chacun de ses caractères.
Par ailleurs, on dit que ce mot est « *parfait* » si le code additionné divise le code concaténé.
Exemples :
- Pour le mot `"PAUL"`, le code concaténé est la chaîne `'1612112'`, soit l’entier 1 612 112.
Son code additionné est l’entier 50 car 16 + 1 + 21 + 12 = 50.
50 ne divise pas l’entier 1 612 112 ; par conséquent, le mot `"PAUL"` n’est pas
parfait.
- Pour le mot `"ALAIN"`, le code concaténé est la chaîne `'1121914'`, soit l’entier
1 121 914. Le code additionné est l’entier 37 car 1 + 12 + 1 + 9 + 14 = 37.
37 divise l’entier 1 121 914 ; par conséquent, le mot `"ALAIN"` est parfait.
Compléter la fonction `est_parfait` ci-dessous qui prend comme argument une chaîne
de caractères `mot` (en lettres majuscules) et qui renvoie le code alphabétique concaténé,
le code additionné de `mot`, ainsi qu’un booléen qui indique si `mot` est parfait ou pas.
```python linenums='1'
dico = {"A":1, "B":2, "C":3, "D":4, "E":5, "F":6, "G":7, \
"H":8, "I":9, "J":10, "K":11, "L":12, "M":13, \
"N":14, "O":15, "P":16, "Q":17, "R":18, "S":19, \
"T":20, "U":21,"V":22, "W":23, "X":24, "Y":25, "Z":26}
def est_parfait(mot) :
#mot est une chaîne de caractères (en lettres majuscules)
code_c = ""
code_a = ???
for c in mot :
code_c = code_c + ???
code_a = ???
code_c = int(code_c)
if ??? :
mot_est_parfait = True
else :
mot_est_parfait = False
return [code_a, code_c, mot_est_parfait]
Exemples :
>>> est_parfait("PAUL")
[50, 1612112, False]
>>> est_parfait("ALAIN")
[37, 1121914, True]
Sujet 10 ⚓︎
Exercice 10.1
L’occurrence d’un caractère dans un phrase est le nombre de fois où ce caractère est présent.
Exemples :
- l’occurrence du caractère ‘o’ dans ‘bonjour’ est 2 ;
- l’occurrence du caractère ‘b’ dans ‘Bébé’ est 1 ;
- l’occurrence du caractère ‘B’ dans ‘Bébé’ est 1 ;
- l’occurrence du caractère ‘ ‘ dans ‘Hello world !’ est 2.
On cherche les occurrences des caractères dans une phrase. On souhaite stocker ces occurrences dans un dictionnaire dont les clefs seraient les caractères de la phrase et les valeurs l’occurrence de ces caractères.
Par exemple : avec la phrase 'Hello world !' le dictionnaire est le suivant :
{'H': 1,'e': 1,'l': 3,'o': 2,' ': 2,'w': 1,'r': 1,'d': 1,'!': 1}
Écrire une fonction occurence_lettres prenant comme paramètre une variable
phrase de type str. Cette fonction doit renvoyer un dictionnaire de type constitué des
occurrences des caractères présents dans la phrase.
F. Chambon relève des erreurs d'orthographe et de typographie dans l'exercice 10.1 ; ainsi qu'une fin d'énoncé peu claire.
Source : commentaires à propos du 10.1.
Après vérification, le terme occurrence vient de la linguistique :
En linguistique, l'occurrence d'un mot est son apparition dans un corpus. Pour dater l'apparition d'un mot dans une langue, les lexicographes cherchent la première occurrence de ce mot : on dit que le mot est attesté à telle ou telle date.
Source : wikipédia
La définition donnée est donc fausse ou en tout cas peu connue.
L’occurrence d’un caractère dans une phrase est son apparition dans la phrase.
Exemples :
- dans
'bonjour'il y a 2 occurrences du caractère'o'; - dans
'Bébé'il y a une seule occurrence du caractère'b'et une seule du caractère'B'; - on compte 3 occurrences du caractère
' '(espace) dans'Bonjour le monde !'.
On cherche à comptabiliser les occurrences des caractères dans une phrase. On souhaite stocker ces nombres d'occurrences dans un dictionnaire dont les clefs seraient les caractères de la phrase et les valeurs associées les nombres d'occurrences de ces caractères.
Écrire une fonction nb_occurrences prenant comme paramètre une chaîne de caractères
phrase et qui renvoie le dictionnaire des nombres d'occurrences.
Exemples :
>>> nb_occurrences('Bonjour !')
{'B': 1, 'o': 2, 'n': 1, 'j': 1, 'u': 1, 'r': 1, ' ': 1, '!': 1}
>>> nb_occurrences('ha ! ha ! ha !')
{'h': 3, 'a': 3, ' ': 5, '!': 3}
1 2 3 4 5 6 7 8 | |
Ou encore avec la méthode get pour éviter le if explicite (hors-programme) :
def nb_occurrences(phrase):
d_occurrences = {}
for caractere in phrase:
d_occurrences[caractere] = d_occurrences.get(caractere, 0) + 1
return d_occurrences
Construction en compréhension et fonction prédéfinie de Python (hors-programme) :
def nb_occurrences(phrase):
return {lettre:phrase.count(lettre) for lettre in phrase}
L’occurrence d’un caractère dans un phrase est le nombre de fois où ce caractère est
présent.
Exemples :
- l’occurrence du caractère ‘o’ dans ‘bonjour’ est 2 ;
- l’occurrence du caractère ‘b’ dans ‘Bébé’ est 1 ;
- l’occurrence du caractère ‘B’ dans ‘Bébé’ est 1 ;
- l’occurrence du caractère ‘ ‘ dans ‘Hello world !’ est 2.
On cherche les occurrences des caractères dans une phrase. On souhaite stocker ces
occurrences dans un dictionnaire dont les clefs seraient les caractères de la phrase et
les valeurs l’occurrence de ces caractères.
Par exemple : avec la phrase 'Hello world !' le dictionnaire est le suivant :
`{'H': 1,'e': 1,'l': 3,'o': 2,' ': 2,'w': 1,'r': 1,'d': 1,'!': 1}`
Écrire une fonction `occurence_lettres` prenant comme paramètre une variable
`phrase` de type `str`. Cette fonction doit renvoyer un dictionnaire de type constitué des
occurrences des caractères présents dans la phrase.
Exercice 10.2
La fonction fusion prend deux listes L1, L2 d’entiers triées par ordre croissant et les
fusionne en une liste triée L12 qu’elle renvoie.
Le code Python de la fonction est
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 | |
Compléter le code.
Exemple :
>>> fusion([1,6,10],[0,7,8,9])
[0, 1, 6, 7, 8, 9, 10]
F. Chambon relève encore des soucis PEP8 (mauvais nommage et espaces manquantes). Il dénonce l'initialisation du tableau résultat par concaténation multiple :
tableau = [0] * n
devrait être remplacé par :
tableau = [0 for _ in range(n)]
Je ne suis pas d'accord avec ça. Le seul reproche qu'on peut faire à [0] * n c'est que les élèves pourraient vouloir s'en servir pour initialiser une liste de listes.
Mais pour une liste d'objets non mutables (donc une liste d'entiers) l'écriture [0] * n est quand beaucoup plus concise, lisible et... efficace en temps (un rapport 10 environ)
Par contre je suis d'accord avec la remarque sur le fait que le résultat final peut être une liste qu'on va remplir avec des append successifs.
La fonction fusionne prend en paramètres l1 et l2 deux listes d’entiers triées par ordre croissant et les fusionne en une liste triée l12 qu’elle renvoie.
Le code Python de la fonction est
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 | |
Compléter le code.
Exemples :
>>> fusionne([1, 6, 10], [0, 7, 8, 9])
[0, 1, 6, 7, 8, 9, 10]
>>> fusionne([], [0, 7, 8, 9])
[0, 7, 8, 9]
>>> fusionne([1, 6, 10], [])
[1, 6, 10]
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 | |
La fonction `fusion` prend deux listes `L1`, `L2` d’entiers triées par ordre croissant et les
fusionne en une liste triée `L12` qu’elle renvoie.
Le code Python de la fonction est
```python linenums='1'
def fusion(L1,L2):
n1 = len(L1)
n2 = len(L2)
L12 = [0]*(n1+n2)
i1 = 0
i2 = 0
i = 0
while i1 < n1 and ... :
if L1[i1] < L2[i2]:
L12[i] = ...
i1 = ...
else:
L12[i] = L2[i2]
i2 = ...
i += 1
while i1 < n1:
L12[i] = ...
i1 = i1 + 1
i = ...
while i2 < n2:
L12[i] = ...
i2 = i2 + 1
i = ...
return L12
Compléter le code.
Exemple :
>>> fusion([1,6,10],[0,7,8,9])
[0, 1, 6, 7, 8, 9, 10]
Sujet 11 ⚓︎
Exercice 11.1
Écrire une fonction recherche qui prend en paramètres un tableau tab de nombres
entiers triés par ordre croissant et un nombre entier n, et qui effectue une recherche
dichotomique du nombre entier n dans le tableau non vide tab.
Cette fonction doit renvoyer un indice correspondant au nombre cherché s’il est dans le
tableau, -1 sinon.
Exemples :
>>> recherche([2, 3, 4, 5, 6], 5)
3
>>> recherche([2, 3, 4, 6, 7], 5)
-1
R. Janvier nous dit que le principal défaut de l'exercice 11.1 est qu'il est trop difficile pour un exercice 1 : cet exercice a déjà été proposé dans 2 autres sujets mais en exercice 2. De plus, imposer une méthode de résolution sur un exercice qui n'est pas un texte à trou n'a pas beaucoup de sens : que faire si le candidat répond à l'exercice mais sans utiliser la méthode ?
Cette exercice doit être supprimé et remplacé.
Pas de corrigé proposé : cet exercice doit être supprimé de ce sujet
Écrire une fonction `recherche` qui prend en paramètres un tableau `tab` de nombres
entiers triés par ordre croissant et un nombre entier `n`, et qui effectue une recherche
dichotomique du nombre entier `n` dans le tableau non vide `tab`.
Cette fonction doit renvoyer un indice correspondant au nombre cherché s’il est dans le
tableau, `-1` sinon.
Exemples :
```python
>>> recherche([2, 3, 4, 5, 6], 5)
3
>>> recherche([2, 3, 4, 6, 7], 5)
-1
```
Exercice 11.2
Le codage de César transforme un message en changeant chaque lettre en la décalant dans l’alphabet. Par exemple, avec un décalage de 3, le A se transforme en D, le B en E, ..., le X en A, le Y en B et le Z en C. Les autres caractères (‘!’,’ ?’…) ne sont pas codés.
La fonction position_alphabet ci-dessous prend en paramètre un caractère lettre
et renvoie la position de lettre dans la chaîne de caractères ALPHABET s’il s’y trouve
et -1 sinon.
La fonction cesar prend en paramètre une chaîne de caractères message et un nombre
entier decalage et renvoie le nouveau message codé avec le codage de César utilisant
le décalage decalage.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 | |
Compléter la fonction cesar.
Exemples :
>>> cesar('BONJOUR A TOUS. VIVE LA MATIERE NSI !',4)
'FSRNSYV E XSYW. ZMZI PE QEXMIVI RWM !'
>>> cesar('GTSOTZW F YTZX. ANAJ QF RFYNJWJ SXN !',-5)
'BONJOUR A TOUS. VIVE LA MATIERE NSI !'
R. Janvier note des erreurs typographiques et attire l'attention sur l'utilisation de la méthode find pas au programme. Peut-être plutôt utiliser la fonction ord qui donne le code ascii d'un caractère : ord(lettre) - ord('A') va donner la position de lettre dans l'alphabet
Attention au choix des noms de variables. Dans la boucle ce sera plutôt for caractere in message: que for lettre ... car justement ce n'est pas forcément une lettre (cela peut être un signe de ponctuation).
Le codage de César transforme un message en changeant chaque lettre par une autre obtenue par décalage dans l’alphabet de la lettre d'origine. Par exemple, avec un décalage de 3, le A se transforme en D, le B en E, ..., le X en A, le Y en B et le Z en C. Les autres caractères (‘!’,’ ?’…) ne sont pas codés.
La fonction position_alphabet ci-dessous prend en paramètre un caractère lettre
et renvoie la position de lettre dans la chaîne de caractères ALPHABET s’il s’y trouve.
La fonction cesar prend en paramètres une chaîne de caractères message et un nombre
entier decalage et renvoie le nouveau message codé avec le codage de César utilisant
le décalage decalage.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 | |
Compléter la fonction cesar.
Exemples :
>>> cesar('BONJOUR A TOUS. VIVE LA MATIERE NSI !', 4)
'FSRNSYV E XSYW. ZMZI PE QEXMIVI RWM !'
>>> cesar('GTSOTZW F YTZX. ANAJ QF RFYNJWJ SXN !', -5)
'BONJOUR A TOUS. VIVE LA MATIERE NSI !'
1 2 3 4 5 6 7 8 9 10 11 12 13 14 | |
Le codage de César transforme un message en changeant chaque lettre en la décalant
dans l’alphabet.
Par exemple, avec un décalage de 3, le A se transforme en D, le B en E, ..., le X en A,
le Y en B et le Z en C. Les autres caractères (‘!’,’ ?’…) ne sont pas codés.
La fonction `position_alphabet` ci-dessous prend en paramètre un caractère `lettre`
et renvoie la position de `lettre` dans la chaîne de caractères `ALPHABET` s’il s’y trouve
et `-1` sinon.
La fonction `cesar` prend en paramètre une chaîne de caractères `message` et un nombre
entier `decalage` et renvoie le nouveau message codé avec le codage de César utilisant
le décalage `decalage`.
```python linenums='1'
ALPHABET = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
def position_alphabet(lettre):
return ALPHABET.find(lettre)
def cesar(message, decalage):
resultat = ''
for ... in message:
if lettre in ALPHABET:
indice = ( ... ) % 26
resultat = resultat + ALPHABET[indice]
else:
resultat = ...
return resultat
Compléter la fonction cesar.
Exemples :
>>> cesar('BONJOUR A TOUS. VIVE LA MATIERE NSI !',4)
'FSRNSYV E XSYW. ZMZI PE QEXMIVI RWM !'
>>> cesar('GTSOTZW F YTZX. ANAJ QF RFYNJWJ SXN !',-5)
'BONJOUR A TOUS. VIVE LA MATIERE NSI !'
Sujet 12 ⚓︎
Exercice 12.1
Programmer la fonction moyenne prenant en paramètre un tableau d'entiers tab (type
list) qui renvoie la moyenne de ses éléments si le tableau est non vide et affiche
'erreur' si le tableau est vide.
Exemples :
>>> moyenne([5,3,8])
5.333333333333333
>>> moyenne([1,2,3,4,5,6,7,8,9,10])
5.5
>>> moyenne([])
'erreur'
R. Janvier relève qu'une fonction qui renvoie un objet d'un type différent en cas d'erreur ce n'est pas une bonne idée. Il propose de considérer le tableau de l'exercice comme non vide pour éliminer l'erreur de la division par zéro.
Il se pose aussi la question de l'interdiction d'utiliser la fonction prédéfinie sum. Notons enfin que cet exercice se retrouve en 35.1 et 39.1.
Programmer la fonction moyenne prenant en paramètre un tableau non vide d'entiers tableau (type
list) qui renvoie la moyenne de ses éléments.
Exemples :
>>> moyenne([5, 3, 8])
5.333333333333333
>>> moyenne([1, 2, 3, 4, 5, 6, 7])
4.0
def moyenne(tableau):
nb_elements, total = 0, 0
for element in tableau:
nb_elements += 1
total += element
return total / nb_elements
Si on s'autorise len :
1 2 3 4 5 | |
Avec sum :
def moyenne(tableau):
return sum(tableau) / len(tableau)
Programmer la fonction ```moyenne``` prenant en paramètre un tableau d'entiers ```tab``` (type
`list`) qui renvoie la moyenne de ses éléments si le tableau est non vide et affiche
'erreur' si le tableau est vide.
Exemples :
```python
>>> moyenne([5,3,8])
5.333333333333333
>>> moyenne([1,2,3,4,5,6,7,8,9,10])
5.5
>>> moyenne([])
'erreur'
```
Exercice 12.2
On considère un tableau d'entiers tab (type list dont les éléments sont des 0 ou des 1). On se propose de trier ce tableau selon l'algorithme suivant : à chaque étape du tri,le tableau est constitué de trois zones consécutives, la première ne contenant que des 0,
la seconde n'étant pas triée et la dernière ne contenant que des 1.
| Zone de 0 | Zone non triée | Zone de 1 |
Tant que la zone non triée n'est pas réduite à un seul élément, on regarde son premier élément :
- si cet élément vaut 0, on considère qu'il appartient désormais à la zone ne contenant que des 0 ;
- si cet élément vaut 1, il est échangé avec le dernier élément de la zone non triée et on considère alors qu’il appartient à la zone ne contenant que des 1.
Dans tous les cas, la longueur de la zone non triée diminue de 1.
Recopier sous Python en la complétant la fonction tri suivante :
1 2 3 4 5 6 7 8 9 10 11 12 13 14 | |
Exemple :
>>> tri([0,1,0,1,0,1,0,1,0])
[0, 0, 0, 0, 0, 1, 1, 1, 1]
R. Janvier dit apprécier cet exercice, qu'on retrouve dans le sujet 26, moins bien expliqué d'après lui. Il soulève quelques soucis de typographie (des espaces manquantes) ainsi que ce problème quasi récurrent sur toutes les fonctions de tri en place : cette volonté de faire tout de même un return pour faciliter l'affichage des exemples.
Le nom de la version sujet 26 (separe) est plus sympathique aussi. Ce dernier sujet s'autorise l'échange de valeurs par affectation multiple. Mais cette solution ne peut pas être exigée. La solution serait donc de proposer au candidat d'écrire une fonction echange(tab, i, j).
F. Nativel remarque, très justement :
Puisqu'on sait que le tableau ne contient que des 0 ou des 1, dans le
elseon sait qu'il s'agit d'un 1. La conséquence : on peut se passer de l'échange et faire uniquement deux affectations :
...
else:
tab[debut] = tab[fin]
tab[fin] = 1
...
On considère un tableau d'entiers tab (type list dont les éléments sont des 0 ou des 1). On se propose de trier ce tableau selon l'algorithme suivant : à chaque étape du tri, le tableau est constitué de trois zones consécutives, la première ne contenant que des 0,
la seconde n'étant pas triée et la dernière ne contenant que des 1.
Ci-dessous un schéma de la situation pendant le processus de séparation des 0 et des 1 :
debut de zone fin de zone
non triée non triée
| |
v v
------------------------------------
| 0 ... 0 | zone non triée | 1 ... 1 |
------------------------------------
Tant que la zone non triée n'est pas réduite à un seul élément, on regarde son premier élément :
- si cet élément vaut 0, on considère qu'il appartient désormais à la zone ne contenant que des 0 ;
- si cet élément vaut 1, il est échangé avec le dernier élément de la zone non triée et on considère alors qu’il appartient à la zone ne contenant que des 1.
Dans tous les cas, la longueur de la zone non triée diminue de 1.
Compléter la fonction separe :
1 2 3 4 5 6 7 8 9 10 11 | |
Exemple :
>>> L = [8, 8, 1, 8, 8, 0, 8]
>>> echange(L, 2, 5)
>>> L
[8, 8, 0, 8, 8, 1, 8]
>>> T = [0, 1, 0, 1, 0, 1, 0, 1, 0]
>>> separe(T)
>>> T
[0, 0, 0, 0, 0, 1, 1, 1, 1]
1 2 3 4 5 6 7 8 9 10 11 | |
Les pointillés sont mis pour que l'élève puisse écrire cette version :
1 2 3 4 5 6 7 8 9 10 11 | |
On considère un tableau d'entiers `tab` (type `list` dont les éléments sont des `0` ou des `1`). On se propose de trier ce tableau selon l'algorithme suivant : à chaque étape du tri,le tableau est constitué de trois zones consécutives, la première ne contenant que des `0`,
la seconde n'étant pas triée et la dernière ne contenant que des `1`.
<table>
<tr>
<td>Zone de 0</td><td>Zone non triée</td><td>Zone de 1</td>
</tr>
</table>
Tant que la zone non triée n'est pas réduite à un seul élément, on regarde son premier
élément :
- si cet élément vaut 0, on considère qu'il appartient désormais à la zone ne contenant
que des 0 ;
- si cet élément vaut 1, il est échangé avec le dernier élément de la zone non triée et on
considère alors qu’il appartient à la zone ne contenant que des 1.
Dans tous les cas, la longueur de la zone non triée diminue de 1.
Recopier sous Python en la complétant la fonction `tri` suivante :
```python linenums='1'
def tri(tab):
#i est le premier indice de la zone non triee, j le dernier indice.
#Au debut, la zone non triee est le tableau entier.
i = ...
j = ...
while i != j :
if tab[i]== 0:
i = ...
else :
valeur = tab[j]
tab[j] = ...
...
j = ...
...
Exemple :
>>> tri([0,1,0,1,0,1,0,1,0])
[0, 0, 0, 0, 0, 1, 1, 1, 1]
Sujet 13 ⚓︎
La structure de File est un pilier du programme NSI Terminale, son implémentation utilisant les objets est simple et élégante : ici l'exercice 2 bafoue cette implémentation. Soit on supprime le sujet soit on revoit le contenu de l'énoncé et du code à trou proposés.
Exercice 13.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]
R. Janvier pense (à raison) que l'exercice du rendu de monnaie semble un peu difficile pour un exercice 1, même si l'algorithme est l'une des stars du programme de NSI. Il poursuit sur quelques choix discutables sur la forme. Retrouvez son analyse complète : commentaires à propos du 13.1
Sa proposition de ne pas insister sur le fait qu'il s'agisse d'un algorithme glouton semble raisonnable et c'est sa version que nous mettons à disposition dans la version modifiée de l'énoncé.
Peut-être ne pas mettre dans l'énoncé de nom pour les trois variables de la liste résultat puisque suivant la solution adoptée par le candidat, ces variables peuvent ne pas être explicites.
De plus, puisque le système monétaire est figé, il serait souhaitable de le proposer en constante :
VALEURS = (5, 2, 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 correspondent (dans cet ordre) aux nombres de billets de 5 euros, de pièces de 2 euros et de pièces de 1 euro à rendre afin que le total rendu soit égal à somme_a_rendre.
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.
Vous pourrez utiliser la constante suivante :
VALEURS = (5, 2, 1)
Exemples :
>>> rendu(13)
[2,1,1]
>>> rendu(64)
[12,2,0]
>>> rendu(89)
[17,2,0]
>>> rendu(4)
[0, 2, 0]
1 2 3 4 5 6 7 8 9 | |
On peut se servir de la fonction divmod si on la connait :
1 2 3 4 5 6 7 | |
Certains candidats (la plupart ?) ne sauront pas ou ne penserons pas à utiliser une liste (3 ce n'est pas beaucoup) et feront quelque chose comme :
def rendu(somme_a_rendre):
n5 = somme_a_rendre // 5
somme_a_rendre = somme_a_rendre % 5
n2 = somme_a_rendre // 2
n1 = somme_a_rendre % 2
return [n5, n2, n1]
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 :
```python
>>> rendu(13)
[2,1,1]
>>> rendu(64)
[12,2,0]
>>> rendu(89)
[17,2,0]
```
Exercice 13.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 | |
File suivante où l’attribut dernier_file contient le maillon
correspondant à l’élément arrivé en dernier dans la file :
1 2 3 4 5 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 | |
>>> 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
R. Janvier tente de sauver cet exercice et vous pouvez jeter un oeil à son analyse : [commentaires à propos du 13.2]
Mais cet exercice est à revoir entièrement : l'implémentation de la structure de File avec une seule entrée et un chaînage renversé (ie dans le sens inverse de ce qu'il faudrait faire pour avoir des opérations efficaces) est une hérésie, j'explique pourquoi ici : à propos de comment chainer une liste pour avoir une File
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 (à sa création le maillon ne connaît pas son suivant, d'où l'utilisation de l'objet None):
1 2 3 4 | |
La File est constituée de maillons avec un maillon de tete, celui qu'on a enlever lors de l'action defile et un maillon de queue qui est le dernier à être arrivé par l'action enfile.
Compléter la classe File et vérifier votre travail sur les exemples. On vous donne l'initialiseur, la méthode est_vide qui renvoie True si la file est vide, False sinon, la méthode affiche qui permet de voir l'état de la file manipulée.
class File:
def __init__(self):
self.tete = None
self.queue = None
def est_vide(self):
return self.queue is None
def affiche(self):
maillon = self.tete
print('<-- sens de la file <--')
while maillon is not None:
print(maillon.valeur, end=' ')
maillon = maillon.suivant
print()
def enfile(self, element):
nouveau_maillon = ...
if self.est_vide():
self.tete = ...
else:
self.queue.suivant = ...
self... = nouveau_maillon
def defile(self):
if ...:
resultat = ...
self.tete = ...
return ...
>>> F = File()
>>> F.est_vide()
True
>>> F.enfile(2)
>>> F.affiche()
<-- sens de la file <--
2
>>> F.est_vide()
False
>>> F.enfile(5)
>>> F.enfile(7)
>>> F.affiche()
<-- sens de la file <--
2 5 7
>>> F.defile()
2
>>> F.defile()
5
>>> F.affiche()
<-- sens de la file <--
7
1 2 3 4 5 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 | |
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 :
```python linenums='1'
class Maillon :
def __init__(self,v) :
self.valeur = v
self.suivant = None
File suivante où l’attribut dernier_file contient le maillon
correspondant à l’élément arrivé en dernier dans la file :
1 2 3 4 5 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 | |
>>> 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
Sujet 14 ⚓︎
Exercice 14.1
On considère des mots à trous : ce sont des chaînes de caractères contenant uniquement
des majuscules et des caractères *. Par exemple INFO*MA*IQUE, ***I***E** et
*S* sont des mots à trous.
Programmer une fonction correspond qui :
- prend en paramètres deux chaînes de caractères
motetmot_a_trousoùmot_a_trousest un mot à trous comme indiqué ci-dessus, - renvoie :
Truesi on peut obtenirmoten remplaçant convenablement les caractères'*'demot_a_trous.Falsesinon.
Exemple :
>>> correspond('INFORMATIQUE', 'INFO*MA*IQUE')
True
>>> correspond('AUTOMATIQUE', 'INFO*MA*IQUE')
False
Une fonction inspirée de l'actualité jeux du moment. Rien à signaler sur cet exercice simple. Pour pinailler : on pourrait raccourcir un peu l'énoncé qui, avec sa double liste à puces est un peu étalé. Mais c'est un très bon exercice. D'ailleurs beaucoup de collègues parmi celles et ceux qui ont relu les sujets s'accordent à dire que ce sujet 14 est le meilleur de la série.
F. Nativel soulève une petite imprécision : rien n'est dit si le mot et le mot à trou ne sont pas de la même longueur ie est-ce que le caractère '*' remplace exactement 1 lettre majuscule ? Sûrement que oui, il vaut mieux le préciser dans l'énoncé.
On considère des mots à trous : ce sont des chaînes de caractères contenant uniquement
des majuscules et des caractères *. Par exemple INFO*MA*IQUE, ***I***E** et
*S* sont des mots à trous.
Écrire une fonction correspond prenant deux chaînes de caractères paramètres : mot et mot_a_trous où mot_a_trous est un mot à trous comme indiqué ci-dessus. La fonction renvoie True si on peut obtenir mot en remplaçant convenablement les caractères '*' de mot_a_trous, False sinon. Il est entendu que le caractère '*' remplace une et une seule lettre majuscule.
Exemples :
>>> correspond('INFORMATIQUE', 'INFO*MA*IQUE')
True
>>> correspond('AUTOMATIQUE', 'INFO*MA*IQUE')
False
def correspond(mot, mot_a_trous):
for i in range(len(mot)):
if mot_a_trous[i] != '*' and mot_a_trous[i] != mot[i]:
return False
return True
Versions complètement hors-programme
L'occasion de (re-)découvrir les fonctions all et any ...avec le bonus d'illustrer :
On commence par le any, traduction directe de la version précédente.
def correspond(mot, mot_a_trous):
return not any(mot_a_trous[i] != '*' and mot_a_trous[i] != mot[i] for i in range(len(mot)))
def correspond(mot, mot_a_trous):
return all(mot_a_trous[i] == '*' or mot_a_trous[i] == mot[i] for i in range(len(mot)))
Ou avec un enumerate si on n'aime pas range :
def correspond(mot, mot_a_trous):
return all(mot_a_trous[i] == '*' or mot_a_trous[i] == lettre for i, lettre in enumerate(mot))
On considère des mots à trous : ce sont des chaînes de caractères contenant uniquement
des majuscules et des caractères `*`. Par exemple `INFO*MA*IQUE`, `***I***E**` et
`*S*` sont des mots à trous.
Programmer une fonction correspond qui :
- prend en paramètres deux chaînes de caractères `mot` et `mot_a_trous` où
`mot_a_trous` est un mot à trous comme indiqué ci-dessus,
- renvoie :
- `True` si on peut obtenir `mot` en remplaçant convenablement les caractères
`'*'` de `mot_a_trous`.
- `False` sinon.
Exemple :
```python
>>> correspond('INFORMATIQUE', 'INFO*MA*IQUE')
True
>>> correspond('AUTOMATIQUE', 'INFO*MA*IQUE')
False
```
Exercice 14.2
On considère au plus 26 personnes A, B, C, D, E, F ... qui peuvent s'envoyer des messages avec deux règles à respecter :
- chaque personne ne peut envoyer des messages qu'à la même personne (éventuellement elle-même),
- chaque personne ne peut recevoir des messages qu'en provenance d'une seule personne (éventuellement elle-même).
Voici un exemple - avec 6 personnes - de « plan d'envoi des messages » qui respecte les règles ci-dessus, puisque chaque personne est présente une seule fois dans chaque colonne :
- A envoie ses messages à E
- E envoie ses messages à B
- B envoie ses messages à F
- F envoie ses messages à A
- C envoie ses messages à D
- D envoie ses messages à C
Et le dictionnaire correspondant à ce plan d'envoi est le suivant :
plan_a = {'A':'E', 'B':'F', 'C':'D', 'D':'C', 'E':'B', 'F':'A'}
Sur le plan d'envoi plan_a des messages ci-dessus, il y a deux cycles distincts : un premier
cycle avec A, E, B, F et un second cycle avec C et D. En revanche, le plan d’envoi plan_b ci-dessous :
plan_b = {'A':'C', 'B':'F', 'C':'E', 'D':'A', 'E':'B', 'F':'D'}
comporte un unique cycle : A, C, E, B, F, D. Dans ce cas, lorsqu’un plan d’envoi comporte un unique cycle, on dit que le plan d’envoi est cyclique.
Pour savoir si un plan d'envoi de messages comportant N personnes est cyclique, on peut utiliser l'algorithme ci-dessous :
On part de la personne A et on inspecte les N – 1 successeurs dans le plan d'envoi :
-
Si un de ces N – 1 successeurs est A lui-même, on a trouvé un cycle de taille inférieure ou égale à N – 1. Il y a donc au moins deux cycles et le plan d'envoi n'est pas cyclique.
-
Si on ne retombe pas sur A lors de cette inspection, on a un unique cycle qui passe par toutes les personnes : le plan d'envoi est cyclique.
Compléter la fonction suivante en respectant la spécification.
Remarque : la fonction python len permet d'obtenir la longueur d'un dictionnaire.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 | |
Exemples :
>>> est_cyclique({'A':'E', 'F':'A', 'C':'D', 'E':'B', 'B':'F', 'D':'C'})
False
>>> est_cyclique({'A':'E', 'F':'C', 'C':'D', 'E':'B', 'B':'F', 'D':'A'})
True
>>> est_cyclique({'A':'B', 'F':'C', 'C':'D', 'E':'A', 'B':'F', 'D':'E'})
True
>>> est_cyclique({'A':'B', 'F':'A', 'C':'D', 'E':'C', 'B':'F', 'D':'E'})
False
Voilà encore un très bon exercice, faisant manipuler un dictionnaire tout en restant assez simple. Peut-être un peu trop simple. Comme pour l'exercice 1, l'énoncé est un peu long mais difficile de faire plus court.
Peut-être peut-on donner de vrais prénoms, la fonction prenant alors en deuxième paramètre un des prénoms (s'il y a un cycle on le trouvera de toute façon). Ca permet aussi de lever la contrainte moins de 26 noms.
On considère des personnes, identifiées par un pseudo unique, qui peuvent s'envoyer des messages avec deux règles à respecter :
- chaque personne ne peut envoyer des messages qu'à 1 seule et même personne (éventuellement elle-même),
- chaque personne ne peut recevoir des messages qu'en provenance d'une seule personne (éventuellement elle-même).
Voici un exemple - avec 6 personnes - de « plan d'envoi des messages » qui respecte les règles ci-dessus, puisque chaque personne est présente une seule fois dans chaque colonne :
- Anne envoie ses messages à Elodie
- Elodie envoie ses messages à Bruno
- Bruno envoie ses messages à Fidel
- Fidel envoie ses messages à Anne
- Claude envoie ses messages à Denis
- Denis envoie ses messages à Claude
Et le dictionnaire correspondant à ce plan d'envoi est le suivant :
plan_a = {'Anne':'Elodie', 'Bruno':'Fidel', 'Claude':'Denis',
'Denis':'Claude', 'Elodie':'Bruno', 'Fidel':'Anne'}
Sur le plan d'envoi plan_a des messages ci-dessus, il y a deux cycles distincts : un premier
cycle avec Anne, Elodie, Bruno, Fidel et un second cycle avec Claude et Denis. En revanche, le plan d’envoi plan_b ci-dessous :
plan_b = {'Anne':'Claude', 'Bruno':'Fidel', 'Claude':'Elodie',
'Denis':'Anne', 'Elodie':'Bruno', 'Fidel':'Denis'}
comporte un unique cycle : Anne, Claude, Elodie, Bruno, Fidel, Denis. Dans ce cas, lorsqu’un plan d’envoi comporte un unique cycle, on dit que le plan d’envoi est cyclique.
Pour savoir si un plan d'envoi de messages comportant N personnes est cyclique, on peut utiliser l'algorithme ci-dessous :
On part d'une personne A et on inspecte les N – 1 successeurs dans le plan d'envoi :
-
Si un de ces N – 1 successeurs est A lui-même, on a trouvé un cycle de taille inférieure ou égale à N – 1. Il y a donc au moins deux cycles et le plan d'envoi n'est pas cyclique.
-
Si on ne retombe pas sur A lors de cette inspection, on a un unique cycle qui passe par toutes les personnes : le plan d'envoi est cyclique.
Compléter la fonction suivante en respectant la spécification.
Remarque : la fonction python len permet d'obtenir la longueur d'un dictionnaire.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | |
Exemples :
>>> PLAN_A = {'Anne':'Elodie', 'Fidel':'Anne', 'Claude':'Denis', 'Elodie':'Bruno', 'Bruno':'Fidel', 'Denis':'Claude'}
>>> est_cyclique(PLAN_A, 'Anne')
False
>>> PLAN_B = {'Anne':'Elodie', 'Fidel':'Claude', 'Claude':'Denis', 'Elodie':'Bruno', 'Bruno':'Fidel', 'Denis':'Anne'}
>>> est_cyclique(PLAN_B, 'Anne')
True
>>> est_cyclique(PLAN_B, 'Denis')
True
>>> PLAN_C = {'Anne':'Bruno', 'Fidel':'Claude', 'Claude':'Denis', 'Elodie':'Anne', 'Bruno':'Fidel', 'Denis':'Elodie'}
>>> est_cyclique(PLAN_C, 'Claude')
True
def est_cyclique(plan, pseudo):
n = len(plan)
personne = pseudo
for i in range(n-1):
personne = plan[personne]
if personne == pseudo:
return False
return True
On considère au plus 26 personnes A, B, C, D, E, F ... qui peuvent s'envoyer des messages
avec deux règles à respecter :
- chaque personne ne peut envoyer des messages qu'à la même personne
(éventuellement elle-même),
- chaque personne ne peut recevoir des messages qu'en provenance d'une seule
personne (éventuellement elle-même).
Voici un exemple - avec 6 personnes - de « plan d'envoi des messages » qui respecte les
règles ci-dessus, puisque chaque personne est présente une seule fois dans chaque
colonne :
- A envoie ses messages à E
- E envoie ses messages à B
- B envoie ses messages à F
- F envoie ses messages à A
- C envoie ses messages à D
- D envoie ses messages à C
Et le dictionnaire correspondant à ce plan d'envoi est le suivant :
`plan_a = {'A':'E', 'B':'F', 'C':'D', 'D':'C', 'E':'B', 'F':'A'}`
Sur le plan d'envoi `plan_a` des messages ci-dessus, il y a deux cycles distincts : un premier
cycle avec A, E, B, F et un second cycle avec C et D. En revanche, le plan d’envoi `plan_b` ci-dessous :
`plan_b = {'A':'C', 'B':'F', 'C':'E', 'D':'A', 'E':'B', 'F':'D'}`
comporte un unique cycle : A, C, E, B, F, D. Dans ce cas, lorsqu’un plan d’envoi comporte un
unique cycle, on dit que le plan d’envoi est *cyclique*.
Pour savoir si un plan d'envoi de messages comportant N personnes est cyclique, on peut
utiliser l'algorithme ci-dessous :
On part de la personne A et on inspecte les N – 1 successeurs dans le plan d'envoi :
- Si un de ces N – 1 successeurs est A lui-même, on a trouvé un cycle de taille
inférieure ou égale à N – 1. Il y a donc au moins deux cycles et le plan d'envoi n'est
pas cyclique.
- Si on ne retombe pas sur A lors de cette inspection, on a un unique cycle qui passe
par toutes les personnes : le plan d'envoi est cyclique.
Compléter la fonction suivante en respectant la spécification.
*Remarque :* la fonction python `len` permet d'obtenir la longueur d'un dictionnaire.
```python linenums='1'
def est_cyclique(plan):
'''
Prend en paramètre un dictionnaire plan correspondant
à un plan d'envoi de messages entre N personnes A, B, C,
D, E, F ...(avec N <= 26).
Renvoie True si le plan d'envoi de messages est cyclique
et False sinon.
'''
personne = 'A'
N = len(...)
for i in range(...):
if plan[...] == ...:
return ...
else:
personne = ...
return ...
```
*Exemples :*
```python
>>> est_cyclique({'A':'E', 'F':'A', 'C':'D', 'E':'B', 'B':'F', 'D':'C'})
False
>>> est_cyclique({'A':'E', 'F':'C', 'C':'D', 'E':'B', 'B':'F', 'D':'A'})
True
>>> est_cyclique({'A':'B', 'F':'C', 'C':'D', 'E':'A', 'B':'F', 'D':'E'})
True
>>> est_cyclique({'A':'B', 'F':'A', 'C':'D', 'E':'C', 'B':'F', 'D':'E'})
False
```
Sujet 15 ⚓︎
Exercice 15.1
Écrire une fonction python appelée nb_repetitions qui prend en paramètres un
élément elt et une liste tab et renvoie le nombre de fois où l’élément apparaît dans la
liste.
Exemples :
>>> nb_repetitions(5,[2,5,3,5,6,9,5])
3
>>> nb_repetitions('A',[ 'B', 'A', 'B', 'A', 'R'])
2
>>> nb_repetitions(12,[1, '! ',7,21,36,44])
0
Exercice simple. L'énoncé ne respecte pas toujours la règle typographie de l'espace après une virgule. Dans le dernier exemple, pourquoi tout d'un coup ce caractère au milieu des entiers. Cela n'a pas vraiment d'intérêt et d'ailleurs on pourrait parler de tableau plutôt que liste.
Écrire une fonction python nb_repetitions qui prend en paramètres un
élément element et un tableau tab et renvoie le nombre de fois où l’élément apparaît dans le tableau.
Exemples :
>>> nb_repetitions(5, [2, 5, 3, 5, 6, 9, 5])
3
>>> nb_repetitions('A', ['B', 'A', 'B', 'A', 'R'])
2
>>> nb_repetitions(12, [1, 8 , 7, 21, 36, 44])
0
1 2 3 4 5 6 | |
L'examinateur devra veiller à ce que le candidat ne se contente pas de :
def nb_repetitions(element, tab):
return tab.count(element)
La fonction sum peut prendre un itérateur en paramètre, et caster correctement les booléens (True vaudra 1, False 0) pour offrir une autre solution en 1 ligne :
def nb_repetitions(element, tab):
return sum(elt == element for elt in tab)
Écrire une fonction python appelée `nb_repetitions` qui prend en paramètres un
élément `elt` et une liste `tab` et renvoie le nombre de fois où l’élément apparaît dans la
liste.
Exemples :
```python
>>> nb_repetitions(5,[2,5,3,5,6,9,5])
3
>>> nb_repetitions('A',[ 'B', 'A', 'B', 'A', 'R'])
2
>>> nb_repetitions(12,[1, '! ',7,21,36,44])
0
```
Exercice 15.2
Pour rappel, la conversion d’un nombre entier positif en binaire peut s’effectuer à l’aide des divisions successives comme illustré ici :
Voici une fonction Python basée sur la méthode des divisions successives permettant de convertir un nombre entier positif en binaire :
1 2 3 4 5 6 7 | |
binaire.
Exemples :
>>> binaire(0)
'0'
>>> binaire(77)
'1001101'
Romain Janvier qui a relu ce sujet nous livre son verdict :
-
Je ne sais pas si la figure aide vraiment. Surtout que dans l’algo, on doit s’arrêter quand le quotient est 0 et dans la figure, on s’arrête lorsque a=1. En fait le dessin correspond à cette fonction :
def binaire(a): bin_a = "" while a > 1: bin_a = str(a%2) + bin_a a = a // 2 bin_a = str(a) + bin_a return bin_a -
J’ai des doutes sur le nom des variables. Je préfairais
nbetnb_bin, mais là, c’est du pinaillage. - Dans les exemples, c’est bien, il y a le cas 0 qui peut poser problème.
- Le code n’est pas très dur à remplir, même s’il n’est pas lisible par Python en l’état.
- Pour la ligne du
while, je mettrais bienwhile ...:.
Je le rejoins essentiellement sur la figure qui n'est pas adaptée (une autre est proposée dans l'énoncé modifié).
Pour rappel, la conversion d’un nombre entier positif en binaire peut s’effectuer à l’aide des divisions successives comme illustré ici :
Voici une fonction Python basée sur la méthode des divisions successives permettant de convertir un nombre entier positif en binaire :
1 2 3 4 5 6 7 | |
binaire.
Exemples :
>>> binaire(0)
'0'
>>> binaire(77)
'1001101'
1 2 3 4 5 6 7 | |
Pour rappel, la conversion d’un nombre entier positif en binaire peut s’effectuer à l’aide
des divisions successives comme illustré ici :
{: .centrer}
Voici une fonction Python basée sur la méthode des divisions successives permettant de
convertir un nombre entier positif en binaire :
```python linenums='1'
def binaire(a):
bin_a = str(...)
a = a // 2
while a ... :
bin_a = ...(a%2) + ...
a = ...
return bin_a
```
Compléter la fonction `binaire`.
Exemples :
```python
>>> binaire(0)
'0'
>>> binaire(77)
'1001101'
```
Sujet 16 ⚓︎
Exercice 16.1
Écrire une fonction maxi qui prend en paramètre une liste tab de nombres entiers et renvoie un couple donnant le plus grand élément de cette liste, ainsi que l’indice de la première apparition de ce maximum dans la liste.
Exemple :
>>> maxi([1,5,6,9,1,2,3,7,9,8])
(9,3)
Q. Konieczko nous a proposé une relecture de ce sujet 16. Il souligne le nombre de tests trop peu nombreux et l'absence de spécification en cas de tableau vide.
Source : commentairesà propos du 16.1
Pour moi l'exercice est surtout beaucoup trop simple. L'exercice 2 malheureusement ne sauvera pas ce sujet.
A noter : il s'agit du même exercice que le 06.1, où F. Chambon suggère de choisir un nom un peu plus explicite pour la fonction.
Écrire une fonction valeur_et_indice_max qui prend en paramètre un tab non vide de nombres entiers et renvoie un couple donnant le plus grand élément de cette liste, ainsi que l’indice de la première apparition de ce maximum dans la liste.
Exemples :
>>> valeur_et_indice_max([1, 5, 6, 9, 1, 2, 3, 7, 9, 8])
(9, 3)
>>> valeur_et_indice_max([1, 1, 1, 4, 4])
(4, 3)
>>> valeur_et_indice_max([10])
(10, 0)
1 2 3 4 5 6 7 8 | |
Comme aucune consigne n'existe concernant les fonctions prédéfinies...
1 2 3 | |
Une version avec enumerate (hors-programme) :
1 2 3 4 5 6 7 8 | |
Écrire une fonction `maxi` qui prend en paramètre une liste `tab` de nombres entiers et renvoie un couple donnant le plus grand élément de cette liste, ainsi que l’indice de la première apparition de ce maximum dans la liste.
Exemple :
```python
>>> maxi([1,5,6,9,1,2,3,7,9,8])
(9,3)
```
Exercice 16.2
Cet exercice utilise des piles qui seront représentées en Python par des listes (type list).
On rappelle que l’expression T1 = list(T) fait une copie de Tindépendante de T, que
l’expression x = T.pop() enlève le sommet de la pile T et le place dans la variable x et,
enfin, que l’expression T.append(v) place la valeur v au sommet de la pile T.
Compléter le code Python de la fonction positif ci-dessous qui prend une pile T de
nombres entiers en paramètre et qui renvoie la pile des entiers positifs dans le même
ordre, sans modifier la variable T.
1 2 3 4 5 6 7 8 9 10 11 12 13 | |
Exemple :
>>> positif([-1,0,5,-3,4,-6,10,9,-8 ])
T = [-1, 0, 5, -3, 4, -6, 10, 9, -8]
[0, 5, 4, 10, 9]
D'après Q. Konieczko, ce deuxième exercice souffre de :
- mauvais nommage de variables,
- présence inutile d'un
print
Source : commentaires à propos du 16.2
Je rajouterai :
- une utilisation bien fastidieuse de la pile... on se demande pourquoi avoir choisi cette structure, pas du tout adapté au problème.
- l'affectation
T2 = []à la fin duwhilequi vient de viderT2est inutile - de même que la variable intermédiaire
xdans la deuxième boucle - on peut rappeler que lors de l'affichage en ligne d'une pile, la droite de la pile représente le sommet
- un s au nom de la fonction, on recupère tous les positifs
Cet exercice utilise des piles qui seront représentées en Python par des listes (type list). De plus, lors de l'affichage de la pile en ligne, le côté droit représente le sommet de la pile.
On rappelle que l’expression liste_1 = list(liste) fait une copie de liste indépendante de liste. L’expression x = pile.pop() enlève le sommet de la pile pile et le place dans la variable x. Enfin, l’expression pile.append(v) place la valeur v au sommet de la pile pile.
Compléter le code Python de la fonction positifs ci-dessous qui prend une pile pile de
nombres entiers en paramètre et qui renvoie la pile des entiers positifs dans le même
ordre, en laissant inchangée la pile référencée par la variable pile.
1 2 3 4 5 6 7 8 9 10 | |
Exemples :
>>> T = [-1, 0, 5, -3, 4, -6, 10, 9, -8]
>>> positifs(T)
[0, 5, 4, 10, 9]
>>> T
[-1, 0, 5, -3, 4, -6, 10, 9, -8]
>>> T = [-10, -5]
>>> positifs(T)
[]
>>> T
[-10, -5]
>>> T = [1, 2, 3, 4]
>>> positifs(T)
[1, 2, 3, 4]
>>> T
[1, 2, 3, 4]
1 2 3 4 5 6 7 8 9 10 | |
Cet exercice utilise des piles qui seront représentées en Python par des listes (type `list`).
On rappelle que l’expression `T1 = list(T)` fait une copie de `T `indépendante de `T`, que
l’expression `x = T.pop()` enlève le sommet de la pile `T` et le place dans la variable `x` et,
enfin, que l’expression `T.append(v)` place la valeur `v` au sommet de la pile `T`.
Compléter le code Python de la fonction `positif` ci-dessous qui prend une pile `T` de
nombres entiers en paramètre et qui renvoie la pile des entiers positifs dans le même
ordre, sans modifier la variable `T`.
```python linenums='1'
def positif(T):
T2 = ...(T)
T3 = ...
while T2 != []:
x = ...
if ... >= 0:
T3.append(...)
T2 = []
while T3 != ...:
x = T3.pop()
...
print('T = ',T)
return T2
Exemple :
>>> positif([-1,0,5,-3,4,-6,10,9,-8 ])
T = [-1, 0, 5, -3, 4, -6, 10, 9, -8]
[0, 5, 4, 10, 9]
Sujet 17 ⚓︎
Il faut corriger la valeur par défaut mutable dans le 17.2 et le sujet sera viable. Sans cette correction c'est
Exercice 17.1
Pour cet exercice :
-
On appelle « mot » une chaîne de caractères composée avec des caractères choisis parmi les 26 lettres minuscules ou majuscules de l'alphabet,
-
On appelle « phrase » une chaîne de caractères :
- composée avec un ou plusieurs « mots » séparés entre eux par un seul
caractère espace
' ', - se finissant :
- soit par un point
'.'qui est alors collé au dernier mot, - soit par un point d'exclamation
'!'ou d'interrogation'?'qui est alors séparé du dernier mot par un seul caractère espace' '.
- soit par un point
- composée avec un ou plusieurs « mots » séparés entre eux par un seul
caractère espace
Exemples :
Après avoir remarqué le lien entre le nombre de mots et le nombres de caractères espace dans une phrase, programmer une fonction nombre_de_mots qui prend en paramètre une phrase et renvoie le nombre de mots présents dans cette phrase.
>>> nombre_de_mots('Le point d exclamation est separe !')
6
>>> nombre_de_mots('Il y a un seul espace entre les mots !')
9
Q. Konieczko trouve cet exercice bizarre mais ne lui trouve pas de défaut majeur.
Source : commentaires à propos du 17.1
Effectivement, le bizarre vient probablement qu'au début on pense à une manipulation sur les chaîne de caractères, puis dans l'énoncé on nous annonce qu'il suffit en fait de compter le nombre d'espaces.
L'exercice est donc en fait une sorte de nombre d'occurences. Tout va bien. Il faudrait ajouter quelques exemples.
Pour cet exercice :
-
On appelle « mot » une chaîne de caractères composée de caractères choisis parmi les 26 lettres minuscules ou majuscules de l'alphabet,
-
On appelle « phrase » une chaîne de caractères :
- composée d'un ou de plusieurs « mots » séparés entre eux par un seul
caractère espace
' ', - se finissant :
- soit par un point
'.'qui est alors collé au dernier mot, - soit par un point d'exclamation
'!'ou d'interrogation'?'qui est alors séparé du dernier mot par un seul caractère espace' '.
- soit par un point
- composée d'un ou de plusieurs « mots » séparés entre eux par un seul
caractère espace
Exemples :
Après avoir remarqué le lien entre le nombre de mots et le nombres de caractères espace
dans une phrase, programmer une fonction nombre_de_mots qui prend en paramètre une
phrase et renvoie le nombre de mots présents dans cette phrase.
>>> nombre_de_mots('Le point d exclamation est separe !')
6
>>> nombre_de_mots('Il y a bien une seule espace entre les mots ?')
10
>>> nombre_de_mots('Oui espace est feminin quand c est un caractere de ponctuation.')
11
La version attendue probablement :
def nombre_de_mots(phrase):
nb_espaces = 0
for lettre in phrase:
if lettre == ' ':
nb_espaces += 1
if phrase[len(phrase)-1] == '.':
nb_mots = nb_espaces + 1
else:
nb_mots = nb_espaces
return nb_mots
On peut exploiter le fait qu'à la sortie de la boucle lettre référence bien la dernière lettre de phrase et s'autoriser deux return pour raccourcir le code :
def nombre_de_mots(phrase):
nb_espaces = 0
for lettre in phrase:
if lettre == ' ':
nb_espaces += 1
if lettre == '.':
return nb_espaces + 1
else:
return nb_espaces
Pour cet exercice :
- On appelle « mot » une chaîne de caractères composée avec des caractères choisis
parmi les 26 lettres minuscules ou majuscules de l'alphabet,
- On appelle « phrase » une chaîne de caractères :
- composée avec un ou plusieurs « mots » séparés entre eux par un seul
caractère espace `' '`,
- se finissant :
- soit par un point `'.'` qui est alors collé au dernier mot,
- soit par un point d'exclamation `'!'` ou d'interrogation `'?'` qui est alors
séparé du dernier mot par un seul caractère espace `' '`.
*Exemples :*
Après avoir remarqué le lien entre le nombre de mots et le nombres de caractères espace
dans une phrase, programmer une fonction nombre_de_mots qui prend en paramètre une
phrase et renvoie le nombre de mots présents dans cette phrase.
```python
>>> nombre_de_mots('Le point d exclamation est separe !')
6
>>> nombre_de_mots('Il y a un seul espace entre les mots !')
9
```
Exercice 17.2
La classe ABR ci-dessous permet d'implémenter une structure d'arbre binaire de recherche.
1 2 3 4 5 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 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 | |
Compléter les fonctions récursives parcours et recherche afin qu'elles respectent leurs spécifications.
Voici un exemple d'utilisation :
>>> a = ABR()
>>> a.insere(7)
>>> a.insere(3)
>>> a.insere(9)
>>> a.insere(1)
>>> a.insere(9)
>>> a.parcours()
[1,3, 7, 9, 9]
>>> a.recherche(4)
False
>>> a.recherche(3)
True
Q. Konieczko remarque l'erreur grossière de la valeur par défaut sur un paramètre mutable. Il pointe la lourdeur de la notation pointée en cascade : self.racine.gauche.insere(element)
Source : commentaires à propos du 17.2.
La classe ABR ci-dessous permet d'implémenter une structure d'arbre binaire de recherche.
1 2 3 4 5 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 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 | |
Compléter les fonctions récursives parcours et recherche afin qu'elles respectent leurs
spécifications.
Voici un exemple d'utilisation :
>>> a = ABR()
>>> a.insere(7)
>>> a.insere(3)
>>> a.insere(9)
>>> a.insere(1)
>>> a.insere(9)
>>> a.parcours()
[1, 3, 7, 9, 9]
>>> a.recherche(4)
False
>>> a.recherche(3)
True
class Noeud:
''' Classe implémentant un noeud d'arbre binaire
disposant de 3 attributs :
- valeur : la valeur de l'étiquette,
- gauche : le sous-arbre gauche.
- droit : le sous-arbre droit. '''
def __init__(self, v, g, d):
self.valeur = v
self.gauche = g
self.droite = d
class ABR:
''' Classe implémentant une structure
d'arbre binaire de recherche. '''
def __init__(self):
'''Crée un arbre binaire de recherche vide'''
self.racine = None
def est_vide(self):
'''Renvoie True si l'ABR est vide et False sinon.'''
return self.racine is None
def parcours(self, tab = None):
''' Renvoie la liste tab complétée avec tous les
éléments de l'ABR triés par ordre croissant. '''
if tab is None:
tab = []
if self.est_vide():
return tab
else:
self.racine.gauche.parcours(tab)
tab.append(self.racine.valeur)
self.racine.droite.parcours(tab)
return tab
def insere(self, element):
'''Insère un élément dans l'arbre binaire de recherche, si cet élément ne figure pas déjà'''
if self.est_vide():
self.racine = Noeud(element, ABR(), ABR())
else:
if element < self.racine.valeur:
self.racine.gauche.insere(element)
else:
self.racine.droite.insere(element)
def recherche(self, element):
'''
Renvoie True si element est présent dans l'arbre
binaire et False sinon.
'''
if self.est_vide():
return False
else:
if element < self.racine.valeur:
return self.racine.gauche.recherche(element)
elif element > self.racine.valeur:
return self.racine.droite.recherche(element)
else:
return True
La classe ABR ci-dessous permet d'implémenter une structure d'arbre binaire de recherche.
```python linenums='1'
class Noeud:
''' Classe implémentant un noeud d'arbre binaire
disposant de 3 attributs :
- valeur : la valeur de l'étiquette,
- gauche : le sous-arbre gauche.
- droit : le sous-arbre droit. '''
def __init__(self, v, g, d):
self.valeur = v
self.gauche = g
self.droite = d
class ABR:
''' Classe implémentant une structure
d'arbre binaire de recherche. '''
def __init__(self):
'''Crée un arbre binaire de recherche vide'''
self.racine = None
def est_vide(self):
'''Renvoie True si l'ABR est vide et False sinon.'''
return self.racine is None
def parcours(self, tab = []):
''' Renvoie la liste tab complétée avec tous les
éléments de l'ABR triés par ordre croissant. '''
if self.est_vide():
return tab
else:
self.racine.gauche.parcours(tab)
tab.append(...)
...
return tab
def insere(self, element):
'''Insère un élément dans l'arbre binaire de recherche.'''
if self.est_vide():
self.racine = Noeud(element, ABR(), ABR())
else:
if element < self.racine.valeur:
self.racine.gauche.insere(element)
else :
self.racine.droite.insere(element)
def recherche(self, element):
'''
Renvoie True si element est présent dans l'arbre
binaire et False sinon.
'''
if self.est_vide():
return ...
else:
if element < self.racine.valeur:
return ...
elif element > self.racine.valeur:
return ...
else:
return ...
Compléter les fonctions récursives parcours et recherche afin qu'elles respectent leurs spécifications.
Voici un exemple d'utilisation :
>>> a = ABR()
>>> a.insere(7)
>>> a.insere(3)
>>> a.insere(9)
>>> a.insere(1)
>>> a.insere(9)
>>> a.parcours()
[1,3, 7, 9, 9]
>>> a.recherche(4)
False
>>> a.recherche(3)
True
Sujet 18 ⚓︎
Il s'agit d'un sujet vraiment facile : les deux exercices sont très très simples. Il faudra préciser dans l'exercice 1 du cas de l'existence ou pas de plusieurs occurences de la température minimale.
Exercice 18.1
On a relevé les valeurs moyennes annuelles des températures à Paris pour la période allant de 2013 à 2019. Les résultats ont été récupérés sous la forme de deux listes : l’une pour les températures, l’autre pour les années :
t_moy = [14.9, 13.3, 13.1, 12.5, 13.0, 13.6, 13.7]
annees = [2013, 2014, 2015, 2016, 2017, 2018, 2019]
Écrire la fonction mini qui prend en paramètres le tableau releve des relevés et le
tableau date des dates et qui renvoie la plus petite valeur relevée au cours de la
période et l’année correspondante.
Exemple :
>>> mini(t_moy, annees)
(12.5, 2016)
Il s'agit d'une recherche de minimum. Néanmoins, comme ce minimum est associé à une autre valeur (l'année), se pose la question du cas où le minimum apparaît plusieurs fois. Le plus simple est de préciser que toutes les valeurs sont distinctes.
On a relevé les valeurs moyennes annuelles des températures à Paris pour la période allant de 2013 à 2019. Les résultats ont été récupérés sous la forme de deux listes : l’une pour les températures, l’autre pour les années :
t_moy = [14.9, 13.3, 13.1, 12.5, 13.0, 13.6, 13.7]
annees = [2013, 2014, 2015, 2016, 2017, 2018, 2019]
Écrire la fonction mini qui prend en paramètres le tableau releve des relevés et le
tableau date des dates et qui renvoie la plus petite valeur relevée au cours de la
période et l’année correspondante. On pourra considérer que le minimum est unique.
Exemple :
>>> mini(t_moy, annees)
(12.5, 2016)
1 2 3 4 5 6 7 8 9 10 11 | |
En utilisant les fonctions prédéfinies de Python :
1 2 3 4 | |
On a relevé les valeurs moyennes annuelles des températures à Paris pour la période
allant de 2013 à 2019. Les résultats ont été récupérés sous la forme de deux listes : l’une pour les températures, l’autre pour les années :
```python
t_moy = [14.9, 13.3, 13.1, 12.5, 13.0, 13.6, 13.7]
annees = [2013, 2014, 2015, 2016, 2017, 2018, 2019]
```
Écrire la fonction `mini` qui prend en paramètres le tableau `releve` des relevés et le
tableau `date` des dates et qui renvoie la plus petite valeur relevée au cours de la
période et l’année correspondante.
Exemple :
```python
>>> mini(t_moy, annees)
(12.5, 2016)
```
Exercice 18.2
Un mot palindrome peut se lire de la même façon de gauche à droite ou de droite à gauche : bob, radar, et non sont des mots palindromes.
De même certains nombres sont eux aussi des palindromes : 33, 121, 345543.
L’objectif de cet exercice est d’obtenir un programme Python permettant de tester si un nombre est un nombre palindrome.
Pour remplir cette tâche, on vous demande de compléter le code des trois fonctions ci-
dessous sachant que la fonction est_nbre_palindrome s’appuiera sur la fonction
est_palindrome qui elle-même s’appuiera sur la fonction inverse_chaine.
La fonction inverse_chaine inverse l'ordre des caractères d'une chaîne de caractères
chaine et renvoie la chaîne inversée.
La fonction est_palindrome teste si une chaine de caractères chaine est un
palindrome. Elle renvoie True si c’est le cas et False sinon. Cette fonction s’appuie sur
la fonction précédente.
La fonction est_nbre_palindrome teste si un nombre nbre est un palindrome. Elle
renvoie True si c’est le cas et False sinon. Cette fonction s’appuie sur la fonction
précédente.
Compléter le code des trois fonctions ci-dessous.
def inverse_chaine(chaine):
result = ...
for caractere in chaine:
result = ...
return result
def est_palindrome(chaine):
inverse = inverse_chaine(chaine)
return ...
def est_nbre_palindrome(nbre):
chaine = ...
return est_palindrome(chaine)
>>> inverse_chaine('bac')
'cab'
>>> est_palindrome('NSI')
False
>>> est_palindrome('ISN-NSI')
True
>>> est_nbre_palindrome(214312)
False
>>> est_nbre_palindrome(213312)
True
Q. Konieczko note quelques petites erreurs de typographie.
L'exercice est un des rares à mettre l'accent sur l'interaction de plusieurs fonctions pour résoudre un problème. Ici, trois fonctions au total, mais, très très courtes et finalement l'élève n'a qu'à compléter les appels manquants. Cela semble un peu léger.
L'autre souci c'est que l'algorithme sous-jacent pour tester qu'un mot est palindrome est naïf : inverser l'ordre des lettres et vérifier l'égalité avec le mot original. Ce qui en terme de complexité fait de l'ordre de \(2n\) manipulations (si \(n\) est la longueur du mot) contre \(n/2\) si on applique l'algorithme classique consistant à tester les lettres en partant de chacune des extrémités.
On peut garder le sujet ainsi, mais c'est un exercice vraiment facile. Pas d'énoncé modifié à proposer.
1 2 3 4 5 6 7 8 9 10 11 12 13 | |
Quelques versions exotiques pour la fonction inverse_chaine (hors-programme):
1 2 | |
1 2 | |
Un mot palindrome peut se lire de la même façon de gauche à droite ou de droite à
gauche : *bob*, *radar*, et *non* sont des mots palindromes.
De même certains nombres sont eux aussi des palindromes : 33, 121, 345543.
L’objectif de cet exercice est d’obtenir un programme Python permettant de tester si un
nombre est un nombre palindrome.
Pour remplir cette tâche, on vous demande de compléter le code des trois fonctions ci-
dessous sachant que la fonction `est_nbre_palindrome` s’appuiera sur la fonction
`est_palindrome` qui elle-même s’appuiera sur la fonction `inverse_chaine`.
La fonction `inverse_chaine` inverse l'ordre des caractères d'une chaîne de caractères
`chaine` et renvoie la chaîne inversée.
La fonction `est_palindrome` teste si une chaine de caractères `chaine` est un
palindrome. Elle renvoie `True` si c’est le cas et `False` sinon. Cette fonction s’appuie sur
la fonction précédente.
La fonction `est_nbre_palindrome` teste si un nombre `nbre` est un palindrome. Elle
renvoie `True` si c’est le cas et `False` sinon. Cette fonction s’appuie sur la fonction
précédente.
Compléter le code des trois fonctions ci-dessous.
```python
def inverse_chaine(chaine):
result = ...
for caractere in chaine:
result = ...
return result
def est_palindrome(chaine):
inverse = inverse_chaine(chaine)
return ...
def est_nbre_palindrome(nbre):
chaine = ...
return est_palindrome(chaine)
>>> inverse_chaine('bac')
'cab'
>>> est_palindrome('NSI')
False
>>> est_palindrome('ISN-NSI')
True
>>> est_nbre_palindrome(214312)
False
>>> est_nbre_palindrome(213312)
True
Sujet 19 ⚓︎
Exercice 19.1 = 21.1
Programmer la fonction multiplication, prenant en paramètres deux nombres entiers
n1 et n2, et qui renvoie le produit de ces deux nombres.
Les seules opérations autorisées sont l’addition et la soustraction.
Exemples :
>>> multiplication(3,5)
15
>>> multiplication(-4,-8)
32
>>> multiplication(-2,6)
-12
>>> multiplication(-2,0)
0
Q. Konieczko trouve cet exerice 1 délicat : mal gérer le cas des négatifs ou ne pas être à l'aise avec le range(debut, fin, pas) peut mettre le candidat en difficulté.
Source : commentaires à propos du 19.1
Peut-être l'énoncé pourrait-il proposé une petite indication :
On rappelle que si \(a\) est un entier négatif et \(b\) un entier alors on peut manipuler \(-a\) qui sera positif et remplacer \(a \times b\) par \(-(-a \times b)\).
Edit : cet exercice est le même que le 21.1, d'autres lecteurs ont proposé d'autres remarques.
Programmer la fonction multiplication, prenant en paramètres deux nombres entiers
n1 et n2, et qui renvoie le produit de ces deux nombres.
Les seules opérations autorisées sont l’addition et la soustraction.
Indication : On rappelle que si \(a\) est un entier négatif et \(b\) un entier alors on peut manipuler \(-a\) qui sera positif et remplacer \(a \times b\) par \(-(-a \times b)\).
Exemples :
>>> multiplication(3, 5)
15
>>> multiplication(-4, -8)
32
>>> multiplication(-2, 6)
-12
>>> multiplication(3, -4)
-12
>>> multiplication(-2, 0)
0
Cette version n'est pas si évidente pour un élève : il faut bien voir dans le cas d'une double négation ce qui se passe (double appel récursif passant par chacun des if)
1 2 3 4 5 6 7 8 9 | |
Peut-être que cette version plus longue mais plus explicite sera celle trouvée par les candidats en réussite sur cet exercice pas facile :
def multiplication(n1, n2):
if n1 < 0 and n2 < 0:
return multiplication(-n1, -n2)
elif n1 < 0:
return -multiplication(-n1, n2)
elif n2 < 0:
return -multiplication(n1, -n2)
else:
resultat = 0
for _ in range(n2):
resultat += n1
return resultat
Programmer la fonction `multiplication`, prenant en paramètres deux nombres entiers
`n1` et `n2`, et qui renvoie le produit de ces deux nombres.
Les seules opérations autorisées sont l’addition et la soustraction.
Exemples :
```python
>>> multiplication(3,5)
15
>>> multiplication(-4,-8)
32
>>> multiplication(-2,6)
-12
>>> multiplication(-2,0)
0
```
Exercice 19.2
Soit T un tableau non vide d'entiers triés dans l'ordre croissant et n un entier.
La fonction chercher, donnée à la page suivante, doit renvoyer un indice où la valeur n
apparaît éventuellement dans T, et None sinon.
Les paramètres de la fonction sont :
T, le tableau dans lequel s'effectue la recherche ;n, l'entier à chercher dans le tableau ;i, l'indice de début de la partie du tableau où s'effectue la recherche ;j, l'indice de fin de la partie du tableau où s'effectue la recherche.
La fonction chercher est une fonction récursive basée sur le principe « diviser pour
régner ».
Le code de la fonction commence par vérifier si 0 <= i et j < len(T).
Si cette
condition n’est pas vérifiée, elle affiche "Erreur" puis renvoie None.
Recopier et compléter le code de la fonction chercher proposée ci-dessous :
1 2 3 4 5 6 7 8 9 10 11 12 13 | |
L'exécution du code doit donner :
>>> chercher([1,5,6,6,9,12],7,0,10)
Erreur
>>> chercher([1,5,6,6,9,12],7,0,5)
>>> chercher([1,5,6,6,9,12],9,0,5)
4
>>> chercher([1,5,6,6,9,12],6,0,5)
2
Q. Konieczko est assez indulgent avec cet exercice : commentaires à propos du 19.2. Il pointe les erreurs de non respect du PEP8 et s'étonne de la gestion de l'erreur par un print.
Effectivement les exceptions ne sont pas au programme. Mais la gestion des bornes de l'intervalle de recherche dans une recherche dichotomique doit-elle être exposée ? Je crois plutôt que cette recherche doit se faire à l'aide de 2 fonctions dont l'une n'expose pas ces paramètres à l'utilisateur :
def recherche(tableau, element):
return recherche_dichotomique(tableau, element, 0, len(tableau)-1)
Dans ces conditions, il n'y a pas d'erreur possible sur les bornes. Dans l'énoncé peut-être ne faut-il pas faire apparaître le terme dichotomique qui pourrait être une question de l'examinateur.
Soit tableau un tableau non vide d'entiers triés dans l'ordre croissant et n un entier.
La fonction indice_de doit renvoyer l'indice où la valeur n
apparaît dans tableau, et None si la valeur n'y figure pas.
Cette recherche utilise une fonction chercher récursive et basée sur le principe « diviser pour
régner ».
Les paramètres de la fonction chercher sont :
tableau, le tableau dans lequel s'effectue la recherche ;n, l'entier à chercher dans le tableau ;deb, l'indice de début de la partie du tableau où s'effectue la recherche ;fin, l'indice de fin de la partie du tableau où s'effectue la recherche.
Recopier et compléter le code de la fonction chercher proposée ci-dessous :
1 2 3 4 5 6 7 8 9 10 11 12 13 | |
L'exécution du code doit donner :
>>> indice_de([1, 5, 6, 6, 9, 12], 7)
>>> indice_de([1, 5, 6, 6, 9, 12], 9)
4
>>> indice_de([1, 5, 6, 6, 9, 12], 6)
2
1 2 3 4 5 6 7 8 9 10 11 12 13 | |
Soit `T` un tableau non vide d'entiers triés dans l'ordre croissant et `n` un entier.
La fonction `chercher`, donnée à la page suivante, doit renvoyer un indice où la valeur `n`
apparaît éventuellement dans `T`, et `None` sinon.
Les paramètres de la fonction sont :
- `T`, le tableau dans lequel s'effectue la recherche ;
- `n`, l'entier à chercher dans le tableau ;
- `i`, l'indice de début de la partie du tableau où s'effectue la recherche ;
- `j`, l'indice de fin de la partie du tableau où s'effectue la recherche.
La fonction `chercher` est une fonction récursive basée sur le principe « diviser pour
régner ».
Le code de la fonction commence par vérifier si `0 <= i` et `j < len(T)`.
Si cette
condition n’est pas vérifiée, elle affiche `"Erreur"` puis renvoie `None`.
Recopier et compléter le code de la fonction `chercher` proposée ci-dessous :
```python linenums='1'
def chercher(T, n, i, j):
if i < 0 or ??? :
print("Erreur")
return None
if i > j :
return None
m = (i + j) // ???
if T[m] < ??? :
return chercher(T, n, ??? , ???)
elif ??? :
return chercher(T, n, ??? , ??? )
else :
return ???
```
L'exécution du code doit donner :
```python
>>> chercher([1,5,6,6,9,12],7,0,10)
Erreur
>>> chercher([1,5,6,6,9,12],7,0,5)
>>> chercher([1,5,6,6,9,12],9,0,5)
4
>>> chercher([1,5,6,6,9,12],6,0,5)
2
```
Sujet 20 ⚓︎
Exercice 20.1
L'opérateur « ou exclusif » entre deux bits renvoie 0 si les deux bits sont égaux et 1 s'ils sont
différents :
0 ⊕ 0 = 0 , 0 ⊕ 1 = 1 , 1 ⊕ 0 = 1 , 1 ⊕ 1 = 0
On représente ici une suite de bits par un tableau contenant des 0 et des 1.
Exemples :
a = [1, 0, 1, 0, 1, 1, 0, 1]
b = [0, 1, 1, 1, 0, 1, 0, 0]
c = [1, 1, 0, 1]
d = [0, 0, 1, 1]
Écrire la fonction xor qui prend en paramètres deux tableaux de même longueur et qui renvoie
un tableau où l’élément situé à position i est le résultat, par l’opérateur « ou exclusif », des
éléments à la position i des tableaux passés en paramètres.
En considérant les quatre exemples ci-dessus, cette fonction doit passer les tests suivants :
assert(xor(a, b) == [1, 1, 0, 1, 1, 0, 0, 1])
assert(xor(c, d) == [1, 1, 1, 0])
Q. Konieczko pointe pas mal de point délicats pour la compréhension de l'énoncé de cet exercice : commentaires à propos du 20.1 :
- le caractère peu lisible utilisé pour le "ou exclusif"
- la mauvais présentation de la table de vérité, peu lisible
- les exemples de tableaux de bits non nécessaires là où ils se trouvent
Effectivement, le caractère ⊕ n'apporte rien et on devrait remplacer la ligne par une vraie table de vérité.
C'est le premier sujet où les exemples sont présentés dans des assert. Par souci d'harmonisation il serait bon de ne pas le faire.
L'opérateur « ou exclusif » (parfois représenté par le symbole ⊕) entre deux bits renvoie 0 si les deux bits sont égaux et 1 s'ils sont différents. Ci-dessous la table de vérité de cet opérateur.
| a | b | a ⊕ b |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
Écrire la fonction xor qui prend en paramètres deux tableaux de bits de même longueur et qui renvoie un tableau où l’élément situé à la position i est le résultat, par l’opérateur « ou exclusif » , des
éléments à la position i des tableaux passés en paramètres.
Exemples :
>>> a = [1, 0, 1, 0, 1, 1, 0, 1]
>>> b = [0, 1, 1, 1, 0, 1, 0, 0]
>>> c = [1, 1, 0, 1]
>>> d = [0, 0, 1, 1]
En considérant les quatre exemples ci-dessus, cette fonction doit passer les tests suivants :
>>> xor(a, b)
[1, 1, 0, 1, 1, 0, 0, 1]
>>> xor(c, d)
[1, 1, 1, 0]
def xor(bits_a, bits_b):
n = len(bits_a)
assert n == len(bits_b)
bits_xor = []
for i in range(n):
if bits_a[i] != bits_b[i]:
bits_xor.append(1)
else:
bits_xor.append(0)
return bits_xor
Une version en compréhension, plus élégante (légèrement hors-programme peut-être à cause du cast en int du booléen) :
def xor(bits_a, bits_b):
n = len(bits_a)
assert n == len(bits_b)
return [int(bits_a[i] != bits_b[i]) for i in range(n)]
Si on connait les opérateurs bit à bit de Python :
def xor(bits_a, bits_b):
n = len(bits_a)
assert n == len(bits_b)
return [bits_a[i] ^ bits_b[i] for i in range(n)]
Ou alors on ruse :
def xor(bits_a, bits_b):
n = len(bits_a)
assert n == len(bits_b)
return [abs(bits_a[i] - bits_b[i]) for i in range(n)]
L'opérateur « ou exclusif » entre deux bits renvoie 0 si les deux bits sont égaux et 1 s'ils sont
différents :
0 ⊕ 0 = 0 , 0 ⊕ 1 = 1 , 1 ⊕ 0 = 1 , 1 ⊕ 1 = 0
On représente ici une suite de bits par un tableau contenant des 0 et des 1.
Exemples :
```python
a = [1, 0, 1, 0, 1, 1, 0, 1]
b = [0, 1, 1, 1, 0, 1, 0, 0]
c = [1, 1, 0, 1]
d = [0, 0, 1, 1]
```
Écrire la fonction ```xor``` qui prend en paramètres deux tableaux de même longueur et qui renvoie
un tableau où l’élément situé à position `i` est le résultat, par l’opérateur « ou exclusif », des
éléments à la position `i` des tableaux passés en paramètres.
En considérant les quatre exemples ci-dessus, cette fonction doit passer les tests suivants :
```python
assert(xor(a, b) == [1, 1, 0, 1, 1, 0, 0, 1])
assert(xor(c, d) == [1, 1, 1, 0])
```
Exercice 20.2
Dans cet exercice, on appelle carré d’ordre \(n\) un tableau de \(n\) lignes et \(n\) colonnes dont chaque case contient un entier naturel.
Exemples :
Un carré est dit magique lorsque les sommes des éléments situés sur chaque ligne, chaque colonne et chaque diagonale sont égales. Ainsi c2 et c3 sont magiques car la somme de chaque ligne, chaque colonne et chaque diagonale est égale à 2 pour c2 et 15 pour c3. c4 n’est pas magique car la somme de la première ligne est égale à 34 alors que celle de la dernière colonne est égale à 27.
La classe Carre ci-après contient des méthodes qui permettent de manipuler des carrés.
Compléter la fonction est_magique qui prend en paramètre un carré et qui renvoie la valeur de
la somme si ce carré est magique, False sinon.
1 2 3 4 5 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 37 38 | |
Tester la fonction est_magique sur les carrés c2, c3 et c4.
Comme Q. Konieczko le fait remarquer : encore une erreur de paramètre nommé sur un mutable. Ajouter à cela des exemples de carrés non fournis, qui obligera les élèves à les saisir et ce sujet mérite sa
Source : commentaires à propos du 20.2
Je rajouterai qu'une fonction qui retourne des types différents en fonction des données est problématique. L'exercice doit se contenter d'une fonction booléenne. On peut aussi demander au candidat de faire les appels pour créer les instances de carrés de la figure. On lui fournit les tableaux de valeurs.
La méthode d'affichage n'est jamais utilisé et peut être retirée : le sujet est déjà bien long.
Dans cet exercice, on appelle carré d’ordre \(n\) un tableau de \(n\) lignes et \(n\) colonnes dont chaque case contient un entier naturel.
Exemples :
Un carré est dit magique lorsque les sommes des éléments situés sur chaque ligne, chaque colonne et chaque diagonale sont égales. Ainsi c2 et c3 sont magiques car la somme de chaque ligne, chaque colonne et chaque diagonale est égale à 2 pour c2 et 15 pour c3. c4 n’est pas magique car la somme de la première ligne est égale à 34 alors que celle de la dernière colonne est égale à 27.
La classe Carre ci-après contient des méthodes qui permettent de manipuler des carrés.
Compléter la fonction est_magique qui prend en paramètre un carré et qui renvoie True si le carré est magique, False sinon.
1 2 3 4 5 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 | |
On vous donne les tableaux de valeurs des carrés de la figure :
>>> TAB2 = [[1, 1], [1, 1]]
>>> TAB3 = [[2, 9, 4], [7, 5, 3], [6, 1, 8]]
>>> TAB4 = [[4, 5, 16, 9], [14, 7, 2, 11], [3, 10, 15, 6], [13, 12, 8, 1]]
Compléter les instructions ci-dessous pour modéliser les carrés correspondants :
>>> C2 = ...(TAB2)
>>> C3 = ...
>>> C4 = ...
Tester la fonction est_magique sur les carrés :
>>> est_magique(C2)
True
>>> est_magique(C3)
True
>>> est_magique(C4)
False
class Carre:
def __init__(self, tableau):
self.ordre = len(tableau)
self.valeurs = tableau
def somme_ligne(self, i):
'''Calcule la somme des valeurs de la ligne i'''
return sum(self.valeurs[i])
def somme_col(self, j):
'''Calcule la somme des valeurs de la colonne j'''
return sum([self.valeurs[i][j] for i in range(self.ordre)])
def est_magique(carre):
n = carre.ordre
s = carre.somme_ligne(0)
#test de la somme de chaque ligne
for i in range(1, n):
if carre.somme_ligne(i) != s:
return False
#test de la somme de chaque colonne
for j in range(n):
if carre.somme_colonne(j) != s:
return False
#test de la somme de chaque diagonale
if sum([carre.valeurs[k][k] for k in range(n)]) != s:
return False
if sum([carre.valeurs[k][n-1-k] for k in range(n)]) != s:
return False
return True
>>> TAB2 = [[1, 1], [1, 1]]
>>> TAB3 = [[2, 9, 4], [7, 5, 3], [6, 1, 8]]
>>> TAB4 = [[4, 5, 16, 9], [14, 7, 2, 11], [3, 10, 15, 6], [13, 12, 8, 1]]
>>> C2 = Carre(TAB2)
>>> C3 = Carre(TAB3)
>>> C4 = Carre(TAB4)
Dans cet exercice, on appelle carré d’ordre $n$ un tableau de $n$ lignes et $n$ colonnes dont chaque case contient un entier naturel.
Exemples :
{: .center width=70%}
Un carré est dit magique lorsque les sommes des éléments situés sur chaque ligne, chaque
colonne et chaque diagonale sont égales. Ainsi c2 et c3 sont magiques car la somme de chaque
ligne, chaque colonne et chaque diagonale est égale à 2 pour c2 et 15 pour c3. c4 n’est pas
magique car la somme de la première ligne est égale à 34 alors que celle de la dernière colonne
est égale à 27.
La classe `Carre` ci-après contient des méthodes qui permettent de manipuler des carrés.
Compléter la fonction `est_magique` qui prend en paramètre un carré et qui renvoie la valeur de
la somme si ce carré est magique, `False` sinon.
```python linenums='1'
class Carre:
def __init__(self, tableau = [[]]):
self.ordre = len(tableau)
self.valeurs = tableau
def affiche(self):
'''Affiche un carré'''
for i in range(self.ordre):
print(self.valeurs[i])
def somme_ligne(self, i):
'''Calcule la somme des valeurs de la ligne i'''
return sum(self.valeurs[i])
def somme_col(self, j):
'''Calcule la somme des valeurs de la colonne j'''
return sum([self.valeurs[i][j] for i in range(self.ordre)])
def est_magique(carre):
n = carre.ordre
s = carre.somme_ligne(0)
#test de la somme de chaque ligne
for i in range(..., ...):
if carre.somme_ligne(i) != s:
return ...
#test de la somme de chaque colonne
for j in range(n):
if ... != s:
return False
#test de la somme de chaque diagonale
if sum([carre.valeurs[...][...] for k in range(n)]) != s:
return False
if sum([carre.valeurs[k][n-1-k] for k in range(n)]) != s:
return False
return ...
```
Tester la fonction `est_magique` sur les carrés c2, c3 et c4.
Sujet 21 ⚓︎
Exercice 21.1 = 19.1
Programmer la fonction multiplication, prenant en paramètres deux nombres entiers
n1 et n2, et qui renvoie le produit de ces deux nombres.
Les seules opérations autorisées sont l’addition et la soustraction.
Lorsque j'ai lu ce sujet pour la première fois, je me suis dis que l'auteur avait du oublier de préciser que les entiers étaient positifs. Puis j'ai vu que la soustraction était autorisé donc je me suis dis que non on avait bien à traiter les 4 cas.
F. Nativel a une remarque intéressante sur le sujet :
Les élèves apprennent au collège « je multiplie les nombres sans leur signe et j’applique la règle des signes ». Ce même algo peut servir de guide pour un énoncé plus abordable.
J. Diraison propose une autre idée : se passer de la valeur absolue et utiliser le fait que \((-a)\times (-b) = a\times b\).
Nommage des variables : pour une opérations arithmétique, a et b semble acceptable comme noms de variables, en tout cas pas plus mauvais que n1, n2.
Dans tous les cas cet exercice reste difficile pour un exercice 1 (a priori pas vraiment un algorithme vu).
Programmer la fonction multiplication, prenant en paramètres deux nombres entiers
a et b, et qui renvoie le produit de ces deux nombres.
Les seules opérations autorisées sont l’addition et la soustraction.
On pourra s'inspirer de la méthode suivante :
- on calcule la multiplication des valeurs positives de
aetb(attention en ne se servant que de l'addition) - on applique la règle des signes : si
aetbsont de même signe alors le résultat de la multiplication est positif sinon il est négatif.
On pourra se servir de la fonction abs qui donne la baleur absolue d'un nombre :
>>> abs(5)
5
>>> abs(-5)
5
Version sans fonction abs
Programmer la fonction multiplication, prenant en paramètres deux nombres entiers
a et b, et qui renvoie le produit de ces deux nombres.
Les seules opérations autorisées sont l’addition et la soustraction.
On pourra utiliser l'indication suivante : \((-a)\times (-b) = a\times b\)
Une première version issue de l'énoncé original, et en se servant de la règle : \(5 \\times (-6)= - (5 \\times 6)\).
1 2 3 4 5 6 7 8 9 | |
La version avec abs :
def multiplication(a, b):
produit = 0
absolue_b = abs(b)
for _ in range(abs(a)):
produit += absolue_b
if (a > 0 and b < 0) or (a < 0 and b > 0):
return -produit
else:
return produit
La version sans abs :
def multiplication(a, b):
if a < 0:
a, b = -a, -b
produit = 0
for _ in range(a):
produit += b
return produit
et avec un itérateur :
def multiplication(a, b):
if a < 0:
a, b = -a, -b
return sum(b for _ in range(a))
Programmer la fonction `multiplication`, prenant en paramètres deux nombres entiers
`n1` et `n2`, et qui renvoie le produit de ces deux nombres.
Les seules opérations autorisées sont l’addition et la soustraction.
Exercice 21.2
Recopier et compléter sous Python la fonction suivante en respectant la spécification. On ne recopiera pas les commentaires.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 | |
Exemples :
>>> dichotomie([15, 16, 18, 19, 23, 24, 28, 29, 31, 33],28)
True
>>> dichotomie([15, 16, 18, 19, 23, 24, 28, 29, 31, 33],27)
False
La recherche dichotomique est effectivement un algorithme classique du programme de NSI. On peut alors estimer que le code à trous fournis associé à la spécification de la fonction en docstring suffit comme énoncé.
Peut-être. Mais les noms de variables devraient être explicites non ? m me semble un peu juste. ind_milieu ou milieu non ? D'un autre côté le code à trous initial me semble ne pas laisser suffisamment de trous... l'exercice est un peu trop guidé.
Recopier et compléter la fonction suivante en respectant la spécification. On ne recopiera pas les commentaires.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 | |
Exemples :
>>> dichotomie([15, 16, 18, 19, 23, 24, 28, 29, 31, 33],28)
True
>>> dichotomie([15, 16, 18, 19, 23, 24, 28, 29, 31, 33],27)
False
>>> dichotomie([], 1)
False
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 | |
Recopier et compléter sous Python la fonction suivante en respectant la spécification. On
ne recopiera pas les commentaires.
```python linenums='1'
def dichotomie(tab, x):
"""
tab : tableau d’entiers trié dans l’ordre croissant
x : nombre entier
La fonction renvoie True si tab contient x et False sinon
"""
debut = 0
fin = len(tab) - 1
while debut <= fin:
m = ...
if x == tab[m]:
return ...
if x > tab[m]:
debut = m + 1
else:
fin = ...
return ...
```
Exemples :
```python
>>> dichotomie([15, 16, 18, 19, 23, 24, 28, 29, 31, 33],28)
True
>>> dichotomie([15, 16, 18, 19, 23, 24, 28, 29, 31, 33],27)
False
```
Sujet 22 ⚓︎
Exercice 22.1
Programmer une fonction renverse, prenant en paramètre une chaîne de caractères non vide
mot et renvoie une chaîne de caractères en inversant ceux de la chaîne mot.
Exemple :
>>> renverse("informatique")
"euqitamrofni"
Un énoncé simple, des noms de fonction et de variable simples. Rien à signaler sur cet exercice. Si on veut pinailler : pourquoi préciser que le mot doit être non vide ?
Énoncé très simple mais le solutions sont nombreuses :
def renverse(mot):
tom = ''
for caractere in mot:
tom = caractere + tom
return tom
Une version récursive
def renverse(mot):
if mot == '':
return ''
else:
return renverse(mot[1:]) + mot[0]
En utilisant le slicing (hors-programme) :
def renverse(mot):
return mot[::-1]
Programmer une fonction `renverse`, prenant en paramètre une chaîne de caractères non vide
`mot` et renvoie une chaîne de caractères en inversant ceux de la chaîne `mot`.
Exemple :
```python
>>> renverse("informatique")
"euqitamrofni"
```
Exercice 22.2
Un nombre premier est un nombre entier naturel qui admet exactement deux diviseurs distincts entiers et positifs : 1 et lui-même.
Le crible d’Ératosthène permet de déterminer les nombres premiers plus petit qu’un certain nombre N fixé.
On considère pour cela un tableau tab de N booléens, initialement tous égaux à True, sauf
tab[Criblecrible0] et tab[1] qui valent False, 0 et 1 n’étant pas des nombres premiers.
On parcourt alors ce tableau de gauche à droite.
Pour chaque indice i :
-
si
tab[i]vautTrue: le nombreiest premier et on donne la valeurFalseà toutes les cases du tableau dont l’indice est un multiple dei, à partir de2*i(c’est-à-dire2*i,3*i...). -
si
tab[i]vautFalse: le nombrein’est pas premier et on n’effectue aucun changement sur le tableau.
On dispose de la fonction crible, incomplète et donnée ci-dessous, prenant en paramètre un
entier N strictement positif et renvoyant un tableau contenant tous les nombres premiers plus
petits que N.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | |
Compléter le code de cette fonction.
Une erreur de frappe dans l'énoncé. On préfèrera n à N. Le principal souci de cet exercice est la question explicite sur la fonction range avec 3 paramètres. Clairement hors-programme. Il faut au contraire donner ce que fait range, par exemple au moment où on parle des multiples 2*i, 3*i etc.
Dans l'énoncé modifié, on rajoute des trous et des exemples.
Un nombre premier est un nombre entier naturel qui admet exactement deux diviseurs distincts entiers et positifs : 1 et lui-même.
Le crible d’Ératosthène permet de déterminer les nombres premiers plus petit qu’un certain nombre \(n\) fixé.
On considère pour cela un tableau tab de \(n\) booléens, initialement tous égaux à True, sauf
tab[0] et tab[1] qui valent False, 0 et 1 n’étant pas des nombres premiers.
On parcourt alors ce tableau de gauche à droite. Pour chaque indice i :
- si
tab[i]vautTrue: le nombreiest premier et on donne la valeurFalseà toutes les cases du tableau dont l’indice est un multiple dei, à partir de2*i(c’est-à-dire2*i,3*i...). Note : la fonctionrangeva nous permettre de parcourir ces multiples. - si
tab[i]vautFalse: le nombrein’est pas premier et on n’effectue aucun changement sur le tableau.
On dispose de la fonction crible, incomplète et donnée ci-dessous, prenant en paramètre un
entier n strictement positif et renvoyant un tableau contenant tous les nombres premiers plus
petits que n.
1 2 3 4 5 6 7 8 9 10 11 12 13 | |
Exemples :
>>> crible(40)
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37]
>>> crible(2)
[]
>>> crible(7)
[2, 3, 5]
Compléter le code de cette fonction.
Un nombre premier est un nombre entier naturel qui admet exactement deux diviseurs distincts
entiers et positifs : 1 et lui-même.
Le crible d’Ératosthène permet de déterminer les nombres premiers plus petit qu’un certain
nombre N fixé.
On considère pour cela un tableau `tab` de N booléens, initialement tous égaux à `True`, sauf
`tab[Criblecrible0]` et `tab[1]` qui valent `False`, 0 et 1 n’étant pas des nombres premiers.
On parcourt alors ce tableau de gauche à droite.
Pour chaque indice `i` :
- si `tab[i]` vaut `True` : le nombre `i` est premier et on donne la valeur `False` à toutes les
cases du tableau dont l’indice est un multiple de `i`, à partir de `2*i` (c’est-à-dire `2*i`, `3*i` ...).
- si `tab[i]` vaut `False` : le nombre `i` n’est pas premier et on n’effectue aucun
changement sur le tableau.
On dispose de la fonction `crible`, incomplète et donnée ci-dessous, prenant en paramètre un
entier N strictement positif et renvoyant un tableau contenant tous les nombres premiers plus
petits que N.
```python linenums='1'
def crible(N):
"""
Renvoie un tableau contenant tous les nombres premiers plus petits que N
"""
premiers = []
tab = [True] * N
tab[0], tab[1] = False, False
for i in range(..., N):
if tab[i] == ...:
premiers.append(...)
for multiple in range(2*i, N, ...):
tab[multiple] = ...
return premiers
assert crible(40) == [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37]
```
Compléter le code de cette fonction.
Sujet 23 ⚓︎
Exercice 23.1
Sur le réseau social TipTop, on s’intéresse au nombre de « like » des abonnés. Les données sont stockées dans des dictionnaires où les clés sont les pseudos et les valeurs correspondantes sont les nombres de « like » comme ci-dessous :
{'Bob': 102, 'Ada': 201, 'Alice': 103, 'Tim': 50}
Écrire une fonction max_dico qui :
- Prend en paramètre un dictionnaire
diconon vide dont les clés sont des chaînes de caractères et les valeurs associées sont des entiers ; - Renvoie un tuple dont :
- La première valeur est la clé du dictionnaire associée à la valeur maximale ;
- La seconde valeur est la première valeur maximale présente dans le dictionnaire.
Exemples :
>>> max_dico({'Bob': 102, 'Ada': 201, 'Alice': 103, 'Tim': 50})
('Ada', 201)
>>> max_dico({'Alan': 222, 'Ada': 201, 'Eve': 220, 'Tim': 50})
('Alan', 222)
Exercice de recherche de maximum un peu original puisqu'on recherche parmi les valeurs d'un dictionnaire. Mais comme le souligne F. Nativel : commentaires à propos du 23.1, la valeur maximale pourrait apparaître plusieurs fois. Le plus simple serait de préciser dans l'énoncé qu'on récupère le premier pseudo (das l'ordre alphabétique).
Puisqu'on est parti sur une pseuo contextualisation de l'exercice autant aller au bout de la démarche et nommer plus joliement la fonction, non ?
Sur le réseau social TipTop, on s’intéresse au nombre de « like » des abonnés. Les données sont stockées dans des dictionnaires où les clés sont les pseudos et les valeurs correspondantes sont les nombres de « like » comme ci-dessous :
{'Bob': 102, 'Ada': 201, 'Alice': 103, 'Tim': 50}
Écrire une fonction top_like qui :
- Prend en paramètre un dictionnaire
likesnon vide dont les clés sont des chaînes de caractères et les valeurs associées sont des entiers ; - Renvoie un tuple dont :
- La première valeur est la clé du dictionnaire associée à la valeur maximale ; en cas d'égalité sur plusieurs clés, on choisira la plus petite suivant l'ordre alphabétique
- La seconde valeur est la valeur maximale présente dans le dictionnaire.
Exemples :
>>> top_like({'Bob': 102, 'Ada': 201, 'Alice': 103, 'Tim': 50})
('Ada', 201)
>>> top_like({'Alan': 222, 'Ada': 201, 'Eve': 222, 'Tim': 50})
('Alan', 222)
def top_like(likes):
top_pseudo = None
top_nb_likes = 0
for pseudo in likes:
nb_likes = likes[pseudo]
if nb_likes > top_nb_likes or nb_likes == top_nb_likes and pseudo < top_pseudo:
top_pseudo = pseudo
top_nb_likes = nb_likes
return top_pseudo, top_nb_likes
En utilisant la méthode items
def top_like(likes):
top_pseudo = None
top_nb_likes = 0
for pseudo, nb_likes in likes.items():
if nb_likes > top_nb_likes or nb_likes == top_nb_likes and pseudo < top_pseudo:
top_pseudo = pseudo
top_nb_likes = nb_likes
return top_pseudo, top_nb_likes
Sur le réseau social TipTop, on s’intéresse au nombre de « like » des abonnés.
Les données sont stockées dans des dictionnaires où les clés sont les pseudos et les valeurs
correspondantes sont les nombres de « like » comme ci-dessous :
`{'Bob': 102, 'Ada': 201, 'Alice': 103, 'Tim': 50}`
Écrire une fonction `max_dico` qui :
- Prend en paramètre un dictionnaire `dico` non vide dont les clés sont des chaînes de
caractères et les valeurs associées sont des entiers ;
- Renvoie un tuple dont :
- La première valeur est la clé du dictionnaire associée à la valeur maximale ;
- La seconde valeur est la première valeur maximale présente dans le
dictionnaire.
Exemples :
```python
>>> max_dico({'Bob': 102, 'Ada': 201, 'Alice': 103, 'Tim': 50})
('Ada', 201)
>>> max_dico({'Alan': 222, 'Ada': 201, 'Eve': 220, 'Tim': 50})
('Alan', 222)
```
Exercice 23.2
Nous avons l’habitude de noter les expressions arithmétiques avec des parenthèses comme par exemple : (2 + 3) × 5.
Il existe une autre notation utilisée par certaines calculatrices, appelée notation postfixe, qui n’utilise pas de parenthèses. L’expression arithmétique précédente est alors obtenue en saisissant successivement 2, puis 3, puis l’opérateur +, puis 5, et enfin l’opérateur ×. On modélise cette saisie par le tableau [2, 3, '+', 5, '*'].
Autre exemple, la notation postfixe de 3 × 2 + 5 est modélisée par le tableau :
[3, 2, '*', 5, '+'].
D’une manière plus générale, la valeur associée à une expression arithmétique en notation postfixe est déterminée à l’aide d’une pile en parcourant l’expression arithmétique de gauche à droite de la façon suivante :
- Si l’élément parcouru est un nombre, on le place au sommet de la pile ;
- Si l’élément parcouru est un opérateur, on récupère les deux éléments situés au sommet de la pile et on leur applique l’opérateur. On place alors le résultat au sommet de la pile.
- À la fin du parcours, il reste alors un seul élément dans la pile qui est le résultat de l’expression arithmétique.
Dans le cadre de cet exercice, on se limitera aux opérations × et +.
Pour cet exercice, on dispose d’une classe Pile qui implémente les méthodes de base sur la
structure de pile.
Compléter le script de la fonction eval_expression qui reçoit en paramètre une liste python
représentant la notation postfixe d’une expression arithmétique et qui renvoie sa valeur
associée.
Exemple :
>>> eval_expression([2, 3, '+', 5, '*'])
25
1 2 3 4 5 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 | |
C'est un bon exercice, qui utilise une structure de Pile dont on donne l'implémentation. Le candidat n'a pas à coder cette structure, simplement l'utiliser.
Pas d'énoncé modifié. On pourrait donner quelques exemples de plus (surtout que l'exemple donné n'est pas celui de l'énoncé) et dire qu'on suppose toujours les expressions bien formées (pas de gestion d'erreur).
Exemples :
>>> eval_expression([3, 2, '*', 5, '+']) #correspond à 3 * 2 + 5, l'ex. de l'énoncé
11
>>> eval_expression([2, 3, '+', 5, '*']) #correspond à (2 + 3) * 5
25
class Pile:
"""Classe définissant une structure de pile."""
def __init__(self):
self.contenu = []
def est_vide(self):
"""Renvoie le booléen True si la pile est vide, False sinon."""
return self.contenu == []
def empiler(self, v):
"""Place l'élément v au sommet de la pile"""
self.contenu.append(v)
def depiler(self):
"""
Retire et renvoie l’élément placé au sommet de la pile,
si la pile n’est pas vide.
"""
if not self.est_vide():
return self.contenu.pop()
def eval_expression(tab):
p = Pile()
for ... in tab:
if element != '+' ... element != '*':
p.empiler(...)
else:
if element == ...:
resultat = p.depiler() + ...
else:
resultat = ...
p.empiler(...)
return ...
Nous avons l’habitude de noter les expressions arithmétiques avec des parenthèses comme
par exemple : (2 + 3) × 5.
Il existe une autre notation utilisée par certaines calculatrices, appelée notation postfixe, qui n’utilise pas de parenthèses. L’expression arithmétique précédente est alors obtenue en
saisissant successivement 2, puis 3, puis l’opérateur +, puis 5, et enfin l’opérateur ×. On
modélise cette saisie par le tableau [2, 3, '+', 5, '*'].
Autre exemple, la notation postfixe de 3 × 2 + 5 est modélisée par le tableau :
[3, 2, '*', 5, '+'].
D’une manière plus générale, la valeur associée à une expression arithmétique en notation
postfixe est déterminée à l’aide d’une pile en parcourant l’expression arithmétique de gauche
à droite de la façon suivante :
- Si l’élément parcouru est un nombre, on le place au sommet de la pile ;
- Si l’élément parcouru est un opérateur, on récupère les deux éléments situés au
sommet de la pile et on leur applique l’opérateur. On place alors le résultat au sommet
de la pile.
- À la fin du parcours, il reste alors un seul élément dans la pile qui est le résultat de
l’expression arithmétique.
Dans le cadre de cet exercice, on se limitera aux opérations × et +.
Pour cet exercice, on dispose d’une classe `Pile` qui implémente les méthodes de base sur la
structure de pile.
Compléter le script de la fonction `eval_expression` qui reçoit en paramètre une liste python
représentant la notation postfixe d’une expression arithmétique et qui renvoie sa valeur
associée.
Exemple :
```python
>>> eval_expression([2, 3, '+', 5, '*'])
25
1 2 3 4 5 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 | |
Sujet 24 ⚓︎
L'exercice 2 avec sa Pile mal définie et inutile plombe ce sujet 24.
Exercice 24.1
Écrire la fonction maxliste, prenant en paramètre un tableau non vide de nombres tab (type
list) et renvoyant le plus grand élément de ce tableau.
Exemples :
>>> maxliste([98, 12, 104, 23, 131, 9])
131
>>> maxliste([-27, 24, -3, 15])
24
def maxliste(tab):
valeur_max = 0
for valeur in tab:
if valeur > valeur_max:
valeur_max = valeur
return valeur_max
On risque de voir :
def maxliste(tab):
return max(tab)
Écrire la fonction `maxliste`, prenant en paramètre un tableau non vide de nombres `tab` (type
`list`) et renvoyant le plus grand élément de ce tableau.
Exemples :
```python
>>> maxliste([98, 12, 104, 23, 131, 9])
131
>>> maxliste([-27, 24, -3, 15])
24
```
Exercice 24.2
On dispose de chaînes de caractères contenant uniquement des parenthèses ouvrantes et fermantes.
Un parenthésage est correct si :
- le nombre de parenthèses ouvrantes de la chaîne est égal au nombre de parenthèses fermantes.
- en parcourant la chaîne de gauche à droite, le nombre de parenthèses déjà ouvertes doit être, à tout moment, supérieur ou égal au nombre de parenthèses déjà fermées.
Ainsi, "((()())(()))" est un parenthésage correct.
Les parenthésages "())(()" et "(())(()" sont, eux, incorrects.
On dispose du code de la classe Pile suivant :
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 | |
On souhaite programmer une fonction parenthesage qui prend en paramètre une chaîne ch de
parenthèses et renvoie True si la chaîne est bien parenthésée et False sinon.
Cette fonction utilise une pile et suit le principe suivant : en parcourant la chaîne de gauche à
droite, si on trouve une parenthèse ouvrante, on l’empile au sommet de la pile et si on trouve
une parenthèse fermante, on dépile (si possible !) la parenthèse ouvrante stockée au sommet
de la pile.
La chaîne est alors bien parenthésée si, à la fin du parcours, la pile est vide.
Elle est, par contre, mal parenthésée : - si dans le parcours, on trouve une parenthèse fermante, alors que la pile est vide ; - ou si, à la fin du parcours, la pile n’est pas vide.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 | |
Compléter le code de la fonction parenthesage.
L'exercice voulait utiliser une Pile. Malheureusement l'implémentation de la Pile souffre du syndrôme du paramètre par défaut mutable. D'autre part, avec un seul type de caractère (la parenthèse) la Pile est inutile, il suffit de compter :
- on compte +1 pour une parenthèse ouvrante, -1 pour une fermante
- si au cours du comptage on tombe sur -1 on renvoie
False: le parenthésage n'est pas correct - à la fin on renvoie
Truesi le compteur est à 0 etFalsesinon
On va donc proposé deux versions modifiées :
- la première garde seulement les parenthèses et supprime l'utilisation de la Pile
- la deuxième rajoute les crochets (
[et]) et les accolades ({et}}) et propose une implémentation correcte de la Pile.
On dispose de chaînes de caractères contenant uniquement des parenthèses ouvrantes et fermantes.
Un parenthésage est correct si :
- le nombre de parenthèses ouvrantes de la chaîne est égal au nombre de parenthèses fermantes.
-
en parcourant la chaîne de gauche à droite, le nombre de parenthèses déjà ouvertes doit être, à tout moment, supérieur ou égal au nombre de parenthèses déjà fermées.
-
"((()())(()))" est un parenthésage correct.
- les parenthésages "())(()" et "(())(()" sont, eux, incorrects.
On souhaite programmer une fonction bien_parenthesee qui prend en paramètre une chaîne chaine de
parenthèses et renvoie True si la chaîne est bien parenthésée et False sinon.
Le principe est le suivant :
- on compte +1 pour une parenthèse ouvrante, -1 pour une fermante
- si on est sur une parenthèse fermante alors que le compteur est à 0, on renvoie
False: le parenthésage n'est pas correct - à la fin on renvoie
Truesi le compteur est à 0 etFalsesinon
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 | |
Version nécessitant une Pile (beaucoup plus difficile, probablement trop)
On dispose de chaînes de caractères contenant : - des parenthèses ouvrantes et fermantes - des crochets ouvrants et fermants - des accolades ouvrantes et fermantes
On appellera délimiteur une parenthèse, un crochet ou une accolade. Un parenthésage est correct si :
- pour chaque délimiteur le nombre de fermants coïncide avec le nombre d'ouvrants
- en parcourant la chaîne de gauche à droite, pour chaque délimiteur, le nombre d'ouvrant doit être, à tout moment, supérieur ou égal au nombre de fermants.
-
les différents délimiteurs ne doivent pas s'entre-croiser :
[(])est incorrect. -
"([()[]]{()})" est un parenthésage correct.
- les parenthésages "{}[(])" (entre-croisement) et "[]]" (crochet fermant en trop à la fin) sont, eux, incorrects.
On souhaite programmer une fonction bien_parenthesee qui prend en paramètre une chaîne chaine de
délimiteurs et renvoie True si la chaîne est bien parenthésée et False sinon.
Le principe est le suivant en se servant d'une Pile (dont l'implémentation vous est donnée) :
- on parcourt les caractères de la chaîne, si c'est un délimiteur ouvrant on l'empile
- si c'est un délimiteur fermant :
- si la Pile est vide, on renvoie
False: le parenthésage est incorrect - si la Pile n'est pas vide mais que le caractère dépilé n'est pas le délimiteur ouvrant de celui qu'on a : on renvoie
False
- si la Pile est vide, on renvoie
- à la fin du parcourt : si la Pile est vide on renvoie
Truesinon on renvoieFalse
On pourra se servir d'un dictionnaire pour faire la correspondance entre le délimiteur ouvrant et le fermant.
1 2 3 4 5 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 37 38 | |
On peut raccourcir un peu :
def bien_parenthesee(ch):
"""Renvoie True si la chaîne ch est bien parenthésée et False sinon"""
p = Pile()
for c in ch:
if c in DELIMITEUR:
...
elif p.est_vide() or c != DELIMITEUR[...]:
return ...
return ...
On dispose de chaînes de caractères contenant uniquement des parenthèses ouvrantes et
fermantes.
Un parenthésage est correct si :
- le nombre de parenthèses ouvrantes de la chaîne est égal au nombre de parenthèses
fermantes.
- en parcourant la chaîne de gauche à droite, le nombre de parenthèses déjà ouvertes doit
être, à tout moment, supérieur ou égal au nombre de parenthèses déjà fermées.
Ainsi, "((()())(()))" est un parenthésage correct.
Les parenthésages "())(()" et "(())(()" sont, eux, incorrects.
On dispose du code de la classe `Pile` suivant :
```python linenums='1'
class Pile:
""" Classe définissant une pile """
def __init__(self, valeurs=[]):
self.valeurs = valeurs
def est_vide(self):
"""Renvoie True si la pile est vide, False sinon"""
return self.valeurs == []
def empiler(self, c):
"""Place l’élément c au sommet de la pile"""
self.valeurs.append(c)
def depiler(self):
"""Supprime l’élément placé au sommet de la pile, à condition qu’elle soit non vide"""
if self.est_vide() == False:
self.valeurs.pop()
On souhaite programmer une fonction parenthesage qui prend en paramètre une chaîne ch de
parenthèses et renvoie True si la chaîne est bien parenthésée et False sinon.
Cette fonction utilise une pile et suit le principe suivant : en parcourant la chaîne de gauche à
droite, si on trouve une parenthèse ouvrante, on l’empile au sommet de la pile et si on trouve
une parenthèse fermante, on dépile (si possible !) la parenthèse ouvrante stockée au sommet
de la pile.
La chaîne est alors bien parenthésée si, à la fin du parcours, la pile est vide.
Elle est, par contre, mal parenthésée : - si dans le parcours, on trouve une parenthèse fermante, alors que la pile est vide ; - ou si, à la fin du parcours, la pile n’est pas vide.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 | |
Compléter le code de la fonction parenthesage.
```
Sujet 25 ⚓︎
L'exercice 1 est très bien, il faudrait lui trouver un exercice 2 faisable pour avoir un sujet.
Exercice 25.1
On considère des tables (des tableaux de dictionnaires) qui contiennent des enregistrements
relatifs à des animaux hébergés dans un refuge. Les attributs des enregistrements sont
'nom', 'espece', 'age', 'enclos'. Voici un exemple d'une telle table :
animaux = [ {'nom':'Medor', 'espece':'chien', 'age':5, 'enclos':2},
{'nom':'Titine', 'espece':'chat', 'age':2, 'enclos':5},
{'nom':'Tom', 'espece':'chat', 'age':7, 'enclos':4},
{'nom':'Belle', 'espece':'chien', 'age':6, 'enclos':3},
{'nom':'Mirza', 'espece':'chat', 'age':6, 'enclos':5}]
Programmer une fonction selection_enclos qui :
- prend en paramètres :
- une table
table_animauxcontenant des enregistrements relatifs à des animaux (comme dans l'exemple ci-dessus), - un numéro d'enclos
num_enclos;
- une table
- renvoie une table contenant les enregistrements de
table_animauxdont l'attribut'enclos'estnum_enclos.
Exemples avec la table animaux ci-dessus :
>>> selection_enclos(animaux, 5)
[{'nom':'Titine', 'espece':'chat', 'age':2, 'enclos':5},
{'nom':'Mirza', 'espece':'chat', 'age':6, 'enclos':5}]
>>> selection_enclos(animaux, 2)
[{'nom':'Medor', 'espece':'chien', 'age':5, 'enclos':2}]
>>> selection_enclos(animaux, 7)
[]
Bon exercice, qui change des recherches de maximum.
On considère des tables (des tableaux de dictionnaires) qui contiennent des enregistrements
relatifs à des animaux hébergés dans un refuge. Les attributs des enregistrements sont
`'nom'`, `'espece'`, `'age'`, `'enclos'`. Voici un exemple d'une telle table :
```python
animaux = [ {'nom':'Medor', 'espece':'chien', 'age':5, 'enclos':2},
{'nom':'Titine', 'espece':'chat', 'age':2, 'enclos':5},
{'nom':'Tom', 'espece':'chat', 'age':7, 'enclos':4},
{'nom':'Belle', 'espece':'chien', 'age':6, 'enclos':3},
{'nom':'Mirza', 'espece':'chat', 'age':6, 'enclos':5}]
```
Programmer une fonction `selection_enclos` qui :
- prend en paramètres :
- une table `table_animaux` contenant des enregistrements relatifs à des
animaux (comme dans l'exemple ci-dessus),
- un numéro d'enclos `num_enclos` ;
- renvoie une table contenant les enregistrements de `table_animaux` dont l'attribut
`'enclos'` est `num_enclos`.
Exemples avec la table animaux ci-dessus :
```python
>>> selection_enclos(animaux, 5)
[{'nom':'Titine', 'espece':'chat', 'age':2, 'enclos':5},
{'nom':'Mirza', 'espece':'chat', 'age':6, 'enclos':5}]
>>> selection_enclos(animaux, 2)
[{'nom':'Medor', 'espece':'chien', 'age':5, 'enclos':2}]
>>> selection_enclos(animaux, 7)
[]
```
Exercice 25.2
On considère des tableaux de nombres dont tous les éléments sont présents exactement trois fois et à suivre, sauf un élément qui est présent une unique fois et que l'on appelle « l'intrus ». Voici quelques exemples :
tab_a = [3, 3, 3, 9, 9, 9, 1, 1, 1, 7, 2, 2, 2, 4, 4, 4, 8, 8, 8, 5, 5, 5]
#l'intrus est 7
tab_b = [8, 5, 5, 5, 9, 9, 9, 18, 18, 18, 3, 3, 3]
#l'intrus est 8
tab_c = [5, 5, 5, 1, 1, 1, 0, 0, 0, 6, 6, 6, 3, 8, 8, 8]
#l'intrus est 3
- pour les indices multiples de 3 situés strictement avant l'intrus, l'élément correspondant et son voisin de droite sont égaux,
- pour les indices multiples de 3 situés après l'intrus, l'élément correspondant et son voisin de droite - s'il existe - sont différents.
Ce que l'on peut observer ci-dessous en observant les valeurs des paires de voisins marquées par des caractères ^ :
[3, 3, 3, 9, 9, 9, 1, 1, 1, 7, 2, 2, 2, 4, 4, 4, 8, 8, 8, 5, 5, 5]
^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^
0 3 6 9 12 15 18 21
Dans des listes comme celles ci-dessus, un algorithme récursif pour trouver l'intrus consiste alors à choisir un indice i multiple de 3 situé approximativement au milieu des indices parmi lesquels se trouve l'intrus.
Puis, en fonction des valeurs de l'élément d'indice i et de son voisin de droite, à appliquer récursivement l'algorithme à la moitié droite ou à la moitié gauche des indices parmi lesquels se trouve l'intrus.
Compléter la fonction ci-dessous qui met en œuvre cet algorithme.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 | |
Exemples :
>>> trouver_intrus([3, 3, 3, 9, 9, 9, 1, 1, 1, 7, 2, 2, 2, 4, 4, 4, 8, 8,
8, 5, 5, 5], 0, 21)
7
>>> trouver_intrus([8, 5, 5, 5, 9, 9, 9, 18, 18, 18, 3, 3, 3], 0, 12)
8
>>> trouver_intrus([5, 5, 5, 1, 1, 1, 0, 0, 0, 6, 6, 6, 3, 8, 8, 8], 0, 15)
3
Cet exercice est bien trop particulier, rattaché à aucun algorithme classique du programme de NSI. Compliqué à comprendre. A retirer. Aucune version modifiée n'est proposé. On donne quand même un corrigé. C'est très dommage car cela plombe l'exercice 1 qui lui était bien.
def trouver_intrus(tab, g, d):
'''
Renvoie la valeur de l'intrus situé entre les indices g et d
dans la liste tab où
tab vérifie les conditions de l'exercice,
g et d sont des multiples de 3.
'''
if g == d:
return tab[g]
else:
nombre_de_triplets = (d - g) // 3
indice = g + 3 * (nombre_de_triplets // 2)
if tab[indice] == tab[indice+1]:
return trouver_intrus(tab, indice+3, d)
else:
return trouver_intrus(tab, g, indice)
On considère des tableaux de nombres dont tous les éléments sont présents exactement
trois fois et à suivre, sauf un élément qui est présent une unique fois et que l'on appelle «
l'intrus ». Voici quelques exemples :
```python
tab_a = [3, 3, 3, 9, 9, 9, 1, 1, 1, 7, 2, 2, 2, 4, 4, 4, 8, 8, 8, 5, 5, 5]
#l'intrus est 7
tab_b = [8, 5, 5, 5, 9, 9, 9, 18, 18, 18, 3, 3, 3]
#l'intrus est 8
tab_c = [5, 5, 5, 1, 1, 1, 0, 0, 0, 6, 6, 6, 3, 8, 8, 8]
#l'intrus est 3
- pour les indices multiples de 3 situés strictement avant l'intrus, l'élément correspondant et son voisin de droite sont égaux,
- pour les indices multiples de 3 situés après l'intrus, l'élément correspondant et son voisin de droite - s'il existe - sont différents.
Ce que l'on peut observer ci-dessous en observant les valeurs des paires de voisins marquées par des caractères ^ :
[3, 3, 3, 9, 9, 9, 1, 1, 1, 7, 2, 2, 2, 4, 4, 4, 8, 8, 8, 5, 5, 5]
^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^
0 3 6 9 12 15 18 21
Dans des listes comme celles ci-dessus, un algorithme récursif pour trouver l'intrus consiste alors à choisir un indice i multiple de 3 situé approximativement au milieu des indices parmi lesquels se trouve l'intrus.
Puis, en fonction des valeurs de l'élément d'indice i et de son voisin de droite, à appliquer récursivement l'algorithme à la moitié droite ou à la moitié gauche des indices parmi lesquels se trouve l'intrus.
Compléter la fonction ci-dessous qui met en œuvre cet algorithme.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 | |
Exemples :
>>> trouver_intrus([3, 3, 3, 9, 9, 9, 1, 1, 1, 7, 2, 2, 2, 4, 4, 4, 8, 8,
8, 5, 5, 5], 0, 21)
7
>>> trouver_intrus([8, 5, 5, 5, 9, 9, 9, 18, 18, 18, 3, 3, 3], 0, 12)
8
>>> trouver_intrus([5, 5, 5, 1, 1, 1, 0, 0, 0, 6, 6, 6, 3, 8, 8, 8], 0, 15)
3
Sujet 26 ⚓︎
Exercice 26.1
Écrire une fonction RechercheMin qui prend en paramètre un tableau de nombres non
trié tab, et qui renvoie l'indice de la première occurrence du minimum de ce tableau. Les
tableaux seront représentés sous forme de liste Python.
Exemples :
>>> RechercheMin([5])
0
>>> RechercheMin([2, 4, 1])
2
>>> RechercheMin([5, 3, 2, 2, 4])
2
N. Bonnin s'est attelée à la relecture des sujets 26 à 30. Elle pointe l'erreur de nommage de la fonction qui ne respecte pas le PEP8 et pose la question de l'utilisation conjointe de index et min pour arriver au résultat.
Il faudrait préciser aussi que le tableau n'est pas vide.
Source : commentaires à propos du 26.1
Écrire une fonction recherche_min qui prend en paramètre un tableau tableau non vide et nom trié de nombres, et qui renvoie l'indice de la première occurrence du minimum de ce tableau. Les
tableaux seront représentés sous forme de listes Python.
Exemples :
>>> recherche_min([5])
0
>>> recherche_min([2, 4, 1])
2
>>> recherche_min([5, 3, 2, 2, 4])
2
1 2 3 4 5 6 | |
Écrire une fonction `RechercheMin` qui prend en paramètre un tableau de nombres non
trié `tab`, et qui renvoie l'indice de la première occurrence du minimum de ce tableau. Les
tableaux seront représentés sous forme de liste Python.
Exemples :
```python
>>> RechercheMin([5])
0
>>> RechercheMin([2, 4, 1])
2
>>> RechercheMin([5, 3, 2, 2, 4])
2
```
Exercice 26.2 = 12.2
Attention
Il s'agit du même exercice que le 12.2 mais moins bien expliqué. Les versions modifiées sont donc les mêmes, ainsi que les corrections.
On considère la fonction separe ci-dessous qui prend en argument un tableau tab dont
les éléments sont des 0 et des 1 et qui sépare les 0 des 1 en plaçant les 0 en début de
tableau et les 1 à la suite.
1 2 3 4 5 6 7 8 9 10 | |
Compléter la fonction separe ci-dessus.
Exemples :
>>> separe([1, 0, 1, 0, 1, 0, 1, 0])
[0, 0, 0, 0, 1, 1, 1, 1]
>>> separe([1, 0, 0, 0, 1, 1, 0, 1, 1, 0, 1, 0, 1, 1, 1, 0])
[0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1]
N. Bonnin nous dit :
- L’énoncé est un peu lapidaire.
- Le return
tabfinal est superflu.
Source : commentaires à propos du 26.2
Cet exercice est le même que le 12.2, la version modifiée sera donc celle proposée à cet exercice.
On considère un tableau d'entiers tab (type list dont les éléments sont des 0 ou des 1). On se propose de trier ce tableau selon l'algorithme suivant : à chaque étape du tri, le tableau est constitué de trois zones consécutives, la première ne contenant que des 0,
la seconde n'étant pas triée et la dernière ne contenant que des 1.
Ci-dessous un schéma de la situation pendant le processus de séparation des 0 et des 1 :
debut de zone fin de zone
non triée non triée
| |
v v
------------------------------------
| 0 ... 0 | zone non triée | 1 ... 1 |
------------------------------------
Tant que la zone non triée n'est pas réduite à un seul élément, on regarde son premier élément :
- si cet élément vaut 0, on considère qu'il appartient désormais à la zone ne contenant que des 0 ;
- si cet élément vaut 1, il est échangé avec le dernier élément de la zone non triée et on considère alors qu’il appartient à la zone ne contenant que des 1.
Dans tous les cas, la longueur de la zone non triée diminue de 1.
Compléter la fonction separe :
1 2 3 4 5 6 7 8 9 10 11 | |
Exemple :
>>> L = [8, 8, 1, 8, 8, 0, 8]
>>> echange(L, 2, 5)
>>> L
[8, 8, 0, 8, 8, 1, 8]
>>> T = [0, 1, 0, 1, 0, 1, 0, 1, 0]
>>> separe(T)
>>> T
[0, 0, 0, 0, 0, 1, 1, 1, 1]
1 2 3 4 5 6 7 8 9 10 11 | |
Les pointillés sont mis pour que l'élève puisse écrire cette version :
1 2 3 4 5 6 7 8 9 10 11 | |
On considère la fonction `separe` ci-dessous qui prend en argument un tableau `tab` dont
les éléments sont des `0` et des `1` et qui sépare les `0` des `1` en plaçant les `0` en début de
tableau et les `1` à la suite.
```python linenums='1'
def separe(tab):
i = 0
j = ...
while i < j :
if tab[i] == 0 :
i = ...
else :
tab[i], tab[j] = ...
j = ...
return tab
Compléter la fonction separe ci-dessus.
Exemples :
>>> separe([1, 0, 1, 0, 1, 0, 1, 0])
[0, 0, 0, 0, 1, 1, 1, 1]
>>> separe([1, 0, 0, 0, 1, 1, 0, 1, 1, 0, 1, 0, 1, 1, 1, 0])
[0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1]
Sujet 27 ⚓︎
Exercice 27.1
Dans cet exercice, un arbre binaire de caractères est stocké sous la forme d’un dictionnaire où les clefs sont les caractères des nœuds de l’arbre et les valeurs, pour chaque clef, la liste des caractères des fils gauche et droit du nœud.
Par exemple, l’arbre
est stocké dans
a = {'F':['B','G'], 'B':['A','D'], 'A':['',''], 'D':['C','E'], \
'C':['',''], 'E':['',''], 'G':['','I'], 'I':['','H'], \
'H':['','']}
Écrire une fonction récursive taille prenant en paramètres un arbre binaire arbre
sous la forme d’un dictionnaire et un caractère lettre qui est la valeur du sommet de
l’arbre, et qui renvoie la taille de l’arbre à savoir le nombre total de nœud.
On pourra distinguer les 4 cas où les deux « fils » du nœud sont '', le fils gauche
seulement est '', le fils droit seulement est '', aucun des deux fils n’est ''.
Exemple :
>>> taille(a, ’F’)
9
N. Bonnin :
Beaucoup (trop?) de compétences testées dans cet exercice : + dictionnaire avec maniement d’une double indexation clé/indice de liste + récursivité + algorithme de parcours + compréhension d’une modélisation différente de celle préconisée dans le programme
Cela fait beaucoup pour un exercice 1 .
Source : commentaires à propos du 27.1)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 | |
Cette version suffit :
1 2 3 4 5 | |
Dans cet exercice, un arbre binaire de caractères est stocké sous la forme d’un
dictionnaire où les clefs sont les caractères des nœuds de l’arbre et les valeurs, pour
chaque clef, la liste des caractères des fils gauche et droit du nœud.
Par exemple, l’arbre
{: .centrer width=40%}
est stocké dans
```python
a = {'F':['B','G'], 'B':['A','D'], 'A':['',''], 'D':['C','E'], \
'C':['',''], 'E':['',''], 'G':['','I'], 'I':['','H'], \
'H':['','']}
```
Écrire une fonction récursive `taille` prenant en paramètres un arbre binaire `arbre`
sous la forme d’un dictionnaire et un caractère `lettre` qui est la valeur du sommet de
l’arbre, et qui renvoie la taille de l’arbre à savoir le nombre total de nœud.
On pourra distinguer les 4 cas où les deux « fils » du nœud sont `''`, le fils gauche
seulement est `''`, le fils droit seulement est `''`, aucun des deux fils n’est `''`.
Exemple :
```python
>>> taille(a, ’F’)
9
```
Exercice 27.2
On considère l'algorithme de tri de tableau suivant : à chaque étape, on parcourt depuis le début du tableau tous les éléments non rangés et on place en dernière position le plus grand élément.
Exemple avec le tableau : t = [41, 55, 21, 18, 12, 6, 25]
- Étape 1 : on parcourt tous les éléments du tableau, on permute le plus grand élément avec le dernier.
Le tableau devient t = [41, 25, 21, 18, 12, 6, 55]
- Étape 2 : on parcourt tous les éléments sauf le dernier, on permute le plus grand élément trouvé avec l'avant dernier.
Le tableau devient : t = [6, 25, 21, 18, 12, 41, 55]
Et ainsi de suite. La code de la fonction tri_iteratif qui implémente cet algorithme est donné ci-
dessous.
1 2 3 4 5 6 7 8 9 | |
Compléter le code qui doit donner :
>>> tri_iteratif([41, 55, 21, 18, 12, 6, 25])
[6, 12, 18, 21, 25, 41, 55]
On rappelle que l'instruction a, b = b, a échange les contenus de a et b.
N. Bonnin :
Algorithme de tri sélection en place, décrit assez longuement dans l’énoncé alors que c’est un algorithme au programme), quel contraste avec l’exercice 2 du 26. C’est une bonne intention, mais…
- C’est un tri en place mais on retourne le tableau
- Il y a une coquille dans le résultat affiché (le « tableau trié » n’est pas dans l’ordre)
Source : commentaires à propos du 27.2)
Bon il ne s'agit pas vraiment d'un tri par sélection puisque le parcourt du tableau se fait par la droite. De plus, le test à la sortie de la boucle interne pour éviter de faire l'échange est superflu. Comme pou d'autres exercices, on préfèrera utiliser une fonction echange pour l'échange de valeurs d'un tableau : chaque candidat-e utilisant alors l'implémentation de son choix (affectation multiple de Python, utilisation d'une variable intermédiaire etc.).
1 2 3 4 5 6 7 8 9 10 | |
On considère l'algorithme de tri de tableau suivant : à chaque étape, on parcourt depuis
le début du tableau tous les éléments non rangés et on place en dernière position le plus
grand élément.
Exemple avec le tableau : ```t = [41, 55, 21, 18, 12, 6, 25]```
- Étape 1 : on parcourt tous les éléments du tableau, on permute le plus grand élément avec le dernier.
Le tableau devient `t = [41, 25, 21, 18, 12, 6, 55]`
- Étape 2 : on parcourt tous les éléments **sauf le dernier**, on permute le plus grand élément trouvé avec l'avant dernier.
Le tableau devient : ```t = [6, 25, 21, 18, 12, 41, 55]```
Et ainsi de suite. La code de la fonction `tri_iteratif` qui implémente cet algorithme est donné ci-
dessous.
```python linenums='1'
def tri_iteratif(tab):
for k in range(..., 0 ,-1):
imax = ...
for i in range(0, ...):
if tab[i] > ... :
imax = i
if tab[max] > ... :
..., tab[imax] = tab[imax], ...
return tab
```
Compléter le code qui doit donner :
```python
>>> tri_iteratif([41, 55, 21, 18, 12, 6, 25])
[6, 12, 18, 21, 25, 41, 55]
```
On rappelle que l'instruction ```a, b = b, a``` échange les contenus de ```a``` et ```b```.
Sujet 28 ⚓︎
Exercice 28.1
Écrire une fonction moyenne qui prend en paramètre un tableau non vide de nombres
flottants et qui renvoie la moyenne des valeurs du tableau. Les tableaux seront
représentés sous forme de liste Python.
Exemples :
>>> moyenne([1.0])
1.0
>>> moyenne([1.0, 2.0, 4.0])
2.3333333333333335
Pas de grosses fautes mais comme pour les x exemplaires de recherche d'extremum, le calcul de la moyenne d'un tableau de valeurs est un peu éculé et pas très sexy comme exercice. Ici le tableau est bien défini non vide donc pas de souci de division par zéro à traiter.
Comme le fait remarquer N. Bonnin : pourquoi préciser qu'il s'agit de flottants ?
1 2 3 4 5 | |
Écrire une fonction `moyenne` qui prend en paramètre un tableau non vide de nombres
flottants et qui renvoie la moyenne des valeurs du tableau. Les tableaux seront
représentés sous forme de liste Python.
Exemples :
```python
>>> moyenne([1.0])
1.0
>>> moyenne([1.0, 2.0, 4.0])
2.3333333333333335
```
Exercice 28.2 = 15.2
ATTENTION = 15.2
On considère la fonction dec_to_bin ci-dessous qui prend en paramètre un entier positif a en écriture décimale et qui renvoie son écriture binaire sous la forme d'une chaine de caractères.
1 2 3 4 5 6 7 | |
dec_to_bin.
Exemples :
>>> dec_to_bin(83)
'1010011'
>>> dec_to_bin(127)
'1111111'
Romain Janvier qui a relu ce sujet nous livre son verdict :
-
Je ne sais pas si la figure aide vraiment. Surtout que dans l’algo, on doit s’arrêter quand le quotient est 0 et dans la figure, on s’arrête lorsque a=1. En fait le dessin correspond à cette fonction :
def binaire(a): bin_a = "" while a > 1: bin_a = str(a%2) + bin_a a = a // 2 bin_a = str(a) + bin_a return bin_a -
J’ai des doutes sur le nom des variables. Je préfairais
nbetnb_bin, mais là, c’est du pinaillage. - Dans les exemples, c’est bien, il y a le cas 0 qui peut poser problème.
- Le code n’est pas très dur à remplir, même s’il n’est pas lisible par Python en l’état.
- Pour la ligne du
while, je mettrais bienwhile ...:.
Je le rejoins essentiellement sur la figure qui n'est pas adaptée (une autre est proposée dans l'énoncé modifié).
Pour rappel, la conversion d’un nombre entier positif en binaire peut s’effectuer à l’aide des divisions successives comme illustré ici :
Voici une fonction Python basée sur la méthode des divisions successives permettant de convertir un nombre entier positif en binaire :
1 2 3 4 5 6 7 | |
binaire.
Exemples :
>>> binaire(0)
'0'
>>> binaire(77)
'1001101'
1 2 3 4 5 6 7 | |
ATTENTION = 15.2
On considère la fonction `dec_to_bin` ci-dessous qui prend en paramètre un entier positif `a` en écriture décimale et qui renvoie son écriture binaire sous la forme d'une chaine de caractères.
```python linenums='1'
def dec_to_bin(a):
bin_a = ...
a = a//2
while a ... :
bin_a = ... + bin_a
a = ...
return bin_a
```
Compléter la fonction `dec_to_bin`.
Exemples :
```python
>>> dec_to_bin(83)
'1010011'
>>> dec_to_bin(127)
'1111111'
```
Sujet 29 ⚓︎
Sujet rejeté à cause de l'exercice 29.2 qui bafoue les règles élémentaires de programmation : une fonction qui ne fonctionne que pour 1 cas particulier !
Exercice 29.1
On s’intéresse à la suite d’entiers définie par
U1 = 1, U2 = 1 et, pour tout entier naturel n, par Un+2 = Un+1 + Un.
Elle s’appelle la suite de Fibonacci.
Écrire la fonction fibonacci qui prend un entier n > 0 et qui renvoie l’élément d’indice
n de cette suite.
On utilisera une programmation dynamique (pas de récursivité).
Exemple :
>>> fibonacci(1)
1
>>> fibonacci(2)
1
>>> fibonacci(25)
75025
>>> fibonacci(45)
1134903170
La suite de Fibonacci est un grand classique donc même si les suites ne sont pas connues des candidat-es ne faisant pas de mathématiques en spécialité, on peut s'attendre à ce que toutes et tous connaissent cette suite là.
Néanmoins on peut en faire une définition sans le formalisme de suite définie par récurrence.
D'autre part, la mention "On utilisera une programmation dynamique (pas de récursivité)" laisse perplexe. L'auteur-e du sujet voulait probablement dire : on utilisera une solution itérative.
Comme déjà mentionné, soit on propose un exercice 2, à trous parce qu'on a en tête un algorithme ; soit on propose un exercice 1 mais alors pourquoi tenter d'imposer une méthode de résolution ? Peut-être que le candidat ou la candidate aura vu la suite de Fibonacci justement dans le cadre de la récursivité, avec mémoïzation par exemple.
On s’intéresse à la suite d’entiers définie ainsi :
- les deux premiers termes sont 1 et 1
- chacun des suivants est obtenu par la somme des deux termes précédents
Elle s’appelle la suite de Fibonacci.
Écrire la fonction fibonacci qui prend un entier n > 0 et qui renvoie l’élément d’indice
n de cette suite.
Exemples :
>>> fibonacci(1)
1
>>> fibonacci(2)
1
>>> fibonacci(25)
75025
>>> fibonacci(45)
1134903170
1 2 3 4 5 | |
On s’intéresse à la suite d’entiers définie par
`U1 = 1`, `U2 = 1` et, pour tout entier naturel `n`, par `Un+2 = Un+1 + Un`.
Elle s’appelle la suite de Fibonacci.
Écrire la fonction `fibonacci` qui prend un entier `n > 0` et qui renvoie l’élément d’indice
`n` de cette suite.
On utilisera une programmation dynamique (pas de récursivité).
Exemple :
```python
>>> fibonacci(1)
1
>>> fibonacci(2)
1
>>> fibonacci(25)
75025
>>> fibonacci(45)
1134903170
```
Exercice 29.2
Les variables liste_eleves et liste_notes ayant été préalablement définies et étant
de même longueur, la fonction meilleures_notes renvoie la note maximale qui a été
attribuée, le nombre d’élèves ayant obtenu cette note et la liste des noms de ces élèves.
Compléter le code Python de la fonction meilleures_notes ci-dessous.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 | |
Une fois complété, le code ci-dessus donne
>>> meilleures_notes()
(80, 3, ['c', 'f', 'h'])
N. Bonnin pointe l'essentiel de ce qui ne va pas dans cet exercice :
- la fonction travaille sans paramètre et sur 2 variables globales.
Retrouvez l'ensemble de ses commentaires à propos du 29.2
On stocke dans deux tableaux, des élèves (identifiés pour simplifier par une seule lettre) et leurs notes.
La fonction meilleures_notes prend les deux tableaux, celui des élèves en premier paramètre et celui des notes en deuxième et renvoie la note maximale qui a été attribuée, ainsi que la liste des élèves ayant obtenus cette note.
Compléter le code Python de la fonction meilleures_notes ci-dessous.
1 2 3 4 5 6 7 8 9 10 11 12 | |
Exemples :
>>> eleves = ['a','b','c','d','e','f','g','h','i','j']
>>> notes = [1, 40, 80, 60, 58, 80, 75, 80, 60, 24]
>>> meilleures_notes(eleves, notes)
(80, ['c', 'f', 'h'])
1 2 3 4 5 6 7 8 9 10 11 | |
Les variables `liste_eleves` et `liste_notes` ayant été préalablement définies et étant
de même longueur, la fonction `meilleures_notes` renvoie la note maximale qui a été
attribuée, le nombre d’élèves ayant obtenu cette note et la liste des noms de ces élèves.
Compléter le code Python de la fonction `meilleures_notes` ci-dessous.
```python linenums='1'
liste_eleves = ['a','b','c','d','e','f','g','h','i','j']
liste_notes = [1, 40, 80, 60, 58, 80, 75, 80, 60, 24]
def meilleures_notes():
note_maxi = 0
nb_eleves_note_maxi = ...
liste_maxi = ...
for compteur in range(...):
if liste_notes[compteur] == ...:
nb_eleves_note_maxi = nb_eleves_note_maxi + 1
liste_maxi.append(liste_eleves[...])
if liste_notes[compteur] > note_maxi:
note_maxi = liste_notes[compteur]
nb_eleves_note_maxi = ...
liste_maxi = [...]
return (note_maxi,nb_eleves_note_maxi,liste_maxi)
```
Une fois complété, le code ci-dessus donne
```python
>>> meilleures_notes()
(80, 3, ['c', 'f', 'h'])
```
Sujet 30 ⚓︎
L'exercice 1 est déraisonnable : il est d'ailleurs proposé en exercice 2 dans un autre sujet (le 10).
Exercice 30.1 = 10.2
Programmer la fonction fusion prenant en paramètres deux tableaux non vides tab1 et tab2
(type list) d'entiers, chacun dans l’ordre croissant, et renvoyant un tableau trié dans l’ordre
croissant et contenant l’ensemble des valeurs de tab1 et tab2.
Exemples :
>>> fusion([3, 5], [2, 5])
[2, 3, 5, 5]
>>> fusion([-2, 4], [-3, 5, 10])
[-3, -2, 4, 5, 10]
>>> fusion([4], [2, 6])
[2, 4, 6]
Voir le 10.2
Programmer la fonction `fusion` prenant en paramètres deux tableaux non vides `tab1` et `tab2`
(type `list`) d'entiers, chacun dans l’ordre croissant, et renvoyant un tableau trié dans l’ordre
croissant et contenant l’ensemble des valeurs de `tab1` et `tab2`.
Exemples :
```python
>>> fusion([3, 5], [2, 5])
[2, 3, 5, 5]
>>> fusion([-2, 4], [-3, 5, 10])
[-3, -2, 4, 5, 10]
>>> fusion([4], [2, 6])
[2, 4, 6]
```
Exercice 30.2
Les chiffres romains sont un système ancien d’écriture des nombres.
Les chiffres romains sont: I, V, X, L, C, D, et M. Ces symboles représentent respectivement 1, 5, 10, 50, 100, 500, et 1000 en base dix.
Lorsque deux caractères successifs sont tels que le caractère placé à gauche possède une valeur supérieure ou égale à celui de droite, le nombre s’obtient en additionnant le caractère de gauche à la valeur de la chaîne située à droite.
Ainsi, "XVI" est le nombre 16 car X + VI = 10 + 6.
Lorsque deux caractères successifs sont tels que le caractère placé à gauche possède une valeur strictement inférieure à celui de droite, le nombre s’obtient en retranchant le caractère de gauche à la valeur de la chaîne située à droite.
Ainsi, "CDIII" est le nombre 403 car DIII – C = 503 – 100.
On dispose d’un dictionnaire dico, à compléter, où les clés sont les caractères apparaissant dans l’écriture en chiffres romains et où les valeurs sont les nombres entiers associés en écriture décimale.
On souhaite créer une fonction récursive rom_to_dec qui prend en paramètre une chaîne de
caractères (non vide) représentant un nombre écrit en chiffres romains et renvoyant le nombre
associé en écriture décimale :
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 | |
N. Bonnin note que l'énoncé pourrait être un peu plus propre au niveau de la formulation (on parle d'additionner des nombres et des caractères). Il y a aussi un regret de ne pas voir plus de valeurs données pour le dictionnaire des association chiffres romains - décimaux.
Il manque des exemples.
Source : commentaires à propos du 30.2
Une maladresse notable : le dictionnaire qui devrait être une constante est définie à l'intérieur d'une fonction récursive. Cela signifie qu'à chaque appel ce dictionnaire sera recréé. A corriger absolument.
Les chiffres romains sont un système ancien d’écriture des nombres.
Les chiffres romains sont: I, V, X, L, C, D, et M. Ces symboles représentent respectivement 1, 5, 10, 50, 100, 500, et 1000 en base dix.
Cette association pourra être modélisée par un dictionnaire défini une fois pour toute (une constante). Vous complèterez le dictionnaire dont on vous donne le début ci-dessous :
ROMAIN_DEC = {"I":1, "V":5, "X":10, "L":50, ...}
Lorsque deux caractères successifs sont tels que le caractère placé à gauche possède une valeur supérieure ou égale à celui de droite, le nombre s’obtient en additionnant la valeur du caractère de gauche à la valeur de la chaîne située à droite.
Ainsi, "XVI" est le nombre 16 (10 + 6) car X vaut 10 > à 5 qui est la valeur de V.
Lorsque deux caractères successifs sont tels que le caractère placé à gauche possède une valeur strictement inférieure à celui de droite, le nombre s’obtient en retranchant la valeur du caractère de gauche à la valeur de la chaîne située à droite.
Ainsi, "CDIII" est le nombre 403 (503 - 100) car 100 (la valeur de C) est inférieure strictement à 500 (la valeur de D).
On souhaite créer une fonction récursive rom_to_dec qui prend en paramètre une chaîne de
caractères (non vide) représentant un nombre écrit en chiffres romains et renvoyant le nombre
associé en écriture décimale :
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 | |
ROMAIN_DEC = {"I":1, "V":5, "X":10, "L":50, "C":100, "D":500, "M":1000}
def rom_to_dec(nombre):
""" Renvoie l’écriture décimale du nombre donné en chiffres romains """
if len(nombre) == 1:
return ROMAIN_DEC[nombre]
else:
# on supprime le premier caractère de la chaîne contenue dans la variable nombre
# et cette nouvelle chaîne est enregistrée dans la variable nombre_droite
nombre_droite = nombre[1:]
if ROMAIN_DEC[nombre[0]] >= ROMAIN_DEC[nombre[1]]:
return ROMAIN_DEC[nombre[0]] + rom_to_dec(nombre_droite)
else:
return rom_to_dec(nombre_droite) - ROMAIN_DEC[nombre[0]]
Les chiffres romains sont un système ancien d’écriture des nombres.
Les chiffres romains sont: I, V, X, L, C, D, et M.
Ces symboles représentent respectivement 1, 5, 10, 50, 100, 500, et 1000 en base dix.
Lorsque deux caractères successifs sont tels que le caractère placé à gauche possède une
valeur supérieure ou égale à celui de droite, le nombre s’obtient en additionnant le caractère de
gauche à la valeur de la chaîne située à droite.
Ainsi, "XVI" est le nombre 16 car X + VI = 10 + 6.
Lorsque deux caractères successifs sont tels que le caractère placé à gauche possède une
valeur strictement inférieure à celui de droite, le nombre s’obtient en retranchant le caractère de
gauche à la valeur de la chaîne située à droite.
Ainsi, "CDIII" est le nombre 403 car DIII – C = 503 – 100.
On dispose d’un dictionnaire dico, à compléter, où les clés sont les caractères apparaissant
dans l’écriture en chiffres romains et où les valeurs sont les nombres entiers associés en
écriture décimale.
On souhaite créer une fonction récursive `rom_to_dec` qui prend en paramètre une chaîne de
caractères (non vide) représentant un nombre écrit en chiffres romains et renvoyant le nombre
associé en écriture décimale :
```python linenums='1'
def rom_to_dec (nombre):
""" Renvoie l’écriture décimale du nombre donné en chiffres romains """
dico = {"I":1, "V":5, ...}
if len(nombre) == 1:
return ...`
else:
### on supprime le premier caractère de la chaîne contenue dans la variable nombre
### et cette nouvelle chaîne est enregistrée dans la variable nombre_droite
nombre_droite = nombre[1:]
if dico[nombre[0]] >= dico[nombre[1]]:
return dico[nombre[0]] + ...
else:
return ...
assert rom_to_dec("CXLII") == 142
```
Sujet 31 ⚓︎
Pour l'exercice 2, il faut se référer au sujet 1, exercice 2. Cet version complexifie inutilement les choses et donc à ne pas prendre.
Exercice 31.1
Écrire en langage Python une fonction recherche prenant comme paramètres une
variable a de type numérique (float ou int) et un tableau t (type list) et qui
renvoie le nombre d'occurrences de a dans t.
Exemples :
>>> recherche(5,[])
0
>>> recherche(5,[-2, 3, 4, 8])
0
>>> recherche(5,[-2, 3, 1, 5, 3, 7, 4])
1
>>> recherche(5,[-2, 5, 3, 5, 4, 5])
3
R. Janvier :
- Encore une fonction recherche… C’est pour embrouiller les élèves qui apprennent par coeur les solutions sans rien comprendre ?
- Le sujet se restreint aux données numériques, mais pourquoi ? On pourrait donner des exemples avec des textes. Il manque un exemple ou la valeur cherchée est en première position, au cas où.
Source : commentaires à propos du 31.1
Effectivement il s'agit d'une fonction nb_occurrences qui fonctionne pas uniquement avec des valeurs numériques.
Écrire en langage Python une fonction nb_occurrences prenant comme paramètres une valeur element
et un tableau tableau (type list) et qui renvoie le nombre d'occurrences de element dans tableau.
Exemples :
>>> nb_occurrences(5, [])
0
>>> nb_occurrences(5, [5, 3, 4, 8])
1
>>> nb_occurrences('a', ['b', 'a', 'a', 'a', 'c'])
3
>>> nb_occurrences(True, [False, False, True])
1
1 2 3 4 5 6 | |
Bien sûr on s'expose à cette réponse :
def nb_occurrences(element, tableau):
return tableau.count(element)
Écrire en langage Python une fonction `recherche` prenant comme paramètres une
variable `a` de type numérique (`float` ou `int`) et un tableau `t` (type `list`) et qui
renvoie le nombre d'occurrences de `a` dans `t`.
Exemples :
```python
>>> recherche(5,[])
0
>>> recherche(5,[-2, 3, 4, 8])
0
>>> recherche(5,[-2, 3, 1, 5, 3, 7, 4])
1
>>> recherche(5,[-2, 5, 3, 5, 4, 5])
3
```
Exercice 31.2 = 01.2
La fonction rendu_monnaie_centimes prend en paramètres deux nombres entiers
positifs s_due ets_versee et elle permet de procéder au rendu de monnaie de la
différence s_versee – s_due pour des achats effectués avec le système de pièces de
la zone Euro. On utilise pour cela un algorithme qui commence par rendre le maximum de
pièces de plus grandes valeurs et ainsi de suite. La fonction renvoie la liste des pièces qui
composent le rendu.
Toutes les sommes sont exprimées en centimes d’euros. Les valeurs possibles pour les
pièces sont donc [1, 2, 5, 10, 20, 50, 100, 200].
Ainsi, l’instruction rendu_monnaie_centimes(452, 500)
renverra
[20, 20, 5, 2, 1].
En effet, la somme à rendre est de 48 centimes soit 20 + 20 + 5 + 2 + 1.
Le code de la fonction est donné ci-dessous :
1 2 3 4 5 6 7 8 9 10 11 12 | |
Compléter ce code pour qu'il donne :
>>> rendu_monnaie_centimes(700,700)
[]
>>> rendu_monnaie_centimes(112,500)
[200, 100, 50, 20, 10, 5, 2, 1]
R. Janvier :
- Il y a 2 paramètres : la somme à rendre et ce qui est déjà rendu. Mais quel intérêt ? Pour une fonction récursive, pourquoi pas ?
- On met tout en centimes, mais pourquoi ne pas juste rester sur les euros ? Là aussi, on complexifie pour pas grand chose.
- Et puis les valeurs sont dans l’ordre croissant. Donc il faut partir de la fin de la liste.
- Il manque des exemples où on utilise plusieurs fois la même pièce.
- Passable mais compliqué pour pas grand chose. À simplifier
Source : commentaires à propos du 31.2
L'exercice a été donné en sujet 1. La version corrigée va simplement reprendre celle de ce sujet.
On s’intéresse à un algorithme récursif qui permet de rendre la monnaie à partir d’une liste donnée de valeurs de pièces et de billets.
Le système monétaire est donné sous forme d’une liste :
pieces = [100, 50, 20, 10, 5, 2, 1]
On supposera qu’il n’y a pas de limitation quant à leur nombre.
On cherche à donner la liste de pièces à rendre pour une somme donnée en argument. Compléter le code Python ci-dessous de la fonction rendu_glouton qui implémente cet
algorithme et renvoie la liste des pièces à rendre.
1 2 3 4 5 6 7 8 9 10 11 | |
On devra obtenir :
>>> rendu_glouton(68, [], 0)
[50, 10, 5, 2, 1]
>>> rendu_glouton(291, [], 0)
[100, 100, 50, 20, 20, 1]
G. Connan propose un certain nombre de corrections sur sa page.
La version attendue (sans la valeur par défaut) et en mettant les espaces correctement :
1 2 3 4 5 6 7 8 9 10 11 | |
Sachant que cette fonction s'appelle toujours avec la liste vide en deuxième paramètre et 0 a priori en 3e... sauf si on sait qu'on n'a plus de billets de 100.
G. Connan ne détaille pas celle avec la fonction auxiliaire , et pour cause : la fonction en question n'a aucun sens hors la fonction principale et devrait donc être définie à l'intérieur de cette-dernière ce qui fait un code complètement hors-programme :
def rendu_glouton(a_rendre):
def rendu_glouton_aux(a_rendre, solution, i):
if a_rendre == 0:
return solution
piece = pieces[i]
if piece <= a_rendre:
solution.append(piece)
return rendu_glouton_aux(a_rendre - piece, solution, i)
else:
return rendu_glouton_aux(a_rendre, solution, i+1)
pieces = [100, 50, 20, 10, 5, 2, 1]
return rendu_glouton_aux(a_rendre, [], 0)
Version plus générique, avec la liste des pièces en paramètre :
def rendu_glouton(a_rendre, pieces):
def rendu_glouton_aux(a_rendre, solution, i):
if a_rendre == 0:
return solution
elif i >= len(pieces):
return None
else:
piece = pieces[i]
if piece <= a_rendre:
solution.append(piece)
return rendu_glouton_aux(a_rendre - piece, solution, i)
else:
return rendu_glouton_aux(a_rendre, solution, i+1)
return rendu_glouton_aux(a_rendre, [], 0)
Exemples :
>>> rendu_glouton(291, [100, 50, 20, 10, 5, 2, 1])
[100, 100, 50, 20, 20, 1]
>>> rendu_glouton(291, [50, 20, 10, 2, 1])
[50, 50, 50, 50, 50, 20, 20, 1]
>>> rendu_glouton(291, [50, 20, 10, 2])
None
La fonction `rendu_monnaie_centimes` prend en paramètres deux nombres entiers
positifs `s_due` et` s_versee` et elle permet de procéder au rendu de monnaie de la
différence `s_versee – s_due` pour des achats effectués avec le système de pièces de
la zone Euro. On utilise pour cela un algorithme qui commence par rendre le maximum de
pièces de plus grandes valeurs et ainsi de suite. La fonction renvoie la liste des pièces qui
composent le rendu.
Toutes les sommes sont exprimées en centimes d’euros. Les valeurs possibles pour les
pièces sont donc `[1, 2, 5, 10, 20, 50, 100, 200]`.
Ainsi, l’instruction `rendu_monnaie_centimes(452, 500)`
renverra
`[20, 20, 5, 2, 1]`.
En effet, la somme à rendre est de `48` centimes soit `20 + 20 + 5 + 2 + 1`.
Le code de la fonction est donné ci-dessous :
```python linenums='1'
def rendu_monnaie_centimes(s_due, s_versee):
pieces = [1, 2, 5, 10, 20, 50, 100, 200]
rendu = ...
a_rendre = ...
i = len(pieces) - 1
while a_rendre > ... :
if pieces[i] <= a_rendre :
rendu.append(...)
a_rendre = ...
else :
i = ...
return rendu
```
Compléter ce code pour qu'il donne :
```python
>>> rendu_monnaie_centimes(700,700)
[]
>>> rendu_monnaie_centimes(112,500)
[200, 100, 50, 20, 10, 5, 2, 1]
```
Sujet 32 ⚓︎
L'exercice 2, est le seul qui tente quelque chose en liaison avec un autre thème du programme NSI (le réseau), mais la réalisation n'est pas aboutie. Au final le sujet n'a pratiquement aucun intérêt.
Exercice 32.1
Écrire une fonction recherche qui prend en paramètres elt un nombre entier et tab
un tableau de nombres entiers, et qui renvoie l’indice de la première occurrence de elt
dans tab si elt est dans tab et -1 sinon.
Exemples :
>>> recherche(1, [2, 3, 4])
-1
>>> recherche(1, [10, 12, 1, 56])
2
>>> recherche(50, [1, 50, 1])
1
>>> recherche(15, [8, 9, 10, 15])
3
R. Janvier :
- Encore une fonction recherche…
- Sinon, ça change un peu.
- Il manque un exemple où la dernière occurrence est à la position 0.
- Ok
Source : commentaires à propos du 32.1
Certains ne sont pas ok pour la valeur -1 comme valeur de retour en cas d'absence de l'élément recherché. C'est pourtant ce que retourne la fonction Python find. Là je pense que les avis seront partagés, en fonction des habitudes des un-es et des autres et surtout des pratiques avecles élèves.
1 2 3 4 5 6 7 8 9 10 11 12 | |
Écrire une fonction `recherche` qui prend en paramètres `elt` un nombre entier et `tab`
un tableau de nombres entiers, et qui renvoie l’indice de la première occurrence de `elt`
dans `tab` si `elt` est dans `tab` et `-1` sinon.
Exemples :
```python
>>> recherche(1, [2, 3, 4])
-1
>>> recherche(1, [10, 12, 1, 56])
2
>>> recherche(50, [1, 50, 1])
1
>>> recherche(15, [8, 9, 10, 15])
3
```
Exercice 32.2
On définit une classe gérant une adresse IPv4.
On rappelle qu’une adresse IPv4 est une adresse de longueur 4 octets, notée en décimale
à point, en séparant chacun des octets par un point. On considère un réseau privé avec
une plage d’adresses IP de 192.168.0.0 à 192.168.0.255.
On considère que les adresses IP saisies sont valides.
Les adresses IP 192.168.0.0 et 192.168.0.255 sont des adresses réservées.
Le code ci-dessous implémente la classe AdresseIP.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 | |
adresse1, adresse2,
adresse3 avec respectivement les arguments suivants :
'192.168.0.1', '192.168.0.2', '192.168.0.0'
Vérifier que :
>>> adresse1.est_reservee()
False
>>> adresse3.est_reservee()
True
>>> adresse2.adresse_suivante().adresse
'192.168.0.3'
R. Janvier :
- Encore une fonction recherche…
- Sinon, ça change un peu.
- Il manque un exemple où la dernière occurrence est à la position 0.
- Ok
Source : commentaires à propos du 32.1
Certains ne sont pas ok pour la valeur -1 comme valeur de retour en cas d'absence de l'élément recherché. C'est pourtant ce que retourne la fonction Python find. Là je pense que les avis seront partagés, en fonction des habitudes des un-es et des autres et surtout des pratiques avecles élèves.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 | |
On définit une classe gérant une adresse IPv4.
On rappelle qu’une adresse IPv4 est une adresse de longueur 4 octets, notée en décimale
à point, en séparant chacun des octets par un point. On considère un réseau privé avec
une plage d’adresses IP de `192.168.0.0` à `192.168.0.255`.
On considère que les adresses IP saisies sont valides.
Les adresses IP `192.168.0.0` et `192.168.0.255` sont des adresses réservées.
Le code ci-dessous implémente la classe `AdresseIP`.
```python linenums='1'
class AdresseIP:
def __init__(self, adresse):
self.adresse = ...
def liste_octet(self):
"""renvoie une liste de nombres entiers,
la liste des octets de l'adresse IP"""
return [int(i) for i in self.adresse.split(".")]
def est_reservee(self):
"""renvoie True si l'adresse IP est une adresse
réservée, False sinon"""
return ... or ...
def adresse_suivante(self):
"""renvoie un objet de AdresseIP avec l'adresse
IP qui suit l’adresse self
si elle existe et False sinon"""
if ... < 254:
octet_nouveau = ... + ...
return AdresseIP('192.168.0.' + ...)
else:
return False
```
Compléter le code ci-dessus et instancier trois objets : `adresse1`, `adresse2`,
`adresse3` avec respectivement les arguments suivants :
`'192.168.0.1'`, `'192.168.0.2'`, `'192.168.0.0'`
Vérifier que :
```python
>>> adresse1.est_reservee()
False
>>> adresse3.est_reservee()
True
>>> adresse2.adresse_suivante().adresse
'192.168.0.3'
```
Sujet 33 ⚓︎
Sujet problématique, à ne surtout pas prendre.
Exercice 33.1
On modélise la représentation binaire d'un entier non signé par un tableau d'entiers dont
les éléments sont 0 ou 1. Par exemple, le tableau [1, 0, 1, 0, 0, 1, 1] représente
l'écriture binaire de l'entier dont l'écriture décimale est
2**6 + 2**4 + 2**1 + 2**0 = 83.
À l'aide d'un parcours séquentiel, écrire la fonction convertir répondant aux spécifications suivantes :
def convertir(T):
"""
T est un tableau d'entiers, dont les éléments sont 0 ou 1 et
représentant un entier écrit en binaire. Renvoie l'écriture
décimale de l'entier positif dont la représentation binaire
est donnée par le tableau T
"""
>>> convertir([1, 0, 1, 0, 0, 1, 1])
83
>>> convertir([1, 0, 0, 0, 0, 0, 1, 0])
130
Commentaires de R. Janvier :
Est-ce que ce n'est pas trop dur pour un exercice 1 ?
Le sujet propose d'utiliser les puissances de 2. Sauf que je pense que mes élèves non matheux sont incapables de trouver la formule de l'exposant pour la puissance, même si elle est triviale.
Surtout que je n'ai utilisé que la méthode de Horner avec eux (ok, j'ai dû faire 1 fois les puissances en début de 1e), mais je ne pense pas que les non matheux, encore eux, puisse retrouver la méthode tous seuls.
Cela devrait être un exercice 2, avec du code à compléter, même si, il est vrai que ça fait une fonction très courte.
Au moins, comme on utilise une liste d'entier, on évite les conversions entre str et int.
Il manque des tests avec 0 ou 1.
Et on pourrait mettre tab au lieu de T.
Problématique.
On modélise la représentation binaire d'un entier non signé par un tableau d'entiers dont
les éléments sont 0 ou 1. Par exemple, le tableau [1, 0, 1, 0, 0, 1, 1] représente
l'écriture binaire de l'entier dont l'écriture décimale est
2**6 + 2**4 + 2**1 + 2**0 = 83.
À l'aide d'un parcours séquentiel, écrire la fonction convertir répondant aux spécifications suivantes :
def convertir(tab):
"""
tab est un tableau d'entiers, dont les éléments sont 0 ou 1 et
représentant un entier écrit en binaire. Renvoie l'écriture
décimale de l'entier positif dont la représentation binaire
est donnée par le tableau tab
"""
>>> convertir([1, 0, 1, 0, 0, 1, 1])
83
>>> convertir([1, 0, 0, 0, 0, 0, 1, 0])
130
>>> convertir([0])
0
>>> convertir([1])
1
Version probablement attendue :
1 2 3 4 5 6 7 | |
Version avec la méthode de Horner :
1 2 3 4 5 | |
On modélise la représentation binaire d'un entier non signé par un tableau d'entiers dont
les éléments sont 0 ou 1. Par exemple, le tableau `[1, 0, 1, 0, 0, 1, 1]` représente
l'écriture binaire de l'entier dont l'écriture décimale est
`2**6 + 2**4 + 2**1 + 2**0 = 83`.
À l'aide d'un parcours séquentiel, écrire la fonction convertir répondant aux
spécifications suivantes :
```python
def convertir(T):
"""
T est un tableau d'entiers, dont les éléments sont 0 ou 1 et
représentant un entier écrit en binaire. Renvoie l'écriture
décimale de l'entier positif dont la représentation binaire
est donnée par le tableau T
"""
```
Exemple :
```python
>>> convertir([1, 0, 1, 0, 0, 1, 1])
83
>>> convertir([1, 0, 0, 0, 0, 0, 1, 0])
130
```
Exercice 33.2
La fonction tri_insertion suivante prend en argument une liste L et trie cette liste en
utilisant la méthode du tri par insertion. Compléter cette fonction pour qu'elle réponde à la
spécification demandée.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 | |
Exemples :
>>> tri_insertion([2,5,-1,7,0,28])
[-1, 0, 2, 5, 7, 28]
>>> tri_insertion([10,9,8,7,6,5,4,3,2,1,0])
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
Commentaires de R. Janvier :
Encore une fois, des return qui n'ont aucun intérêt.
On traite le cas vide à part alors qu'on ne rentre juste pas dans la boucle, donc aucun intérêt.
Il y a un problème d'indentation des commentaires qui fait croire que la boucle est finie plus tôt que prévue.
On fait 2 parcours pour trouver la position où insérer la valeur.
Les variables ont des noms trop courts.
Comment se souvenir que e sert à conserver la valeur de L[j] pour la remettre à la fin. Perso, j'ai dû chercher.
On demande de rajouter le -1 dans un range pour faire un compte à rebours. Pas sûr que ce soit au programme.
Mal foutu et compliqué. Les élèves vont peut-être trouver en tatonnant, mais est-ce que c'est ce qu'on veut encourager ?
Franchement, ce problème se règle en 6 lignes.
Pourquoi en mettre 2 fois plus en étant moins clair ?
Problématique.
Version avec peu de modifs
La fonction tri_insertion suivante prend en argument une liste L et trie cette liste en
utilisant la méthode du tri par insertion. Compléter cette fonction pour qu'elle réponde à la
spécification demandée.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 | |
Exemples :
>>> tri_insertion([2, 5, -1, 7, 0, 28])
[-1, 0, 2, 5, 7, 28]
>>> tri_insertion([10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0])
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
Version avec plus de modifs
La fonction tri_insertion suivante prend en argument un tableau tab et trie ce tableau en
utilisant la méthode du tri par insertion. Compléter cette fonction pour qu'elle réponde à la
spécification demandée.
1 2 3 4 5 6 7 8 9 10 | |
Exemples :
>>> tri_insertion([2, 5, -1, 7, 0, 28])
[-1, 0, 2, 5, 7, 28]
>>> tri_insertion([10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0])
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 | |
La fonction `tri_insertion` suivante prend en argument une liste `L` et trie cette liste en
utilisant la méthode du tri par insertion. Compléter cette fonction pour qu'elle réponde à la
spécification demandée.
```python linenums='1'
def tri_insertion(L):
n = len(L)
# cas du tableau vide
if ...:
return L
for j in range(1,n):
e = L[j]
i = j
# A l'étape j, le sous-tableau L[0,j-1] est trié
# et on insère L[j] dans ce sous-tableau en déterminant
# le plus petit i tel que 0 <= i <= j et L[i-1] > L[j].
while i > 0 and L[i-1] > ...:
i = ...
# si i != j, on décale le sous tableau L[i,j-1] d’un cran
# vers la droite et on place L[j] en position i
if i != j:
for k in range(j,i,...):
L[k] = L[...]
L[i] = ...
return L
```
Exemples :
```python
>>> tri_insertion([2,5,-1,7,0,28])
[-1, 0, 2, 5, 7, 28]
>>> tri_insertion([10,9,8,7,6,5,4,3,2,1,0])
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
```
Sujet 34 ⚓︎
Sujet problématique à cause de la difficulté de l'exercice 1. À ne pas donner.
Exercice 34.1
Écrire une fonction occurrence_max prenant en paramètres une chaîne de caractères
chaine et qui renvoie le caractère le plus fréquent de la chaîne. La chaine ne contient
que des lettres en minuscules sans accent.
On pourra s’aider du tableau
alphabet = ['a','b','c','d','e','f','g','h','i','j','k','l','m','n','o,','p','q','r','s','t','u','v','w','x','y','z']
et du tableau occurrence de 26 éléments où l’on mettra dans occurrence[i] le
nombre d’apparitions de alphabet[i] dans la chaine.
Puis on calculera l’indice k d’un maximum du tableau occurrence et on affichera alphabet[k].
Exemple :
>>> ch = 'je suis en terminale et je passe le bac et je souhaite poursuivre des etudes pour devenir expert en informatique'
>>> occurrence_max(ch)
‘e’
Il y a une virgule en trop dans 'o,'.
On oblige à utiliser des tableaux alors que les dictionnaires sont plus pratiques pour cela.
On ne rappelle pas l'usage de index qui est indispensable avec les tableaux.
En fait on a un peu 2 exercices en 1 : compter les occurrences et chercher le max.
Ok, on peut faire les 2 en même temps, mais quand dans d'autres sujets on ne demande de traiter qu'un seul de ces problèmes, cela pique un peu.
Surtout que pour compter les occurrences avec les tableaux, c'est bien plus compliqué, surtout pour les élèves en difficulté.
À la rigueur, on pourrait donner le tableau des occurrences et demander le lettre qui apparaît le plus. Ou juste demander le tableau des occurrences.
Problématique.
Écrire une fonction occurrence_max prenant en paramètres une chaîne de caractères
chaine et qui renvoie le caractère le plus fréquent de la chaîne. La chaine ne contient
que des lettres en minuscules sans accent.
On pourra s’aider du tableau
alphabet = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i',
'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r',
's', 't', 'u', 'v', 'w', 'x', 'y', 'z']
et du tableau occurrence de 26 éléments où l’on mettra dans occurrence[i] le
nombre d’apparitions de alphabet[i] dans la chaîne.
Puis on calculera l’indice k d’un maximum du tableau occurrence et on affichera alphabet[k].
On pourra également utiliser un dictionnaire associant chaque lettre à son nombre d'occurrences et déterminer la clé associée à la plus grande valeur.
Exemple :
>>> ch = 'je suis en terminale et je passe le bac et je souhaite poursuivre des etudes pour devenir expert en informatique'
>>> occurrence_max(ch)
‘e’
Version attendue :
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 | |
Version avec index :
1 2 3 4 5 6 7 8 9 10 11 12 | |
Version avec un dictionnaire :
1 2 3 4 5 6 7 8 9 | |
Écrire une fonction `occurrence_max` prenant en paramètres une chaîne de caractères
`chaine` et qui renvoie le caractère le plus fréquent de la chaîne. La chaine ne contient
que des lettres en minuscules sans accent.
On pourra s’aider du tableau
`alphabet = ['a','b','c','d','e','f','g','h','i','j','k','l','m','n','o,','p','q','r','s','t','u','v','w','x','y','z']`
et du tableau `occurrence` de 26 éléments où l’on mettra dans `occurrence[i]` le
nombre d’apparitions de `alphabet[i]` dans la chaine.
Puis on calculera l’indice `k` d’un maximum du tableau `occurrence` et on affichera `alphabet[k]`.
Exemple :
```python
>>> ch = 'je suis en terminale et je passe le bac et je souhaite poursuivre des etudes pour devenir expert en informatique'
>>> occurrence_max(ch)
‘e’
```
Exercice 34.2
On considère une image en 256 niveaux de gris que l’on représente par une grille de nombres, c’est-à-dire une liste composée de sous-listes toutes de longueurs identiques.
La largeur de l’image est donc la longueur d’une sous-liste et la hauteur de l’image est le nombre de sous-listes.
Chaque sous-liste représente une ligne de l’image et chaque élément des sous-listes est un entier compris entre 0 et 255, représentant l’intensité lumineuse du pixel.
Le négatif d’une image est l’image constituée des pixels x_n tels que x_n + x_i = 255
où x_i est le pixel correspondant de l’image initiale.
Compléter le programme ci-dessous :
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 | |
Exemple :
>>> img = [[20, 34, 254, 145, 6], [23, 124, 287, 225, 69], [197, 174, 207, 25, 87], [255, 0, 24, 197, 189]]
>>> nbLig(img)
4
>>> nbCol(img)
5
>>> negatif(img)
[[235, 221, 1, 110, 249], [232, 131, -32, 30, 186], [58, 81, 48, 230, 168], [0, 255, 231, 58, 66]]
>>> binaire(negatif(img),120)
[[1, 1, 0, 0, 1], [1, 1, 0, 0, 1], [0, 0, 0, 1, 1], [0, 1, 1, 0, 0]]
Commentaires de R. Janvier :
Sur le principe c'est intéressant, mais je le trouve hyper dur pour les élèves faibles.
Il faudrait donner les fonctions nbCol et nbLig. La dernière est introuvable pour certains élèves plus faibles. On utilise peu les tableaux en 2D en Tle (les graphes ne sont pas au programme du bac) et donc c'est le genre de détails que les élèves oublient.
Contentons nous de la manipulation de image[i][j] sans demander la hauteur et surtout la largeur.
En plus dans negatif on utilise len(image) au lieu de nbLig(image).
Ils ont corrigé une erreur qu'il y avait dans le sujet de l'année dernière dans la fonction binaire et rajouté une précision sur le calcul du négatif.
Par contre l'exemple de binaire est faux puisqu'il correspond au négatif et pas à img.
Et il y a une valeur supérieure à 255 dans l'exemple.
Je ne parle pas du nom des fonctions...
Problématique.
La partie intéressante est très facile alors que les fonctions annexes sont potentiellement trop difficiles.
Il vaudrait mieux rajouter une fonction pour le miroir horizontal ou vertical, qui demande de la réflexion plus que des connaissances.
J'ai modifié un peu l'énoncé, mais on voit bien que c'est 2 fois la même chose. Il manque vraiment un travail à faire sur les indices.
On considère une image en 256 niveaux de gris que l’on représente par une grille de nombres, c’est-à-dire une liste composée de sous-listes toutes de longueurs identiques.
La largeur de l’image est donc la longueur d’une sous-liste et la hauteur de l’image est le nombre de sous-listes.
Chaque sous-liste représente une ligne de l’image et chaque élément des sous-listes est un entier compris entre 0 et 255, représentant l’intensité lumineuse du pixel.
Le négatif d’une image est l’image constituée des pixels x_n tels que x_n + x_i = 255
où x_i est le pixel correspondant de l’image initiale.
Compléter les fonctions ci-dessous :
1 2 3 4 5 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 | |
Exemple :
>>> img = [[20, 34, 254, 145, 6], [23, 124, 217, 225, 69], [197, 174, 207, 25, 87], [255, 0, 24, 197, 189]]
>>> nbLig(img)
4
>>> nbCol(img)
5
>>> negatif(img)
[[235, 221, 1, 110, 249], [232, 131, 38, 30, 186], [58, 81, 48, 230, 168], [0, 255, 231, 58, 66]]
>>> binaire(negatif(img), 120)
[[0, 0, 1, 1, 0], [0, 0, 1, 1, 0], [1, 1, 1, 0, 0], [1, 0, 0, 1, 1]]
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 | |
On considère une image en 256 niveaux de gris que l’on représente par une grille de
nombres, c’est-à-dire une liste composée de sous-listes toutes de longueurs identiques.
La largeur de l’image est donc la longueur d’une sous-liste et la hauteur de l’image est le
nombre de sous-listes.
Chaque sous-liste représente une ligne de l’image et chaque élément des sous-listes est
un entier compris entre 0 et 255, représentant l’intensité lumineuse du pixel.
Le négatif d’une image est l’image constituée des pixels `x_n` tels que `x_n + x_i = 255`
où `x_i` est le pixel correspondant de l’image initiale.
Compléter le programme ci-dessous :
```python linenums='1'
def nbLig(image):
'''renvoie le nombre de lignes de l'image'''
return ...
def nbCol(image):
'''renvoie la largeur de l'image'''
return ...
def negatif(image):
'''renvoie le négatif de l'image sous la forme d'une liste de listes'''
L = [[0 for k in range(nbCol(image))] for i in range(nbLig(image))] # on créé une image de 0 aux mêmes dimensions que le paramètre image
for i in range(len(image)):
for j in range(...):
L[i][j] = ...
return L
def binaire(image, seuil):
'''renvoie une image binarisée de l'image sous la forme
d'une liste de listes contenant des 0 si la valeur
du pixel est strictement inférieure au seuil
et 1 sinon'''
L = [[0 for k in range(nbCol(image))] for i in range(nbLig(image))] # on crée une image de 0 aux mêmes dimensions que le paramètre image
for i in range(len(image)):
for j in range(...):
if image[i][j] < ... :
L[i][j] = ...
else:
L[i][j] = ...
return L
```
Exemple :
```python
>>> img = [[20, 34, 254, 145, 6], [23, 124, 287, 225, 69], [197, 174, 207, 25, 87], [255, 0, 24, 197, 189]]
>>> nbLig(img)
4
>>> nbCol(img)
5
>>> negatif(img)
[[235, 221, 1, 110, 249], [232, 131, -32, 30, 186], [58, 81, 48, 230, 168], [0, 255, 231, 58, 66]]
>>> binaire(negatif(img),120)
[[1, 1, 0, 0, 1], [1, 1, 0, 0, 1], [0, 0, 0, 1, 1], [0, 1, 1, 0, 0]]
```
Sujet 35 ⚓︎
Sujet passable, mais il faudrait simplifier l'exercice 2.
Exercice 35.1
Écrire une fonction qui prend en paramètre un tableau d'entiers non vide et qui renvoie la moyenne de ces entiers. La fonction est spécifiée ci-après et doit passer les assertions fournies.
def moyenne (tab):
'''
moyenne(list) -> float
Entrée : un tableau non vide d'entiers
Sortie : nombre de type float
Correspondant à la moyenne des valeurs présentes dans le
tableau
'''
assert moyenne([1]) == 1
assert moyenne([1,2,3,4,5,6,7] == 4
assert moyenne([1,2]) == 1.5
Rien de spécial à dire.
1 2 3 4 5 6 7 8 9 10 11 12 | |
Écrire une fonction qui prend en paramètre un tableau d'entiers non vide et qui renvoie la
moyenne de ces entiers. La fonction est spécifiée ci-après et doit passer les assertions
fournies.
```python
def moyenne (tab):
'''
moyenne(list) -> float
Entrée : un tableau non vide d'entiers
Sortie : nombre de type float
Correspondant à la moyenne des valeurs présentes dans le
tableau
'''
assert moyenne([1]) == 1
assert moyenne([1,2,3,4,5,6,7] == 4
assert moyenne([1,2]) == 1.5
```
Exercice 35.2
Le but de l'exercice est de compléter une fonction qui détermine si une valeur est présente dans un tableau de valeurs triées dans l'ordre croissant.
L'algorithme traite le cas du tableau vide.
L'algorithme est écrit pour que la recherche dichotomique ne se fasse que dans le cas où la valeur est comprise entre les valeurs extrêmes du tableau.
On distingue les trois cas qui renvoient False en renvoyant False,1 , False,2 et
False,3.
Compléter l'algorithme de dichotomie donné ci-après.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 | |
Exemples :
>>> dichotomie([15, 16, 18, 19, 23, 24, 28, 29, 31, 33],28)
True
>>> dichotomie([15, 16, 18, 19, 23, 24, 28, 29, 31, 33],27)
(False, 3)
>>> dichotomie([15, 16, 18, 19, 23, 24, 28, 29, 31, 33],1)
(False, 2)
>>> dichotomie([],28)
(False, 1)
R. Janvier propose :
Problème dans la sortie. Soit un boolén, soit un couple (booléen, entier). D'ailleurs, le type de la fonction n'est pas donné dans le Docstring comme dans l'exerice 1... À la rigueur, on peut renvoyer
(True, 0)quand on trouve la valeur. Ou(True, indice)pour indiquer la position où on a trouvé la valeur. Mais en fait, on complexifie juste la fonction pour rien du tout. Quel intérêt de distinguer le cas vide ou le cas où la valeur est trop petite ou trop grande ? Si on veut complexifier la dichotomie, on pourrait regarder le nombre d'essais faits. Mais on ne pourrait pas attendre de voir comment s'en sortent les élèves avant de rajouter des variations arbitraires ? Il manque des espaces après les virgules.
Version avec peu de modifs
Le but de l'exercice est de compléter une fonction qui détermine si une valeur est présente dans un tableau de valeurs triées dans l'ordre croissant.
L'algorithme traite le cas du tableau vide.
L'algorithme est écrit pour que la recherche dichotomique ne se fasse que dans le cas où la valeur est comprise entre les valeurs extrêmes du tableau.
On distingue les trois cas qui renvoient False en renvoyant False, 1 , False, 2 et
False, 3.
Compléter l'algorithme de dichotomie donné ci-après.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 | |
Exemples :
>>> dichotomie([15, 16, 18, 19, 23, 24, 28, 29, 31, 33],28)
True
>>> dichotomie([15, 16, 18, 19, 23, 24, 28, 29, 31, 33],27)
(False, 3)
>>> dichotomie([15, 16, 18, 19, 23, 24, 28, 29, 31, 33],1)
(False, 2)
>>> dichotomie([], 28)
(False, 1)
Version avec un changement plus important
Le but de l'exercice est de compléter une fonction qui détermine si une valeur est présente dans un tableau de valeurs triées dans l'ordre croissant.
L'algorithme traite le cas du tableau vide.
L'algorithme renvoie un couple de valeurs composé d'un booléen indiquant si la valeur a été trouvée, ainsi qu'un entier indiquant le nombre d'étapes nécessaires pour arriver à cette réponse.
Compléter l'algorithme de dichotomie donné ci-après.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 | |
Exemples :
>>> dichotomie([15, 16, 18, 19, 23, 24, 28, 29, 31, 33],28)
(True, 4)
>>> dichotomie([15, 16, 18, 19, 23, 24, 28, 29, 31, 33],27)
(False, 4)
>>> dichotomie([15, 16, 18, 19, 23, 24, 28, 29, 31, 33],23)
(True, 1)
>>> dichotomie([15, 16, 18, 19, 23, 24, 28, 29, 31, 33],1)
(False, 3)
>>> dichotomie([], 28)
(False, 0)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 | |
Le but de l'exercice est de compléter une fonction qui détermine si une valeur est présente
dans un tableau de valeurs triées dans l'ordre croissant.
L'algorithme traite le cas du tableau vide.
L'algorithme est écrit pour que la recherche dichotomique ne se fasse que dans le cas où
la valeur est comprise entre les valeurs extrêmes du tableau.
On distingue les trois cas qui renvoient `False` en renvoyant `False,1` , `False,2` et
`False,3`.
Compléter l'algorithme de dichotomie donné ci-après.
```python linenums='1'
def dichotomie(tab, x):
"""
tab : tableau trié dans l’ordre croissant
x : nombre entier
La fonction renvoie True si tab contient x et False sinon
"""
# cas du tableau vide
if ...:
return False,1
# cas où x n'est pas compris entre les valeurs extrêmes
if (x < tab[0]) or ...:
return False,2
debut = 0
fin = len(tab) - 1
while debut <= fin:
m = ...
if x == tab[m]:
return ...
if x > tab[m]:
debut = m + 1
else:
fin = ...
return ...
```
Exemples :
```python
>>> dichotomie([15, 16, 18, 19, 23, 24, 28, 29, 31, 33],28)
True
>>> dichotomie([15, 16, 18, 19, 23, 24, 28, 29, 31, 33],27)
(False, 3)
>>> dichotomie([15, 16, 18, 19, 23, 24, 28, 29, 31, 33],1)
(False, 2)
>>> dichotomie([],28)
(False, 1)
```
Sujet 36 ⚓︎
Exercice 36.1
Programmer la fonction recherche, prenant en paramètre un tableau non vide tab (type list) d'entiers et un entier n, et qui renvoie l'indice de la dernière occurrence de l'élément cherché. Si l'élément n'est pas présent, la fonction renvoie la longueur du tableau.
Exemples
>>> recherche([5, 3],1)
2
>>> recherche([2,4],2)
0
>>> recherche([2,3,5,2,4],2)
3
1 2 3 4 5 6 | |
Programmer la fonction `recherche`, prenant en paramètre un tableau non vide `tab` (type `list`) d'entiers et un entier `n`, et qui renvoie l'indice de la **dernière** occurrence de l'élément cherché. Si l'élément n'est pas présent, la fonction renvoie la longueur du tableau.
Exemples
```python
>>> recherche([5, 3],1)
2
>>> recherche([2,4],2)
0
>>> recherche([2,3,5,2,4],2)
3
```
Exercice 36.2
On souhaite programmer une fonction donnant la distance la plus courte entre un point de départ et une liste de points. Les points sont tous à coordonnées entières. Les points sont donnés sous la forme d'un tuple de deux entiers. La liste des points à traiter est donc un tableau de tuples.
On rappelle que la distance entre deux points du plan de coordonnées \((x;y)\) et \((x';y')\) est donnée par la formule :
On importe pour cela la fonction racine carrée (sqrt) du module math de Python.
On dispose d'une fonction distance et d'une fonction plus_courte_distance :
from math import sqrt # import de la fonction racine carrée
def distance(point1, point2):
""" Calcule et renvoie la distance entre deux points. """
return sqrt((...)**2 + (...)**2)
assert distance((1, 0), (5, 3)) == 5.0, "erreur de calcul"
def plus_courte_distance(tab, depart):
""" Renvoie le point du tableau tab se trouvant à la plus courte distance du point depart."""
point = tab[0]
min_dist = ...
for i in range (1, ...):
if distance(tab[i], depart)...:
point = ...
min_dist = ...
return point
assert plus_courte_distance([(7, 9), (2, 5), (5, 2)], (0, 0)) == (2, 5), "erreur"
assert) à la fonction distance permettant
de vérifier la ou les préconditions.
S. Hoarau :
- Faire des tests d'égalité sur des
floatn'a aucun sens : leassertpour tester la fonctiondistanceest donc à revoir. - Il manque quelque chose pour ne pas inciter à calculer deux fois la distance courante... on pourrait aussi nommé
meilleurouplus_prochele point le plus proche etpointle point courant.
Modulo ces changements c'est un bon exercice.
On souhaite programmer une fonction donnant la distance la plus courte entre un point de départ et une liste de points. Les points sont tous à coordonnées entières. Les points sont donnés sous la forme d'un tuple de deux entiers. La liste des points à traiter est donc un tableau de tuples.
On rappelle que la distance entre deux points du plan de coordonnées \((x;y)\) et \((x';y')\) est donnée par la formule :
On importe pour cela la fonction racine carrée (sqrt) du module math de Python.
On dispose d'une fonction distance et d'une fonction plus_courte_distance :
from math import sqrt # import de la fonction racine carrée
def distance(point1, point2):
""" Calcule et renvoie la distance entre deux points. """
return sqrt((...)**2 + (...)**2)
assert distance((1, 0), (5, 3)) - 5.0 < 0.00001, "erreur de calcul"
def plus_courte_distance(tab, depart):
""" Renvoie le point du tableau tab se trouvant à la plus courte distance du point depart."""
plus_proche = tab[0]
min_dist = ...
for i in range (1, ...):
point = ...
dist = ...
if dist ...:
plus_proche = ...
min_dist = ...
return plus_proche
Recopier sous Python (sans les commentaires) ces deux fonctions puis compléter leur code et tester votre travail.
Exemples :
>>> plus_courte_distance([(7, 9), (2, 5), (5, 2)], (0, 0))
(2, 5)
>>> plus_courte_distance([(7, 9), (2, 5), (5, 2)], (7, 9))
(7, 9)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 | |
On souhaite programmer une fonction donnant la distance la plus courte entre un point
de départ et une liste de points. Les points sont tous à coordonnées entières.
Les points sont donnés sous la forme d'un tuple de deux entiers.
La liste des points à traiter est donc un tableau de tuples.
On rappelle que la distance entre deux points du plan de coordonnées $(x;y)$ et $(x';y')$
est donnée par la formule :
$$d=\sqrt{(x-x')^2+(y-y')^2}$$
On importe pour cela la fonction racine carrée (`sqrt`) du module `math` de Python.
On dispose d'une fonction `distance` et d'une fonction `plus_courte_distance` :
```python
from math import sqrt # import de la fonction racine carrée
def distance(point1, point2):
""" Calcule et renvoie la distance entre deux points. """
return sqrt((...)**2 + (...)**2)
assert distance((1, 0), (5, 3)) == 5.0, "erreur de calcul"
def plus_courte_distance(tab, depart):
""" Renvoie le point du tableau tab se trouvant à la plus courte distance du point depart."""
point = tab[0]
min_dist = ...
for i in range (1, ...):
if distance(tab[i], depart)...:
point = ...
min_dist = ...
return point
assert plus_courte_distance([(7, 9), (2, 5), (5, 2)], (0, 0)) == (2, 5), "erreur"
assert) à la fonction distance permettant
de vérifier la ou les préconditions.
```
Sujet 37 ⚓︎
Exercice 37.1
Programmer la fonction verifie qui prend en paramètre un tableau de valeurs numériques non
vide et qui renvoie True si ce tableau est trié dans l’ordre croissant, False sinon.
Exemples :
Exemples :
>>> verifie([0, 5, 8, 8, 9])
True
>>> verifie([8, 12, 4])
False
>>> verifie([-1, 4])
True
>>> verifie([5])
True
S. Hoarau :
Énoncé clair et simple. Un exercice qui se situe au bon niveau de difficulté pour un exercice 1. Éventuellement la fonction pourrait s'appeler est_trie, le préfixe est_ rappelant qu'il s'agit d'une fonction booléenne. Pourquoi imposer que le tableau est non vide ?
Programmer la fonction est_trie qui prend en paramètre un tableau de valeurs numériqueset qui renvoie True si ce tableau est trié dans l’ordre croissant, False sinon.
Exemples :
Exemples :
>>> est_trie([0, 5, 8, 8, 9])
True
>>> est_trie([8, 12, 4])
False
>>> est_trie([-1, 4])
True
>>> est_trie([5])
True
>>> est_trie([])
True
def est_trie(tableau):
for i in range(len(tableau)-1):
if tableau[i] > tableau[i+1]:
return False
return True
Pour ceux et celles qui n'aiment pas les multiples return ou qui aiment bien les while :
def est_trie(tableau):
correctement_ordonne = True
i = 0
while correctement_ordonne and i < len(tableau)-1:
correctement_ordonne = tab[i] <= tab[i+1]
i += 1
return correctement_ordonne
Programmer la fonction `verifie` qui prend en paramètre un tableau de valeurs numériques non
vide et qui renvoie `True` si ce tableau est trié dans l’ordre croissant, `False` sinon.
Exemples :
```python
Exemples :
>>> verifie([0, 5, 8, 8, 9])
True
>>> verifie([8, 12, 4])
False
>>> verifie([-1, 4])
True
>>> verifie([5])
True
```
Exercice 37.2
Chaque soir, les auditeurs d’une radio votent en ligne pour leur artiste favori. Ces votes sont stockés dans un tableau.
Exemple :
Urne = ['Oreilles sales', 'Oreilles sales', 'Oreilles sales', 'Extra Vomit',
'Lady Baba', 'Extra Vomit', 'Lady Baba', 'Extra Vomit', 'Lady Baba', 'Extra Vomit']
La fonction depouille doit permettre de compter le nombre de votes exprimés pour chaque
artiste. Elle prend en paramètre un tableau et renvoie le résultat dans un dictionnaire dont les
clés sont les noms des artistes et les valeurs le nombre de votes en leur faveur.
La fonction vainqueur doit désigner le nom du ou des gagnants. Elle prend en paramètre un
dictionnaire dont la structure est celle du dictionnaire renvoyé par la fonction depouille et
renvoie un tableau. Ce tableau peut donc contenir plusieurs éléments s’il y a des artistes ex-
aequo.
Compléter les fonctions depouille et vainqueur ci-après pour qu’elles renvoient les
résultats attendus.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 | |
Commentaire de S. Hoarau :
- bon exercice de manipulation de listes et dictionnaire
- pas besoin de la variable
vainqueurlors de la recherche du nombre de voix le plus élevé (d'autant que la fonction s'appelle déjà comme ça) - on peut augmenter un peu la quantité de zones à compléter
Chaque soir, les auditeurs d’une radio votent en ligne pour leur artiste favori. Ces votes sont stockés dans un tableau.
Exemple :
Urne = ['Oreilles sales', 'Oreilles sales', 'Oreilles sales', 'Extra Vomit',
'Lady Baba', 'Extra Vomit', 'Lady Baba', 'Extra Vomit', 'Lady Baba', 'Extra Vomit']
La fonction depouille doit permettre de compter le nombre de votes exprimés pour chaque
artiste. Elle prend en paramètre un tableau et renvoie le résultat dans un dictionnaire dont les
clés sont les noms des artistes et les valeurs le nombre de votes en leur faveur.
La fonction vainqueur doit désigner le nom du ou des gagnants. Elle prend en paramètre un
dictionnaire dont la structure est celle du dictionnaire renvoyé par la fonction depouille et
renvoie un tableau. Ce tableau peut donc contenir plusieurs éléments s’il y a des artistes ex-
aequo.
Compléter les fonctions depouille et vainqueur ci-après pour qu’elles renvoient les
résultats attendus.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 | |
def depouille(urne):
resultat = {}
for bulletin in urne:
if bulletin in resultat:
resultat[bulletin] = resultat[bulletin] + 1
else:
resultat[bulletin] = 1
return resultat
def vainqueur(election):
nmax = 0
for candidat in election:
if election[candidat] > nmax:
nmax = election[candidat]
liste_finale = [nom for nom in election if election[nom] == nmax]
return liste_finale
Chaque soir, les auditeurs d’une radio votent en ligne pour leur artiste favori. Ces votes sont
stockés dans un tableau.
Exemple :
```python
Urne = ['Oreilles sales', 'Oreilles sales', 'Oreilles sales', 'Extra Vomit',
'Lady Baba', 'Extra Vomit', 'Lady Baba', 'Extra Vomit', 'Lady Baba', 'Extra Vomit']
La fonction depouille doit permettre de compter le nombre de votes exprimés pour chaque
artiste. Elle prend en paramètre un tableau et renvoie le résultat dans un dictionnaire dont les
clés sont les noms des artistes et les valeurs le nombre de votes en leur faveur.
La fonction vainqueur doit désigner le nom du ou des gagnants. Elle prend en paramètre un
dictionnaire dont la structure est celle du dictionnaire renvoyé par la fonction depouille et
renvoie un tableau. Ce tableau peut donc contenir plusieurs éléments s’il y a des artistes ex-
aequo.
Compléter les fonctions depouille et vainqueur ci-après pour qu’elles renvoient les
résultats attendus.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 | |
Sujet 38 ⚓︎
La description de l'algorithme du tri par sélection pourrait être meilleure. De plus c'est probablement un exercice trop difficile pour un exercice 1. c'est ce qui lui coûte une
Exercice 38.1
Écrire une fonction tri_selection qui prend en paramètre une liste tab de nombres
entiers et qui renvoie le tableau trié par ordre croissant.
On utilisera l’algorithme suivant :
- on recherche le plus petit élément du tableau, et on l'échange avec l'élément d'indice 0 ;
- on recherche le second plus petit élément du tableau, et on l'échange avec l'élément d'indice 1 ;
- on continue de cette façon jusqu'à ce que le tableau soit entièrement trié.
Exemple :
>>> tri_selection([1,52,6,-9,12])
[-9, 1, 6, 12, 52]
Commentaire de S. Hoarau :
- L'algorithme n'est pas décrit correctement : il ne s'agit pas de chercher le deuxième plus petit, puis le 3e plus petit etc. ce qui peut sembler difficile à réaliser. L'algorithme s'énonce comme ceci :
- On parcourt le tableau de gauche à droite et on recherche le minimum du tableau entre cette position courante et la fin du tableau
- On échange alors les 2 valeurs
- Il s'agit d'un tri en place ... pourquoi renvoyer le tableau ? Il faudrait au moins un mot d'explication (s'il s'agit par exemple de simplifier l'exemple). (Edit : nous sommes plusieurs à penser que ce n'est pas une justification suffisante)
Mais le tri par sélection reste d'un niveau bien supérieur à ce qui est proposé en général en exercice 1.
Écrire une fonction tri_selection qui prend en paramètre une tableau tab de nombres
entiers et qui trie ce tableau en place (c'est-à-dire que le tableau est modifié) par ordre croissant des valeurs.
On utilisera l’algorithme suivant :
- On parcourt le tableau de gauche à droite :
- on recherche le minimum du tableau entre cette position courante et la fin du tableau
- on échange alors les 2 valeurs
Exemple :
>>> tab = [1, 52, 6, -9, 12]
>>> tri_selection(tab)
>>> tab
[-9, 1, 6, 12, 52]
>>> tab_vide = []
>>> tri_selection(tab_vide)
>>> tab_vide
[]
Version une seule fonction :
1 2 3 4 5 6 7 8 | |
Mais la version plus découpée, se rapproche plus de la description de l'algo :
def minimum(tab, i):
"""Recherche la position du minimum entre la position i et la fin du tableau tab"""
ind_minimum = i
for j in range(i+1, len(tab)):
if tab[j] < tab[ind_minimum]:
ind_minimum = j
return ind_minimum
def echange(tab, i, j):
tab[i], tab[j] = tab[j], tab[i]
def tri_selection(tab):
for i in range(len(tab)-1):
ind_minimum = minimum(tab, i)
echange(tab, i, ind_minimum)
return tab
Écrire une fonction `tri_selection` qui prend en paramètre une liste `tab` de nombres
entiers et qui renvoie le tableau trié par ordre croissant.
On utilisera l’algorithme suivant :
- on recherche le plus petit élément du tableau, et on l'échange avec l'élément d'indice 0 ;
- on recherche le second plus petit élément du tableau, et on l'échange avec l'élément
d'indice 1 ;
- on continue de cette façon jusqu'à ce que le tableau soit entièrement trié.
Exemple :
```python
>>> tri_selection([1,52,6,-9,12])
[-9, 1, 6, 12, 52]
```
Exercice 38.2
Le jeu du « plus ou moins » consiste à deviner un nombre entier choisi entre 1 et 99. Un élève de NSI décide de le coder en langage Python de la manière suivante :
- le programme génère un nombre entier aléatoire compris entre 1 et 99 ;
- si la proposition de l’utilisateur est plus petite que le nombre cherché, l’utilisateur en est averti. Il peut alors en tester un autre ;
- si la proposition de l’utilisateur est plus grande que le nombre cherché, l’utilisateur en est averti. Il peut alors en tester un autre ;
- si l’utilisateur trouve le bon nombre en 10 essais ou moins, il gagne ;
- si l’utilisateur a fait plus de 10 essais sans trouver le bon nombre, il perd.
La fonction randint est utilisée. Si a et b sont des entiers, randint(a,b) renvoie un
nombre entier compris entre a et b.
Compléter le code ci-dessous et le tester :
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 | |
Voilà un bon sujet avec un code à compléter bien écrit (respect du PEP8). Donc pas d'énoncé modifié, pas besoin.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 | |
Le jeu du « plus ou moins » consiste à deviner un nombre entier choisi entre 1 et 99.
Un élève de NSI décide de le coder en langage Python de la manière suivante :
- le programme génère un nombre entier aléatoire compris entre 1 et 99 ;
- si la proposition de l’utilisateur est plus petite que le nombre cherché, l’utilisateur en
est averti. Il peut alors en tester un autre ;
- si la proposition de l’utilisateur est plus grande que le nombre cherché, l’utilisateur en
est averti. Il peut alors en tester un autre ;
- si l’utilisateur trouve le bon nombre en 10 essais ou moins, il gagne ;
- si l’utilisateur a fait plus de 10 essais sans trouver le bon nombre, il perd.
La fonction `randint` est utilisée. Si a et b sont des entiers, `randint(a,b)` renvoie un
nombre entier compris entre `a` et `b`.
Compléter le code ci-dessous et le tester :
```python linenums='1'
from random import randint
def plus_ou_moins():
nb_mystere = randint(1,...)
nb_test = int(input("Proposez un nombre entre 1 et 99 : "))
compteur = ...
while nb_mystere != ... and compteur < ... :
compteur = compteur + ...
if nb_mystere ... nb_test:
nb_test = int(input("Trop petit ! Testez encore : "))
else:
nb_test = int(input("Trop grand ! Testez encore : "))
if nb_mystere == nb_test:
print ("Bravo ! Le nombre était ",...)
print("Nombre d'essais: ",...)
else:
print ("Perdu ! Le nombre était ",...)
Sujet 39 ⚓︎
Pour l'exercice 1, il faut préciser quoi faire en cas de tableau vide... on alors, le plus simple, dire que ce dernier n'est pas vide.
Exercice 39.1
Écrire une fonction moyenne prenant en paramètres une liste d’entiers et qui renvoie la
moyenne des valeurs de cette liste.
Exemple :
>>> moyenne([10,20,30,40,60,110])
45.0
Une x-ième fonction de calcule de moyenne. Le cas de la liste vide n'est pas évoqué, il vaut mieux préciser que la list en'est pas vide. On parle plutôt de tableau de valeurs ici car on ne mpdifie jamais ce tableau.
Écrire une fonction moyenne prenant en paramètres un tableau non vide d’entiers et qui renvoie la
moyenne des valeurs du tableau.
Exemple :
>>> moyenne([10, 20, 30, 40, 60, 110])
45.0
>>> moyenne([1, 3])
2.0
1 2 3 4 5 | |
On trouvera sûrement :
def moyenne(tableau):
return sum(tableau) / len(tableau)
Écrire une fonction `moyenne` prenant en paramètres une liste d’entiers et qui renvoie la
moyenne des valeurs de cette liste.
Exemple :
```python
>>> moyenne([10,20,30,40,60,110])
45.0
```
Exercice 39.2
On travaille sur des dessins en noir et blanc obtenu à partir de pixels noirs et blancs :
La figure « cœur » ci-dessus va servir d’exemple.
On la représente par une grille de nombres, c’est-à-dire par une liste composée de sous-listes de même longueurs.
Chaque sous-liste représentera donc une ligne du dessin.
Dans le code ci-dessous, la fonction affiche permet d’afficher le dessin. Les pixels noirs
(1 dans la grille) seront représentés par le caractère "*" et les blancs (0 dans la grille) par
deux espaces.
La fonction zoomListe prend en argument une liste liste_depart et un entier k. Elle
renvoie une liste où chaque élément de liste_depart est dupliqué k fois.
La fonction zoomDessin prend en argument la grille dessin et renvoie une grille où
toutes les lignes de dessin sont zoomées k fois et répétées k fois.
Soit le code ci-dessous :
1 2 3 4 5 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 37 38 39 40 41 42 43 | |
Résultats à obtenir :
>>> affiche(coeur)
* * * *
* * * *
* * *
* *
* *
* *
* *
* *
* *
*
>>> affiche(zoomDessin(coeur,3))
* * * * * * * * * * * *
* * * * * * * * * * * *
* * * * * * * * * * * *
* * * * * * * * * * * *
* * * * * * * * * * * *
* * * * * * * * * * * *
* * * * * * * * *
* * * * * * * * *
* * * * * * * * *
* * * * * *
* * * * * *
* * * * * *
* * * * * *
* * * * * *
* * * * * *
* * * * * *
* * * * * *
* * * * * *
* * * * * *
* * * * * *
* * * * * *
* * * * * *
* * * * * *
* * * * * *
* * * * * *
* * * * * *
* * * * * *
* * *
* * *
* * *
S. Hoarau :
- Harmoniser le nommage des fonctions, en respectant le PEP8 :
zoomListeetzoomDessindevraient êtrezoom_listeetzoom_dessinresp. - Pas besoin du caractère
\lorsqu'on veut créer une structure typelist,tuple,dict... sur plusieurs lignes - Pour la fonction affiche on aurait apprécié une solution un peu plus intelligente avec l'utilisation d'une constante
CARACTERES = [' ', ' *'] - Aucune raison que la variable pour la deuxième boucle se nomme
col: il ne s'agit pas d'une colonne mais d'une valeur binaire sur la ligne... - dans la fonction
zoomDessinla variable de la première boucle devrait s'appelerligne
Autre version de la fonction affiche
CARACTERES = [' ', ' *']
def affiche(dessin):
for ligne in dessin:
for digit in ligne:
print(CARACTERES[digit], end="")
print()
On travaille sur des dessins en noir et blanc obtenu à partir de pixels noirs et blancs : La figure « cœur » ci-dessus va servir d’exemple. On la représente par une grille de nombres, c’est-à-dire par une liste composée de sous-listes de même longueurs. Chaque sous-liste représentera donc une ligne du dessin.
Dans le code ci-dessous, la fonction affiche permet d’afficher le dessin. Les pixels noirs
(1 dans la grille) seront représentés par le caractère "*" et les blancs (0 dans la grille) par
deux espaces.
La fonction zoom_liste prend en argument une liste liste_depart et un entier k. Elle
renvoie une liste où chaque élément de liste_depart est dupliqué k fois.
La fonction zoom_dessin prend en argument la grille dessin et renvoie une grille où
toutes les lignes de dessin sont zoomées k fois et répétées k fois.
Soit le code ci-dessous :
1 2 3 4 5 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 37 38 39 | |
Résultats à obtenir :
>>> affiche(coeur)
* * * *
* * * *
* * *
* *
* *
* *
* *
* *
* *
*
>>> affiche(zoomDessin(coeur,3))
* * * * * * * * * * * *
* * * * * * * * * * * *
* * * * * * * * * * * *
* * * * * * * * * * * *
* * * * * * * * * * * *
* * * * * * * * * * * *
* * * * * * * * *
* * * * * * * * *
* * * * * * * * *
* * * * * *
* * * * * *
* * * * * *
* * * * * *
* * * * * *
* * * * * *
* * * * * *
* * * * * *
* * * * * *
* * * * * *
* * * * * *
* * * * * *
* * * * * *
* * * * * *
* * * * * *
* * * * * *
* * * * * *
* * * * * *
* * *
* * *
* * *
1 2 3 4 5 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 37 38 39 40 | |
{: .centrer width=30%}
On travaille sur des dessins en noir et blanc obtenu à partir de pixels noirs et blancs :
La figure « cœur » ci-dessus va servir d’exemple.
On la représente par une grille de nombres, c’est-à-dire par une liste composée de sous-listes de même longueurs.
Chaque sous-liste représentera donc une ligne du dessin.
Dans le code ci-dessous, la fonction `affiche` permet d’afficher le dessin. Les pixels noirs
(1 dans la grille) seront représentés par le caractère "*" et les blancs (0 dans la grille) par
deux espaces.
La fonction `zoomListe` prend en argument une liste `liste_depart` et un entier `k`. Elle
renvoie une liste où chaque élément de `liste_depart` est dupliqué `k` fois.
La fonction `zoomDessin` prend en argument la grille `dessin` et renvoie une grille où
toutes les lignes de `dessin` sont zoomées `k` fois et répétées `k` fois.
Soit le code ci-dessous :
```python linenums='1'
coeur = [[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], \
[0, 0, 0, 1, 1, 0, 0, 0, 1, 1, 0, 0, 0], \
[0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0], \
[0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0], \
[0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0], \
[0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0], \
[0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0], \
[0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0], \
[0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0], \
[0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0], \
[0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0], \
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]
def affiche(dessin):
''' affichage d'une grille : les 1 sont représentés par
des " *" , les 0 par deux espaces " " '''
for ligne in dessin:
for col in ligne:
if col == 1:
print(" *", end="")
else:
print(" ", end="")
print()
def zoomListe(liste_depart,k):
'''renvoie une liste contenant k fois chaque
élément de liste_depart'''
liste_zoom = ...
for elt in ... :
for i in range(k):
...
return liste_zoom
def zoomDessin(grille,k):
'''renvoie une grille où les lignes sont zoomées k fois
ET répétées k fois'''
grille_zoom=[]
for elt in grille:
liste_zoom = ...
for i in range(k):
... .append(...)
return grille_zoom
Résultats à obtenir :
>>> affiche(coeur)
* * * *
* * * *
* * *
* *
* *
* *
* *
* *
* *
*
>>> affiche(zoomDessin(coeur,3))
* * * * * * * * * * * *
* * * * * * * * * * * *
* * * * * * * * * * * *
* * * * * * * * * * * *
* * * * * * * * * * * *
* * * * * * * * * * * *
* * * * * * * * *
* * * * * * * * *
* * * * * * * * *
* * * * * *
* * * * * *
* * * * * *
* * * * * *
* * * * * *
* * * * * *
* * * * * *
* * * * * *
* * * * * *
* * * * * *
* * * * * *
* * * * * *
* * * * * *
* * * * * *
* * * * * *
* * * * * *
* * * * * *
* * * * * *
* * *
* * *
* * *
Sujet 40 ⚓︎
Pour l'exercice 2, on peut mettre une mais quand même il faut absolument que la fonction prenne le dictionnaire des notes en paramètre.
Exercice 40.1
Écrire une fonction recherche qui prend en paramètres elt un nombre et tab un
tableau de nombres, et qui renvoie le tableau des indices de elt dans tab si elt est dans tab et le tableau vide [] sinon.
Exemples :
>>> recherche(3, [3, 2, 1, 3, 2, 1])
[0, 3]
>>> recherche(4, [1, 2, 3])
[]
Beaucoup de fonctions de l'exercice 1, se nomment recherche. S'il s'agit bien du thème de la fonction, rien n'interdit de choisir un nom plus précis. Ici par exemple la fonction cherche à répertorier les positions des différentes occurrences d'un élément. On pourrait donc nommer la fonction recherche_positions
Écrire une fonction recherche_positions qui prend en paramètres elt un nombre et tab un
tableau de nombres, et qui renvoie le tableau des indices de elt dans tab et le tableau vide [] si elt n'apparaît pas dans tab.
Exemples :
>>> recherche_positions(3, [3, 2, 1, 3, 2, 1])
[0, 3]
>>> recherche_positions(4, [1, 2, 3])
[]
Version classique
1 2 3 4 5 6 | |
Version en compréhension de liste
1 2 | |
Écrire une fonction `recherche` qui prend en paramètres `elt` un nombre et `tab` un
tableau de nombres, et qui renvoie le tableau des indices de `elt` dans `tab` si `elt` est dans `tab` et le tableau vide `[]` sinon.
Exemples :
```python
>>> recherche(3, [3, 2, 1, 3, 2, 1])
[0, 3]
>>> recherche(4, [1, 2, 3])
[]
```
Exercice 40.2
Un professeur de NSI décide de gérer les résultats de sa classe sous la forme d’un dictionnaire :
- les clefs sont les noms des élèves ;
- les valeurs sont des dictionnaires dont les clefs sont les types d’épreuves et les valeurs sont les notes obtenues associées à leurs coefficients.
Avec :
resultats = {'Dupont':{ 'DS1' : [15.5, 4],
'DM1' : [14.5, 1],
'DS2' : [13, 4],
'PROJET1' : [16, 3],
'DS3' : [14, 4]},
'Durand':{ 'DS1' : [6 , 4],
'DM1' : [14.5, 1],
'DS2' : [8, 4],
'PROJET1' : [9, 3],
'IE1' : [7, 2],
'DS3' : [8, 4],
'DS4' :[15, 4]}}
L’élève dont le nom est Durand a ainsi obtenu au DS2 la note de 8 avec un coefficient 4.
Le professeur crée une fonction moyenne qui prend en paramètre le nom d’un de ces
élèves et lui renvoie sa moyenne arrondie au dixième.
Compléter le code du professeur ci-dessous :
1 2 3 4 5 6 7 8 9 10 11 12 | |
S. Hoarau s'interroge sur quelques uns des choix de l'énoncé de cet exercice 2 :
- Un double dictionnaire est peut-être d'un niveau un peu élevé ; ne serait-ce que vis à vis de la moyenne des exercices donnés.
- pourquoi faire une itération sur
values()pour le 2e dictionnaire ? pas sûr que se soit exigé comme connaissance - pourquoi le dictionnaire de gestion des notes n'est-il pas un paramètre de la fonction ?
Un professeur de NSI décide de gérer les résultats de sa classe sous la forme d’un dictionnaire :
- les clefs sont les noms des élèves ;
- les valeurs sont des dictionnaires dont les clefs sont les types d’épreuves et les valeurs sont les notes obtenues associées à leurs coefficients.
Avec :
resultats = {'Dupont':{ 'DS1' : [15.5, 4],
'DM1' : [14.5, 1],
'DS2' : [13, 4],
'PROJET1' : [16, 3],
'DS3' : [14, 4]},
'Durand':{ 'DS1' : [6 , 4],
'DM1' : [14.5, 1],
'DS2' : [8, 4],
'PROJET1' : [9, 3],
'IE1' : [7, 2],
'DS3' : [8, 4],
'DS4' :[15, 4]}}
L’élève dont le nom est Durand a ainsi obtenu au DS2 la note de 8 avec un coefficient 4.
Le professeur crée une fonction moyenne qui prend en paramètre le nom d’un de ces
élèves et lui renvoie sa moyenne arrondie au dixième. En cas d'absence, la fonction renvoie -1.
Compléter le code du professeur ci-dessous :
1 2 3 4 5 6 7 8 9 10 11 12 | |
1 2 3 4 5 6 7 8 9 10 11 12 | |
Un professeur de NSI décide de gérer les résultats de sa classe sous la forme d’un
dictionnaire :
- les clefs sont les noms des élèves ;
- les valeurs sont des dictionnaires dont les clefs sont les types d’épreuves et les
valeurs sont les notes obtenues associées à leurs coefficients.
Avec :
```python
resultats = {'Dupont':{ 'DS1' : [15.5, 4],
'DM1' : [14.5, 1],
'DS2' : [13, 4],
'PROJET1' : [16, 3],
'DS3' : [14, 4]},
'Durand':{ 'DS1' : [6 , 4],
'DM1' : [14.5, 1],
'DS2' : [8, 4],
'PROJET1' : [9, 3],
'IE1' : [7, 2],
'DS3' : [8, 4],
'DS4' :[15, 4]}}
L’élève dont le nom est Durand a ainsi obtenu au DS2 la note de 8 avec un coefficient 4.
Le professeur crée une fonction moyenne qui prend en paramètre le nom d’un de ces
élèves et lui renvoie sa moyenne arrondie au dixième.
Compléter le code du professeur ci-dessous :
1 2 3 4 5 6 7 8 9 10 11 12 | |