Sujets 01-10 de l'épreuve pratique
La NSI comporte deux épreuves en Terminale :
- Une épreuve théorique de 3h30 sur table notée sur 12 et comportant un choix de 5 exercices. Après lecture rapide des exercices (30 minutes au maximum), il vous restera 3h pour en réaliser 3, soit environ 1h par exercice. Chaque exercice est noté sur 4.
- Une épreuve pratique de 1h et notée sur 8 pendant laquelle vous aurez à programmer et à interagir avec l'examinateur. Il s'agit donc autant d'une épreuve de programmation qu'un oral. Les sujets sont connus à l'avance mais vous tirez le votre au sort juste avant l'épreuve. Chaque sujet comporte deux exercices :
- Un exercice de création pure où on vous demande de réaliser une fonction à partir des spécifications fournies (4 points)
- Un exercice guidé (4 points)
A l'heure actuelle, la banque de sujets comporte 30 sujets.
1 - Sujet 01
A - Thèmes
- Tableaux statiques (implémentés via le type list de Python)
- Tuples
- Assertions
B - Lien local vers le sujet
En cas de panne du site officiel : SUJET 01 version locale
C - Remarques sur le sujet
Pensez bien à lire l'exercice 2 jusqu'au bout : il faut aussi vérifier les préconditions de la fonction distance() avec des assertions.
- Version 2021 : la dernière assertion est à modifier en remplaçant l'envoi d'un point-tableau par un point-tuple.
- Version 2021 : Lire plutôt : Recopier sous Python (sans la documentation).
assert plus_courte_distance([(7, 9), (2, 5), (5, 2)], (0, 0)) == (2, 5), "erreur"
D - De l'aide ?
Pas de difficulté particulière. Il faut juste bien voir le mot en gras... On doit donc lire le tableau jusqu'au bout.
Il faut juste faire attention au type des paramètres pour bien comprendre ce que contiennent les paramètres point1 et point2.
A partir de là, il faut vous demander comment récupérer la coordonnée x à partir de la variable point1.
On retrouve en réalité la recherche d'un minimum dans un tableau non vide.
- On commence par dire que le minimum correspond à la première case
- On lit le contenu de toutes les autres cases et on remplace le minimum calculé et la réponse à renvoyer à chaque fois qu'on trouve une valeur plus petite que le minimum actuel.
E - Correction
2 - Sujet 02
A - Thèmes
- Tableaux statiques (implémentés via le type list de Python)
B - Lien local vers le sujet
En cas de panne du site officiel : SUJET 02 version locale
C - Remarques sur le sujet
Version 2021 : attention, l'exercice 1 vous demande de faire une fonction un peu bizarre puisqu'elle renvoie soit un flottant (la moyenne), soit un string si le tableau est vide.
Version 2021 : attention, l'exercice 2 demande bien de renvoyer la référence de la liste qu'on a modifié par effet de bord. C'est un peu bizarre, mais c'est comme ça.
D - De l'aide ?
Pas de difficulté particulière. Il suffit de se souvenir comment tester qu'un tableau est vide et qu'il faut créer une variable de stockage de la somme des valeurs avant de la remplir dans la boucle.
Le tableau non trié est délimité par son indice gauche noté i dans l'énoncé et son indice droite noté j dans l'énoncé.
Il faut comprendre comment fonctionne la fonction :
- On commence par la gauche
- Si l'élément en cours est un 0 : on le laisse en place et on passe à l'élément suivant, en incrémentant la variable i pour réduire le tableau non trié par la gauche.
- Si l'élément en cours est un 1 : on intervertit la case i et j et on décrémente la variable j pour réduire le tableau non trié par la droite
- On boucle sur la case référencée par i.
E - Correction
3 - Sujet 03
A - Thèmes
- Récursivité si on veut (pour l'exercice 1)
- Tableaux statiques (implémentés via le type list de Python)
- Dichotomie
B - Lien local vers le sujet
En cas de panne du site officiel : SUJET 03 version locale
C - Remarques sur le sujet
Rien de particulier. On parle de dichotomie, donc il faut se souvenir ce que c'est...
D - De l'aide ?
Pas si facile que cela.
Commencer peut-être par faire uniquement la fonction si les deux nombres sont positifs. 8*5 doit être calculé comme 8+8+8+8+8 ou 5+5+5+5+5+5+5+5. Si vous vous souvenez du cours sur la récursivité, on peut le faire aussi en ... récursif.
Et ensuite on complique.
Pour le coup, à part vous dire d'aller revoir cette leçon de 1er...
En gros, on cherche le point central de l'intervalle.
Si ce point central contient plus que ce qu'on cherche, on peut supprimer la partie droite. On décale donc l'extrémité droite sur la case à gauche de la case centrale.
Si ce point central contient moins que ce qu'on cherche, on peut supprimer la partie gauche. On décale donc l'extrémité gauche sur la case à droite de la case centrale.
E - Correction
4 - Sujet 04
A - Thèmes
- Tableaux statiques (implémentés via le type list de Python)
- Dichotomie
- Tuples
B - Lien local vers le sujet
En cas de panne du site officiel : SUJET 04 version locale
C - Remarques sur le sujet
Attention, il faut bien comprendre que la fonction dichotomie() ne renvoie pas nécessairement un booléen mais parfois un tuple contenant un booléen et un entier. Pour être plus explicite, on aurait pu mettre des parenthèses cette fois justement. Le return n'est pas une fonction mais puisqu'il renvoit un tuple, nous aurions pu marquer return (False,1).
Il aurait peut-être fallu donner le prototype de la fonction dichotomie() soit cette forme théorique :
1 | |
Il n'en reste pas moins que c'est étrange de créer une fonction qui peut renvoyer des réponses de types différents. On peut éventuellement s'accorder sur une réponse ou None si on ne trouve rien par exemple. Mais la création de fonctions ayant des réponses de types différents en fonction des cas doit rester exeptionnelle. Si vous voulez aller plus loin que le sujet, on pourrait rajouter une question : comment modifier la réponse même en cas de recherche positive pour renvoyer un tuple (autrement dit que pourrait-on renvoyer en plus du simple booléen ?)
D - De l'aide ?
Pas de difficulté particulière. Il faut juste penser à créer au préalable une variable pour stocker la somme des valeurs qu'on va lire.
Faites attention à la particularité de cette fonction qui renvoit soit True soit False associé à un code d'erreur.
Sinon, on retrouve le principe de la dichotomie : on divise à chaque fois le tableau restant en deux en ne continuant à chercher qu'à droite ou à gauche. Cela veut dire qu'il faudra modifier les variables debut et fin qui délimitent le sous-tableau dans lequel on peut encore faire des recherches.
E - Correction
5 - Sujet 05
A - Thèmes
- Tableaux statiques (implémentés via le type list de Python)
- Entiers non signés en binaire
- Tri par insertion
B - Lien local vers le sujet
En cas de panne du site officiel : SUJET 05 version locale
C - Remarques sur le sujet
Attention : le sujet utilise des noms de variables en une lettre en utilisant alors une majuscule. C'est une convention utilisée parfois, surtout dans le domaine des mathématiques. Donc, attention, T et L sont bien juste des tableaux et pas des classes.
Attention 2 : la fonction de tri renvoie le tableau qu'on lui a envoyé alors qu'il a été modifié en place... C'est contraire à ce qu'on a appris mais il s'agit certainement de juste visualiser le tableau sans avoir à l'évaluer dans la console. Mais normalement, la fonction devrait soit
- modifier en place et ne rien renvoyer ou
- faire une copie du tableau, modifier la copie et renvoyer la copie
D - De l'aide ?
Pas de difficulté particulière. Puisqu'on va devoir lire toutes les cases jusqu'au bout, une boucle bornée sera plus "logique" qu'une boucle non bornée. Le tout est de penser à créer une variable de stockage de la réponse avant de commencer les tours de boucle. La seule difficulté consiste à parvenir à placer les indices dans le bon sens : la case d'indice 0 est celle du bit de poids fort.
Le plus simple est encore de vous créer une liste sur votre brouillon et voir comment on doit la trier. C'est du cours en réalité. L'algorithme du sujet est le même que celui que nous avons vu en première, à part qu'il n'utilise pas les mêmes conditions d'arrêt ect... A vous de réflechir.
E - Correction
6 - Sujet 06
A - Thèmes
- Méthode gloutonne
- Tableaux statiques (implémentés via le type list de Python)
- Liste chainée
- File
B - Lien local vers le sujet
En cas de panne du site officiel : SUJET 06 version locale
C - Remarques sur le sujet 2021
Attention : l'un des tests est faux. Le rendu de 89 euros doit renvoyer un tableau [17, 2, 0] et pas [17, 2, 1].
Attention 2 : la classe à compléter possède des erreurs. Il faudra télécharger en attendant ma propre version de l'exo 2 SUJET 06 version locale implémentant des modifications rendant le sujet réalisable. On verra comment le sujet officiel évolue.
Attention, cet exercice propose une mauvaise implémentation d'une file puisque le défilement est à coût constant : le dernier élément devient le premier de la séquence de Maillons mais l'attribut dernier_maillon de la file pointe sur le premier de cette séquence. Défiler revient donc à aller chercher le dernier élement de la séquence en partant de la seule cellule connue : le dernier arrivé. On obtient donc un défilement à coût linéaire... Si par malchance vous tombez sur celui-ci, expliquez bien que ce n'est une "bonne" implémentation puisqu'on pourrait avoir du constant à l'enfiler et au défilement en plaçant le dernier arrivé en fin de séquence.
Le défilement revient à chercher le prédécesseur du dernier maillon dans la séquence. Une fois trouvé, on stocke la valeur contenue dans le dernier élément de la séquence et on dit que son prédécesseur n'a plus de successeur.
D - De l'aide ?
On commence par créer un tableau de 3 cases contenant 0.
La méthode gloutonne consiste ici à chercher à compléter tant que la monnaie à rendre ne vaut pas zéro.
On commencera par exemple à remplir l'indice 0 d'un tableau de réponse en se demandant comment de billets de 5 euros il faut rendre. Ensuite on modifie la quantité à rendre et on passe aux pièces de 2, ect...
La correction propose d'ailleurs une solution plus automatisée.
Comprennez bien que l'attribut dernier_file devra contenir le dernier arrivé dans la file mais qu'on le placera à l'avant des Maillons représentant les données de la File.
Commencez par mettre au brouillon le cas de l'enfilement : si j'enfile 5 puis 15 puis 25, je dois parvenir à créer
- d'abord une séquence 5 -> None et l'attribut de la file qui pointe sur le 5.
- ensuite une séquence 15 -> 5 -> None et l'attribut de la file qui pointe sur le 15.
- ensuite une séquence 25 -> 15 -> 5 -> None et l'attribut de la file qui pointe sur le 25.
E - Correction
7 - Sujet 07
A - Thèmes
- Programmation Dynamique (pas au programme de l'écrit car elle sera vue après mars)
B - Lien local vers le sujet
En cas de panne du site officiel : SUJET 07 version locale
C - Remarques sur le sujet 2021
D - De l'aide ?
E - Correction
8 - Sujet 08
A - Thèmes
- String
- Tableaux dynamiques (implémentés via le type list de Python), notamment l'utilisation de append().
- Récursivité
- Algorithme glouton (ou méthode gloutonne)
- Rendu de monnaie (un "classique")
B - Lien local vers le sujet
En cas de panne du site officiel : SUJET 08 version locale
C - Remarques sur le sujet
Attention EXO 2: le texte du sujet utilise la variable pieces mais sur la première ligne du programme fourni, on trouve Pieces : la majuscule a certainement été provoquée par un éditeur de texte jugeant qu'un début de texte doit commencer par une majuscule. Pensez à remettre une minuscule.
Attention BIS EXO 2: le sujet comporte par contre une coquille. La méthode append modifie un tableau dynamique sur place mais ne renvoie rien. Il faut donc apporter cette modification :
1
2 | |
Les lignes pour remplacer la précédente :
1
2
3 | |
D - De l'aide ?
Vraiment aucune difficulté particulière : il suffit de se souvenir qu'un string est itérable, comme un tableau.
On peut donc utiliser la fonction native len et la notation crochets+indice pour obtenir un caractère particulier dans le string.
On rappelle que la méthode gloutonne consiste à faire un choix optimal localement de façon à réduire la taille du problème total.
Ici le choix est de toujours rendre la pièce de plus grande valeur d'abord.
Si on doit rendre 60 cents avec des pièces de 50 cents, 20 cents et 10 cents, on choisit donc localemnet de rendre 50 cents.
On a donc réduit la taille du problème puisqu'il ne reste que 10 cents à rendre. Comment faire ? En faisant un choix encore local : on rend la plus grande pièce possible disponible. Ici 10.
E - Correction
9 - Sujet 09
A - Thèmes
- Tableaux dynamiques (dont la méthode append())
- Tableaux de tableaux
- Triangle de Pascal (un "classique")
B - Lien local vers le sujet
En cas de panne du site officiel : SUJET 09 version locale
C - Remarques sur le sujet
Attention EXO 1: le calcul de l'exemple est faux. Le résultat est de 12.5 sur cette moyenne.
D - De l'aide ?
La seule difficulté vient du fait que chaque élément du tableau est un tuple : l'indice 0 contient la note et l'indice 1 contient le coefficient.
Il faudra donc faire la somme de chaque note associée à son coefficient pour obtenir la somme totale et la somme des coefficients.
Une fois calculées ces deux sommes, il suffit de renvoyer le total divisé par la somme des coefficients.
L'exercice 2 est plus compliqué que la moyenne des autres sujets : il faut bien comprendre que append() modifie le tableau en place en lui rajoutant une nouvelle case.
On découpe la création d'un nouveau tableau Ck encodant la ligne en trois parties :
- Création d'un nouveau tableau ne contenant que [1].
- Calcul et rajout avec append() des cases intermédiaires en utilisant le tableau encodant la ligne du dessous et ses cases i-1 et i.
- Rajout de la dernière case pour cette ligne : un [1].
E - Correction
10 - Sujet 10
A - Thèmes
- Recherche de maximum
- Tableaux statiques
- Piles
- Tableaux dynamiques
- Déversement d'une pile dans une autre pile pour inverser les éléments
B - Lien local vers le sujet
En cas de panne du site officiel : SUJET 10 version locale
C - Remarques sur le sujet
Remarque EXO 1: on ne vous demande pas de gérer le tableau vide mais uniquement un tableau d'entiers.
Remarque EXO 2 : le print() n'est là que pour vous montrer ce que contient votre pile. Lors de l'utilisation de cette fonction en production, il faudrait bien évidemment le supprimer. On notera également qu'utiliser t2 = list(t1) revient à faire une copie peu profonde : si les données contenues dans le tableau sont mutables, on pourra modifier le contenu de l'un en modificant le contenu de l'autre. En réalité, cela revient à faire une copie par compréhension. Le jour du bac, préférez t2 = [v for v in t1]
D - De l'aide ?
La seule difficulté vient du fait qu'il faut penser à mémoriser le maximum et la position du maximum.
Comme l'indice doit correspondre à la première occurrence, il faut faire attention à l'inégalité utilisée.
Rien de particulier.
On notera juste que :
- Pour "gagner" du temps, on manipule directement le tableau dynamique plutôt que de passer par des fonctions d'interface
- Il faut penser à inverser la pile T3. Pour cela, on la déverse dans une nouvelle pile qu'on nomme T2 en fin de programme.
E - Correction
Article publié le 10 10 2021
Dernière modification : 10 10 2021
Auteur : ows. h.