Exemple de DS3 - BAC BLANC 2008 (Sfax)

Exercice 1 : 4 Points { a) -2p ; b) – 2p }

Pour déterminer le carré d’un entier naturel n, on utilise une méthode dont le principe est le suivant :
Le carré d’un entier naturel n est égal à la somme des n premiers entiers impairs
Exemple : pour n = 10 : 102 = 1 + 3 + 5 + 7 + 9 + 11 + 13 + 15 + 17 + 19

Travail demandé :

Établir l’analyse puis l’algorithme d’une fonction qui utilise la méthode décrite ci-dessus pour retourner le carré d’un entier naturel n.
Proposer deux solutions :
a) Solution itérative
b) Solution récursive


Exercice 2 : 4 Points { a) – 0.5p ; b) – 1p ; c) – 2.5p }

On considère une suite U définie par :
U1 = 1
U2 = 2
Ui = Ui-1 + (x * Ui-2) (i ≥ 3)
On désire vérifier si un entier t donné est un terme de la suite U en retournant son rang r dans l’affirmative (x est un entier naturel non nul)

Travail demandé :

a) Quel est l’ordre de récurrence de cette suite ?
b) Pour n = 6 et x = 2, donner la valeur du nième terme de la suite U en précisant successivement les valeurs de i, U1, U2 et U
c) Établir l’analyse puis en déduire l’algorithme d’une fonction qui retourne le rang r (r = -1 si t ne représente pas un terme de la suite U)
NB. : La solution ne doit pas utiliser la structure de données « tableau »

Problème : 12 Points
Une société se propose d’organiser un concours pour n candidats dont leurs données sont les suivantes :
Code du candidat - « code » - Entier positif unique
Code secret du candidat - « code_sec » - Chaîne de caractères initialisée à vide lors de la saisie
Niveau scolaire - « niv_scol » - Chaîne dont le nombre de caractères ne dépasse pas 20
Moyenne du concours - « moy_conc » - Réel de 0 à 20

Pour gérer les données des candidats, les responsables de la société lance un appel d’offre pour informatiser ces données par un programme qui offre à l’utilisateur un menu de cinq choix définis selon la valeur d’un entier saisit comme suit :
• La valeur 1, pour saisir les données relatives à n candidats dans un tableau à une dimension T (n est une constante)
• La valeur 2, pour affecter aux champs « code_sec » le code secret de chaque candidat
NB : Le code secret d’un candidat est celui d’une chaîne obtenue par la conversion en hexadécimal (base 16) du code de ce candidat
Exemple :
code = 2563
code_sec = A03 (conversion en hexadécimal du code 2563)
niv_scol = Bac
moy_conc = 11

• La valeur 3, pour trier les données des candidats par ordre décroissant de leurs moyennes.
Utiliser la méthode de tri rapide

• La valeur 4, pour afficher les données des candidats.
• La valeur 5, pour quitter le programme en affichant le message « Au revoir »

Travail demandé :
1) Quelles sont les structures de données adéquates à ce problème ? Justifier le choix de chaque structure proposée.
2) Analyser et déduire l’algorithme du programme principal qui permet de réaliser le traitement décrit précédemment en le décomposant en modules.
3) Analyser chacun des modules envisagés précédemment et en déduire les algorithmes correspondants.