Département : Technologies de l’Informatique
CORRIGE DU DEVOIR DE CONTROLE
Classe(s) : L1-INFO 1 à 5 ECUE : Algorithmique &Programmation
Documents Non Autorisés Enseignant(s) : H. Elouedi, S. Kacem et B. Guettat
Calculatrice Non Autorisée Nombre de pages : 1 Durée : 1 heure Date : 5 Novembre 2018
Exercice 1 : Conversion de jours 4 points
Ecrire un algorithme permettant de convertir un nombre donné de jours Nbjen années (Na),
semaines (Ns) et jours (Nj). L’année contient 365 jours. L’affichage est comme suit :
Exemple :755 jours équivaut à : 2 ans, 3 semaines et 4 jours.
Algorithme conversion
Variable Nbj, Na, Ns,Nj : entier
Début
Répéter
Ecrire("donner le nombre de jours")
Lire(Nbj)
Jusqu’à Nbj>0
NaNbj div 365
Ns Nbj mod 365 div 7
Nj Nbj mod 365 mod 7
Ecrire(Nbj, "jours équivaut à : ", Na, "ans, ", Ns, "semaines et", Nj, "jours")
fin
Exercice 2 : Tirage de nombres 8 points
Ecrire un algorithme qui simule le jeu suivant :
a- A tour de rôle, l’ordinateur et le joueur choisissent un nombre qui ne peut prendre que 3
valeurs :0, 1 ou 2.
L’instruction :N Random(3), permet de choisir au hasard (par l’ordinateur) un nombre N
entre 0 et 2. Le joueur doit saisir le nombre qu’il désire (0, 1 ou 2).
b- Le jeu se déroule selon le principe suivant : Si la différence entre les nombres choisis vaut :
2, le joueur qui a proposé le plus grand nombre gagne un point.
1, le joueur qui a proposé le plus petit nombre gagne un point.
0, aucun point n’est marqué.
c- Le jeu se termine quand l’un des joueurs totalise 10 points.
1/4
Département : Technologies de l’Informatique
Algorithme jeu
Variable Nj, No, Tj,To : entier
Début
Tj0
To0
Répéter
Répéter
Ecrire("Donner votre nombre ")
Lire(Nj)
Jusqu’à Nj>=0 et Nj<=2
Norandom(3)
Selon No-Nj faire
2 : ToTo+2
-2 : Tj Tj+2
1 : ToTo+1
-1 : Tj Tj-1
Fin selon
Jusqu’à Tj>=10 ou To>=10
Si Tj>=10 alors
Ecrire("Tu as gagné")
Else
Ecrire("Tu as perdu")
Fin si
Fin
Exercice 2 : Recherche 8 points
On dispose d’un tableau T de n entiers, de taille maximale 100. On veut vérifier l’existence d’un
entier x saisi à partir du clavier dans le tableau T.
1. Rappeler l’algorithme de recherche séquentielle d’une valeur x dans un tableau T (en donnant
les déclarations nécessaires et en faisant les contrôles de saisie nécessaires et le remplissage du
tableau). (3 points)
Algorithme Recherche_seq
Constante Nmax=100
Variable T : Tableau [1..Nmax] entier
N, i : entier
Début
Répéter
Ecrire ("Donner le nombre d’éléments du tableau")
Lire(N)
2/4
Département : Technologies de l’Informatique
Jusqu’à N>0 et N<=Nmax
Pour i de 1 à N faire
Ecrire("Donner l’élément num ", i)
Lire (T[i])
Fin pour
Ecrire("Donner l’élément à chercher")
Lire (x)
i 1
Tant que T[i]<>x et i<N faire
i i+1
fin tant que
si T[i]=x alors
Ecrire(x, "se trouve à la position ", i)
sinon
Ecrire(x, "ne de trouve pas dans le tableau")
fin si
fin
2. Dans cette question, on veut écrire un algorithme de recherche d’un élément x dans le tableau
Tde n entiers en partant des deux extrémités. Cela veut dire que pour chercher x dans T, on
partira au même temps du premier élément et du dernier élément, puis on continuera en
incrémentant à partir de la gauche et en décrémentantà partir de la droite.
a. Quelle sera la condition d’arrêt de la recherche pour cet algorithme ? (1 point)
Si i est le compteur de début et j est le compteur de fin du tableau, la condition d’arrêt de la
boucle sera (i >= j ou T[i]=x ou T[j]=x)
b. Ecrirel’algorithme de façon claire et lisible (sans reprendre le remplissage du tableau,
seulement le traitement nécessaire à la recherche). (3 points)
Algorithme Recherche2
Constante Nmax=100
Variable T : Tableau [1..Nmax] entier
N, i, j, x : entier
Début
…
i1
jN
tant que i<j et T[i]<>x et T[j]<>x faire
i i+1
3/4
Département : Technologies de l’Informatique
j j-1
fin tant que
si T[i]=x alors
Ecrire(x,"se trouve à la position ", i)
Sinon
Si T[j]=x alors
Ecrire(x,"se trouve à la position", j)
Sinon
Ecrire(x, "ne de trouve pas dans le tableau")
Fin si
Fin si
Fin
c. Pour un tableau T de 20 entiers, évaluez combien de tests au maximum, va-t-on effectuer
en appliquant l’algorithme de recherche séquentielle, puis celui de la question b. Conclure.
(1 point)
En appliquant l’algorithme de recherche séquentielle, on va effectuer au maximum 19 tests (dans
la boucle)
Dans le deuxième algorithme, on va effectuer 10 tests au maximum (dans la boucle)
Conclusion : Le deuxième algorithme est meilleur de point de vue temps d’exécution.
4/4
