Algorithmique & Programmation Orientée Objet Semestre 2 ST 2018-2019 Evaluation intermédiaire Correction commentée
| Exercice n°1 | Exercice n°2 | Problème |
Clavier.class - Ecran.class - Documentation
Sujet pdf
Exercice n°1 a) Une décomposition dichotomique est un traitement informatique dont le principe de base consiste à résoudre un problème en divisant son champ d'application de façon récurrente d'un facteur 2. "de façon récurrente" signifie ici qu'un certain nombre d'étapes de résolution sont exécutées et qu'à chaque étape, le même traitement est réalisé, en l'occurrence sur un champ 2 fois plus petit obtenu par scission du champ de l'étape considérée. Les décompositions dichotomiques sont de 2 types : (1) la récurrence se fait sur un seul des deux sous-champs, (2) la récurrence se fait successivement sur les deux sous-champs. La taille du champ étant divisée par 2 à chaque étape, à force de divisions par 2, le champ devient inéluctablement suffisamment petit pour que, appliquée à ce champ, la détermination du résultat devienne triviale. Exemple : Rechercher le zéro d'une fonction croissante sur l'intervalle [bi,bf] et ayant un zéro sur cet intervalle sera réalisé en déterminant dans lequel des deux intervalles [bi,(bi+bf)/2.0] et [(bi+bf)/2.0,bf] le zéro recherché se trouve et en relançant la recherche dans cet intervalle ainsi de suite selon le même principe jusqu'à que l'amplitude de l'intervalle devienne plus petit qu'une limite fixée. On est ici en présence d'une décomposition de type (1) (voir ci-dessus). Plusieurs traitements à base de décomposition dichotomique ont été présentés au cours du semestre : - type (1) : test de la présence d'une valeur dans un ensemble trié de valeurs, - type (1) : recherche de la racine carrée d'une valeur, - type (2) : tri fusion, - type (2) : tri rapide. b) L'opération de base de l'algorithme de tri à bulle est la permutation, si ces éléments ne respectent pas le critère de tri, de deux éléments placés en positions successives dans l'ensemble à trier. Cette opération de base est utilisée de la façon suivante : - Etape 1 : On parcourt séquentiellement tous les couples de valeurs situées en positions consécutives dans ensemble à trier en appliquant notre opération de "permutation sous condition". Au cours de ce parcours, les grandes valeurs de l'ensemble à trier au sens du critère de tri se déplacent de proche en proche de gauche à droite pour se rapprocher de leurs places finales et, en particulier, la plus grande valeur rejoint la dernière place de l'ensemble c'est à dire sa place finale. - Etape 2 : La dernière valeur étant à sa place, le reste de l'ensemble reste à trier. On réalise un 2ème parcours de permutations que l'on restreint à toutes les valeurs sauf la dernière. Cette étape a pour conséquence de déporter en avant dernière position de l'ensemble global la plus grande valeur de l'ensemble restant à trier. Les deux dernières valeurs de l'ensemble global sont maintenant à leurs places respectives et la zone restant en tête (l'ensemble global moins ses deux dernières valeurs) n'est pas triée. - Etapes suivantes : On poursuit le tri par étapes successives qui ont individuellement pour conséquence, à chaque étape, de placer une nouvelle valeur à sa position en queue et donc d'augmenter de 1 la taille de la zone triée en queue, et de diminuer de 1 la taille de la zone restant à trier en tête. Le tri est fini lorsque la zone à trier en tête est réduite à une seule valeur. Si n est la taille de l'ensemble à trier, on réalise n-1 parcours. Le premier nécessite le test de n-1 couples de valeurs successives, le deuxième teste n-2 couples, le 3ème teste n-3 couples et ainsi de suite jusqu'au n-1ème où 1 couple est testé. L'implantation est effectuée naturellement sous la forme de deux boucles "pour" imbriquées. Le tri à bulle est utilisé lorsque, ne disposant pas d'un algorithme déjà développé, il s'agit d'implanter rapidement un algorithme de tri et lorsqu'il n'est question que de trier des petits ensembles de valeurs. Le choix de cet algorithme dans ces conditions est justifié par le fait qu'il est simple et court à écrire et que l'inefficacité d'exécution qui lui est généralement reconnue n'est alors peut-être pas patente. c) Les trois syntaxes sont (nomType désigne le type élémentaire du tableau, nomVariable désigne le nom de la variable tableau) : - Déclaration sans allocation mémoire ni taille : nomType [][] nomVariable; - Déclaration avec allocation mémoire pour t1*t2 éléments et initialisation de ses éléments à 0 : nomType [][] nomVariable = new nomType[t1][t2] ; - Déclaration avec allocation mémoire et initialisation des éléments avec les valeurs spécifiées entre accolades : nomType [][] nomVariable = { { v11,v12,v13,...,v1m }, { v21,v22,v23,...,v2m }, ... { vn1,vn2,vn3,...,vnm } }; Les tailles n et m selon les deux indices sont calculées lors de la compilation par analyse des valeurs données entre accolades. n est le nombre de lignes définies par les accolades de niveau 1. m est le nombre de valeurs placées entres les accolades de niveau 2. d) Plusieurs raisons peuvent inciter un développeur à ne pas utiliser la récursivité : - Le problème n'est pas formulé sous forme récurrente. Le programmer en utilisant la récursivité nécessiterait de le reformuler sous forme récurrente. Il peut ne pas en exister ou cela peut être complexe et donc comporter des risques d'erreur. - La solution récursive programmée présente un problème de complexité. Exemple : La solution récursive au calcul du nombre de Fibonacci (fib(n)=fib(n-1)+fib(n-2) si n>1, fib(0) = fib(1) = 1) est caractérisée par une complexité en O(fib(n)), qui n'est pas bonne du tout. La solution itérative est de complexité O(n), qui est bien meilleure. - Une préoccupation fondamentale est d'aller le plus vite possible. A complexités équivalentes les solutions itérative et récursive d'un même problème sont souvent caractérisées par une plus grande rapidité en itératif qu'en récursif. - La récursivité risque d'être trop "profonde". L'utilisation de la récursivité implique la consommation d'une certaine quantité de mémoire à chaque appel récursif en "profondeur". La quantité globale utilisée augmente donc à chaque nouvel appel. La mémoire dédiée à ce rôle (la "pile") étant de taille limitée et fixée, il existe donc une profondeur maximale de récursivité. e)
Erreur | Compilation Exécution | Raison ou raison possible
Array index out of bounds | Exécution | Raison : Une valeur d'indice en dehors de l'intervalle de validité [0,t-1] est utilisée pour accéder à un élément d'un tableau de taille t selon la dimension considérée. Exemple : t[10] t[5], t[-1] pour un tableau t de dimension 1 et de taille 5
Stack overflow | Exécution | Raison : Une profondeur de récursivité trop importante est atteinte.
Variable might not have been initialized | Compilation | Raison : Le compilateur pense que la valeur contenue dans une variable est utilisée alors qu'aucune valeur n'aurait été affectée à cette variable. Attention : Cette erreur est susceptible d'être un faux positif. Attention : Le compilateur peut ne pas détecter toutes les erreurs de programmation de ce type.
Cannot find symbol | Compilation | Raison : Le programme compilé utilise un item sensé désigner une variable, une fonction, un type primitif, un type agrégé, un champ de type agrégé ou tout autre item qui n'est pas un des mots réservés du langage de programmation (class, static, public, private, for, while, if, switch, break, final, ...) alors que cet item est inconnu. Exemples : variable non déclarée, faute d'orthographe sur un nom de fonction, fonction de bibliothèque non présente ou non accessible, ...
Null pointer exception | Exécution | Raison possible : Le programme tente d'utiliser le contenu d'une variable ou d'un champ de type agrégé devant être déclaré ou initialisé par new (type agrégé, tableau) mais qui ne l'a pas été.
Exercice n°2 Les explications données ci-dessous n'étaient pas demandées. Remarque : Donner ce genre d'explications facilite beaucoup la compréhension de ce que vous avez voulu écrire sans parfois y arriver totalement correctement. Dans les deux cas, le traitement réalisé étant le même, la même signature de sous-algorithme est développée. Il s'agit d'une action car seuls des affichages sont réalisés. Cette action prend un seul paramètre en entrée, le nombre entier n à traiter. a) Implantation récursive Si le nombre n à traiter est supérieur ou égal à 10, il contient plus de 1 chiffre. Il convient de retirer le chiffre des unités à n et de lancer l'affichage des chiffres du nombre ainsi obtenu en utilisant la récursivité. Ensuite, quelle que soit la valeur de n, le chiffre des unités de n est affiché. Pour retirer le chiffre des unités, on divise par 10. Pour extraire le chiffre des unités, on prend le modulo par 10. b) Implantation sans récursivité Beaucoup d'implantations sont possibles. Toutes se heurtent au problème que la décomposition (pour affichage) d'un nombre entier n en ses chiffres doit être réalisée de gauche à droite alors qu'il est plus simple de la réaliser de droite à gauche. La méthode proposée consiste à déterminer, dans un premier temps, le nombre entier puissance de 10 (nommons le fact) qui utilisé comme diviseur sur n permet de trouver le chiffre de poids le plus fort de n (le chiffre le plus à gauche). La détermination de fact est réalisée itérativement en multipliant fact, initialement affecté avec la valeur 1, par 10 autant de fois qu'il est nécessaire de diviser n par 10 pour que n devienne strictement inférieur à 10. Une fois fact connu, on peut extraire et afficher de proche en proche tous les chiffres de n en itérant sur le traitement consistant à diviser n par fact de façon à trouver et afficher un chiffre puis, pour préparer l'exécution suivante de la séquence d'instructions de l'itération, à retirer à n le chiffre que l'on vient d'obtenir en le remplaçant par n modulo fact et enfin en divisant fact par 10. A force de divisions par 10, fact devient égal à 0 avec pour signification que l'on n'a plus de chiffre à afficher. Une variable auxiliaire nb est utilisée pour éviter d'écraser n avec une autre valeur que celle obtenue en paramètre. { Action d'affichage des chiffres d'un entier } { dans le sens poids fort vers poids faible } { Implantation récursive } { Paramètre d'entrée : } { n : L'entier positif ou nul à traiter } action affichageRecursif(-> entier n) si n >= 10 alors affichageRecursif(n/10) fsi afficherln(n%10) fin action /* Fonction d'affichage des chiffres d'un entier */ /* dans le sens poids fort vers poids faible */ /* Implantation non récursive */ /* Paramètre d'entrée : */ /* n : L'entier positif ou nul à traiter */ public static void affichageNonRecursif(int n) { int fact = 1; int nb = n; while ( nb >= 10 ) { nb = nb/10; fact = fact*10; } do { int chiffre = n/fact; Ecran.afficherln(chiffre); n = n%fact; fact = fact/10; } while ( fact != 0 ); } Problème En (a), (b), (c) et (e), vous trouverez quelques lignes d'explications concernant les sous-algorithmes développés. La rédaction de ces explications n'était pas demandée mais aurait souvent aidé à la compréhension de ce que vous avez écrit. En (d) et (f), vous trouverez les réponses attendues aux questions. Le sous-algorithme correspondant à la question (f) est donné en fin de solution, mais l'écriture effective sous forme algorithmique n'était pas demandée. a) Il s'agit ici de créer un jeu de 52 cartes. Une fonction est donc développée qui retourne le tableau de 52 carte créé. Cette fonction ne présente pas de paramètre car aucune information n'a à être connue pour créer les 52 cartes. Le traitement réalisé par cette fonction est construit par imbrication de deux boucles "pour" permettant de parcourir les couples (couleur,valeur) dans l'ordre demandé. La boucle externe permet de parcourir les 4 couleurs : de 1 à 4 par pas de 1. La boucle interne permet de parcourir les 13 valeurs par ordre décroissant : de 14 à 2 par pas de -1. Un problème particulier est de trouver l'indice où placer le couple (couleur,valeur) représentant chaque carte. Les deux boucles "pour" les génèrent dans l'ordre souhaité. Une variable i initialisée à 0 avant l'amorçage des deux itérations est utilisée comme indice. A chaque nouvelle carte, cette variable est incrémentée de 1. b) Une action est développée car il s'agit ici de réaliser la modification d'un tableau de carte existant. On utilise la possibilité offerte lors du passage d'un paramètre en entête de réaliser un passage en entrée et en sortie : en modification. Une autre possibilité aurait consisté à développer une fonction admettant le tableau à modifier comme paramètre d'entrée et retournant ce tableau après modification. Cette solution est admissible. Toutefois, elle est moins bonne que la première car elle laisse à penser que le tableau retourné, tout en contenant les mêmes cartes réorganisées, pourrait être situé à une adresse mémoire différente de celle du tableau passé en entête. Cette éventualité n'est pas du tout envisagée dans l'énoncé. Le tableau passé en paramètre comportant au moins deux cartes, il n'existe pas de cas particulier, c'est à dire que les deux paquets tc1 et tc2 comportent au minimum une carte. Le traitement implanté réalise exactement les opérations de l'énoncé : - Détermination de la taille t du tableau passé en paramètre. - Tirage au sort de la valeur n. - Déclaration des tableau tc1 et tc2 avec leurs tailles respectives n et t-n. - Copies successives (boucles "pour" successives) dans tc1 et tc2 des cartes de tc. - Copies successives dans tc (boucles "pour" successives) des cartes contenues dans tc2 et tc1. Attention : Les indices utilisés dans tc1 et tc2 pour ces opérations de copie doivent être décalés par rapport à ceux utilisés dans tc faute de quoi les cartes ne sont pas copiées au bon endroit et une erreur de type "Array index out of bounds" intervient. c) Pour les mêmes raisons que celles de la question (b), une action est développée avec comme paramètre unique le tableau de carte à mélanger passé en entrée et en sortie. L'action de la question (b) permettant de couper un tableau de cartes est utilisée. Elle est exécutée au sein d'une boucle "pour" de façon à l'être un nombre de fois égal au nombre de cartes du tableau (calculé puis stocké au préalable dans la variable t). Attention : Il existe un cas particulier. Quand le tableau ne comporte qu'une seule carte, utiliser l'action de la question (b) conduirait inéluctablement à un plantage. Il est donc nécessaire de prévoir cette situation. Dans ce cas, il a été choisi de ne rien faire car un tableau comportant une seule carte est non mélangeable donc intrinsèquement toujours mélangé. d) La complexité de ce sous-algorithme s'exprime comme une fonction de la taille n du paquet de cartes à mélanger (taille du tableau de cartes passé en paramètre). Ce sous-algorithme implante une boucle "pour" réalisant n exécutions du sous-algorithme coupant le paquet de cartes. Ce sous-algorithme implante quatre boucles "pour" réalisant 2 parcours complets de traitement du tableau. Le nombre d'instructions exécutées devrait donc être de l'ordre de 2*n et donc de l'ordre de n. Au total le nombre d'instructions est donc de l'ordre de n*n -> La complexité évaluée est en O(n2). Remarque : Les ordres de temps d'exécution des fonctions hasard et longueur ne sont pas connus. On peut toutefois supposer qu'ils sont en O(1) pour hasard qui de toute façon ne dépend pas de n et au pire en O(n) pour longueur dans le cas où le parcours du tableau est nécessaire au calcul de sa taille (plus probablement en O(1) car la taille peut être stockée en attribut de chaque tableau). Ces valeurs ne change pas l'estimation posée ci-dessus. e) Il s'agit ici de tester l'existence ou non d'un couple de cartes consécutives de valeurs "consécutives" au sein d'un paquet de cartes modélisé par un tableau de carte. Une fonction est donc conçue. Elle retourne un booléen de valeur vrai si le paquet ne comporte pas de tel couple de cartes, faux sinon. Elle prend en paramètre un seul paramètre, le tableau de carte à tester. Celui-ci est passé en entrée. Attention, le tableau de carte passé en paramètre peut ne comporter qu'une seule carte. Si c'est le cas, il ne comporte pas de couple de cartes consécutives de valeurs consécutives car il ne comporte pas de couple de cartes. Il convient donc de retourner vrai. Une boucle de parcours des couples de cartes consécutives est programmée. Si la taille du tableau de cartes est n, il y a potentiellement n-1 couples à tester. Le choix du type de boucle conduit à proscrire absolument le "pour" car celui-ci n'étant interrompu que par terminaison normale au bout du parcours des n-1 couples, nous serions obligé de continuer à parcourir les couples de cartes même quand l'un d'eux de valeurs consécutives aurait été trouvé. Dans cette situation, il convient d'arrêter le parcours et de retourner faux car on sait que le tableau n'est pas "bien mélangé". Afin de ne pas passer pour un programmeur ne connaissant pas les bonnes pratiques du métier, on ne s'autorise pas à réaliser un return dans un "pour" (*). On ne s'autorise pas non plus à toucher, à l'intérieur d'un "pour", à la variable support de comptage du "pour", ni non plus à sa borne finale (*). La boucle programmée est de type "tant que" car son contenu peut fort bien avoir à ne pas être exécuté si le tableau ne comporte qu'une carte. On évite ainsi d'avoir à programmer un "si" préalable testant cette hypothèse. La condition de continuation du "tant que" est la composition de deux conditions canoniques devant être vérifiées (composition par et) pour que le "tant que" continue : (1) Il doit y avoir encore un ou des couples de cartes à tester (on n'est pas arrivé au bout du tableau de cartes). -> La variable i, initialisée à 0 avant l'amorçage du "tant que", donnant l'indice le la première carte du couple de cartes à tester doit être inférieure strictement à la taille t du tableau - 1 (le dernier couple de cartes est composé des cartes d'indices t-2 et t-1). (2) On ne doit pas encore avoir trouvé de couple de cartes consécutives de valeurs consécutives. -> La variable booléenne res retournée par la fonction, initialisée à vrai avant l'amorçage du "tant que", doit toujours avoir vrai pour valeur. Un "si" est utilisé dans le "tant que" pour tester si les cartes d'indices i et i+1 sont de valeurs consécutives. Si c'est le cas, res est affectée avec faux, ce qui aura pour conséquence immédiate l'arrêt de la boucle et le retour de faux par la fonction. Si ce n'est pas le cas, i est incrémenté de 1 pour préparer l'itération suivante et impliquer l'arrêt ou non du "tant que" si on a fini le parcours du tableau. Pour faciliter le développement, faciliter le déboguage et améliorer la lisibilité du code, le choix a été fait d'implanter une fonction à résultat booléen permettant de tester si deux carte quelconques passées en paramètre en entrée sont de valeurs consécutives. (*) Au risque de vous le faire reprocher, vous pourrez vous autoriser ces pratiques de développement quand vous aurez compris les risques qui y sont liés, pourquoi il ne faudrait pas les utiliser et que vous conviendrez, tout en le faisant, qu'il ne faut pas le faire : faites ce que je dis, pas ce que je fais. f) Le but est ici d'obtenir une meilleure efficacité de fonctionnement. Le terme efficacité n'ayant pas de signification particulière, on va viser deux objectifs : - Le mélange est mieux réalisé qu'en (c). Ce n'est pas difficile car le sous-algorithme de la question (c) ne mélange pas vraiment un paquet de cartes. En effet, couper un paquet plusieurs fois est équivalent à ne le couper qu'une fois, la dernière. - La complexité est améliorée pour devenir meilleure que O(n2). Beaucoup de techniques permettent d'atteindre ces deux buts. En voici une qui s'inspire d'un traitement pouvant être réalisé naturellement par une personne : On tient le paquet de cartes dans une main, on le pose en entier sur une table, on tire au sort les cartes du paquet sur la table l'une après l'autre en les replaçant au fur et à mesure les unes sur les autres dans la main où elles étaient initialement placées. Algorithmiquement cela donne : Les cartes sont intégralement recopiées dans un tableau auxiliaire sans en changer l'ordre. Ensuite, on effectue l'opération inverse en recopiant les cartes du tableau auxiliaire dans le tableau initial mais en les tirant au sort dans le tableau auxiliaire. De façon à ne pas créer de "trou" dans le tableau auxiliaire, chaque fois qu'une carte en est retirée, elle est remplacée par la dernière carte du tableau auxiliaire et la variable qui permet de savoir combien de cartes sont encore à retirer est décrémentée de 1. Le déplacement des dernières cartes du tableau auxiliaire vers les emplacements libérés a pour but, bouchant les trous créés, de ne pas avoir à détecter ces trous lorsque l'on tire au sort une carte à retirer. Cela diminue la complexité et concourt au mélange des cartes. Le sous-algorithme ainsi obtenu est de complexités O(n) car il implante deux parcours complets du tableau de cartes. Une expérimentation réalisée sur un tableau de 52 cartes tel que généré par la question (a) mélangé par cette technique montre que, statistiquement, tout au plus quelques couples de cartes consécutives de valeurs consécutives restent présents dans le tableau et que même, assez fréquemment, le tableau est "bien mélangé". structure carte entier valeur entier couleur fin structure { Fonction de création d'un jeu de 52 cartes } { Les cartes sont ordonnées par ordre coissant } { de couleur et à couleurs identiques, } { par ordre décroissant de valeur } { Pas de paramètre d'entête } { Retour : Le tableau de 52 cartes créé } carte [] fonction creerJeuDeCarte() carte [52] jeu entier i <- 0 entier c entier v pour c de 1 à 4 faire pour v de 14 à 2 pas -1 faire jeu[i].valeur <- v jeu[i].couleur <- c i <- i+1 fait fait retourner jeu fin fonction { Action de coupe d'un paquet de cartes } { La position où la coupe est réalisée est tirée } { au sort de façon qu'il y ait au moins une carte } { dans le sous-paquet "inférieur" et au moins } { une carte dans le sous-paquet "supérieur" } { Paramètre d'entrée/sortie : } { tc : Le tableau d'au moins 2 carte à couper } action couper(-> carte [] tc ->) entier t <- longueur(tc) entier n <- 1+(entier) (hasard()*(t-1)) carte [n] tc1 carte [t-n] tc2 entier i pour i de 0 à n-1 faire tc1[i] <- tc[i] fait pour i de n à t-1 faire tc2[i-n] <- tc[i] fait pour i de 0 à t-1-n faire tc[i] <- tc2[i] fait pour i de t-n à t-1 faire tc[i] <- tc1[i-t+n] fait fin action { Action de "mélange" d'un paquet de cartes } { Le paquet de cartes est coupé autant de fois } { qu'il contient de cartes } { Attention : Il n'est pas possible de couper } { un paquet de une carte donc, dans ce cas, } { le paquet n'est pas modifié } { Paramètre d'entrée/sortie : } { tc : Le tableau d'au moins 1 carte à mélanger } action melanger(-> carte [] tc ->) entier t <- longueur(tc) entier i si t > 1 alors pour i de 1 à t faire couper(tc) fait fsi fin action { Fonction de test si deux cartes } { sont de valeurs consécutives } { Paramètres d'entrées : } { c1 : La première carte } { c2 : La seconde carte } { Retour : Booleen vrai si c1 et c2 sont } { des cartes consécutives, faux sinon } booleen fonction sontCartesConsecutives(carte c1,carte c2) retourner ( c1.couleur == c2.couleur ) et ( ( c1.valeur == c2.valeur+1 ) ou ( c1.valeur == c2.valeur-1 ) ) fin fonction { Fonction de test si un jeu de cartes } { est "bien" mélangé } { (i.e. sans cartes consécutives de valeurs } { consécutives) } { Attention : Un jeu ne comportant qu'une seule } { carte est toujours bien mélangé } { Paramètre d'entrée : } { tc : Le tableau d'au moins 1 carte à tester } { Retour : Booleen vrai si le tableau de carte } { tc est bien mélangé, faux sinon } booleen fonction estBienMelange(-> carte [] tc) booleen res <- vrai entier t <- longueur(tc) entier i <- 0 tantque ( i < t-1 ) et ( res == vrai ) faire si sontCartesConsecutives(tc[i],tc[i+1]) == vrai alors res <- faux sinon i <- i+1 fsi fait retourner res fin fonction { Action de mélange d'un paquet de cartes } { Les cartes sont sorties du paquet } { pour être placées dans un paquet auxiliaire } { puis replacées à l'intérieur de leur paquet } { d'origine en les tirant au sort à l'intérieur } { du paquet auxiliaire } { Paramètre d'entrée/sortie : } { tc : Le tableau d'au moins 1 carte à mélanger } action mieuxMelanger(-> carte [] tc ->) entier t <- longueur(tc) carte [t] tcAux entier i entier nb <- t entier p pour i de 0 à t-1 faire tcAux[i] <- tc[i] fait pour i de 0 à t-1 faire p =(entier) (hasard()*nb) tc[i] <- tcAux[p] nb <- nb-1 tcAux[p] <- tcAux[nb] fait fin action
Commentaires sur la notation Les notes apparaissant en entête de copie sont les notes globables des trois exercices et le malus attribué quand les spécifications des entêtes de fonction n'ont pas été réalisées (contrairement à ce qui était explicitement demandé) : - Exercice 1 : note sur 20 points - Exercice 2 : note sur 11 points - Problème : note sur 18 points - Malus : jusqu'à 1 point en moins La formule de calcul de la note glabale est : note exercice 1 * 0,375 + note exercice 2 * 0,4 + note problème * 0,7 + malus Exercice 1 - Question (a) : 3 points - Question (b) : 5 points - Question (c) : 3 points - Question (d) : 4 points - Question (e) : 5 points Exercice 2 - Question (a) : 7 points pour l'entête, la décomposition mathématique, l'implantation de la récursivité et la bonne gestion de la fin de la récursivité - Question (b) : 4 points Exercice 3 - Question (a) : 3 points pour l'entête, l'implantation algorithmique du traitement et le fait que cela marche - Question (b) : 5 points pour l'entête, l'implantation algorithmique du traitement et le fait que cela marche - Question (c) ; 2 points pour la formule et les explications afférentes - Question (d) : 2 points pour l'entête, l'implantation algorithmique du traitement et le fait que cela marche - Question (e) : 4 points pour l'entête, l'implantation algorithmique du traitement et le fait que cela marche - Question (f) : 2 points