Ministère de L’Education
C.R.E .Medenine Devoir de Synthèse N°3
*****
Lycée Ibn Rochd Djerba Midoun Epreuve : Algo &Prog DATE : 23/05/2025
A.S :2024/2025 Classes : 3 SI 1& 2 Durée : 2 heures
Profs : b .Kamel & [Link]
Nom et prénom : ……………………………………………… Groupe :…… N°……….
Exercice 1 : (1,75 pts) 20
Dans un contexte informatique et pour chacune des propositions cités ci-dessous,
mettre dans chaque case la lettre V si la proposition est correcte ou la lettre F dans
le cas contraire.
Les algorithmes d’optimisation
Sont des algorithmes d’approximation
Calculent des valeurs exactes.
Calculent une valeur approchée de la valeur maximale de la solution possible.
cherchent la meilleure solution possible entre plusieurs solutions approchées
possibles à un epsilon près.
Soient deux enregistrements e1 et e2 de types enreg.
enreg un est type prédéfini.
Pour affecter le contenu de e1 dans e2 on écrit : e2←e1.
Les champs de e1 doivent être de type prédéfini.
Exercice 2 : (4,25 pts)
A- Soit l’algorithme de la fonction Inconnue :
Fonction inconnue ( ch1 , ch2 : chaine) : ………….
Debut
Répéter
p ← pos ( ch1[0] , ch2 )
Si p ≠ -1 alors
ch1 ← souschaine (ch1 , 1 , long(ch1) ) TDOL
Fin si Objets Type / Nature
Jusqu’à p = -1 ou ch1 = "" P Entier
Retourner p = -1
Fin
1- Compléter l’entête de la fonction inconnue par le type de résultat.
2- Quel est le résultat retourné par la fonction inconnue pour chacun des
appels suivants :
o Inconnue ("NICHE" , "CHIENNE" ) Résultat : ……………..
o Inconnue ("1577" , "705" ) Résultat : ……………..
o Inconnue ("705" , "1577" ) Résultat : ……………..
3- Déduire le rôle de cette fonction
………………………………………………………………………………………………
………………………………………………………………………………………………
4- Modifier la structure Répéter…Jusqu’à par Tant que …. Faire an appliquant
les modifications nécessaires.
B- Deux entiers N1 et N2 sont dits anagrammes lorsqu’ils sont composés exactement
des mêmes chiffres, apparaissant le même nombre de fois, mais éventuellement
dans un ordre différent.
Exemples:
- N1 = 1164 et N2 = 6141 sont anagrammes
- N1 = 905 et N2 = 9055 ne sont pas anagrammes
- N1 = 405 et N2 = 554 ne sont pas anagrammes
Travail à Faire :
En utilisant la fonction inconnue, écrire l’algorithme d’un module qui permet
d’afficher un message indiquant si N1 et N2 sont anagrammes ou non avec N1 et N2
deux nombres strictement positifs saisis au niveau du programme principal.
Exercice 3 : (2 pts)
Soit la formule de zêta de Rieman suivante :
2 22 32 52 72 112
* * * * * ...
6 2 2 1 32 1 52 1 7 2 1 112 1
Ecrire un algorithme d’un module qui utilise l’expression ci-dessus pour déterminer une
valeur approchée de à 10-4 prés.
N.B : Le calcul s’arrête quand la différence entre deux valeurs consécutives de cette
expression devient strictement inférieure à une erreur epsilon donnée en paramètre (10-4).
Solution :
………………………………………………………………………………………………………
T.D.O.L :
……………………………………………………………………………………………………..
Objet T/N
………………………………………………………………………………………………………
……………………………………………………………………………………………………..
………………………………………………………………………………………………………
……………………………………………………………………………………………………..
………………………………………………………………………………………………………
……………………………………………………………………………………………………..
………………………………………………………………………………………………………
……………………………………………………………………………………………………..
………………………………………………………………………………………………………
……………………………………………………………………………………………………..
………………………………………………………………………………………………………
……………………………………………………………………………………………………..
………………………………………………………………………………………………………
……………………………………………………………………………………………………..
Exercice 3 : (12 pts)
Jeu du Labyrinthe
Objectif :
- Simuler le jeu du labyrinthe sur une matrice M d’ordre n.
- Aider un joueur à atteindre la case "E" (qui peut être
n'importe où dans la matrice) en suivant une séquence de
mouvements.
Chaque mouvement correspond à une position de la
matrice (ligne, colonne).
Représentation du labyrinthe :
La matrice est composée des cases, où chaque case est caractérisée par :
Son type
- case normale, accessible représenté par le caractère "1".
- case interdite représenté par le caractère "0".
- case finale représenté par le caractère "E".
la valeur de sa pénalité
Entier entre 10 et 30 choisie aléatoirement par le programme.
N.B : Pour une case de type normale la valeur de pénalité est automatiquement égale à 0.
Chaque joueur commence avec un solde de 100 points.
Règles du jeu :
- Le joueur saisit à l’avance une chaine (chemin de parcours) de longueur paire composé que par des
chiffres (Tous les chiffres doivent être inférieurs à n).
- À chaque déplacement :
Le programme extrait deux chiffres de la chaine saisie : le premier chiffre représente le numéro
de la ligne de la case destination et le deuxième chiffre représente le numéro de la colonne de la
case destination.
* Si la case est ("1", 0), il avance sans payer. (type case libre)
* Si la case est ("0", X), il paie X points. S’il n’a pas assez de points, il perd. (type case interdite)
* Si la case est ("E", 0), il gagne immédiatement. (type case finale)
et ainsi de suite….
🎮 Fin du jeu (cas possibles) :
1. Le joueur atteint la case "E" → Victoire √.
2. Il n’a plus assez de points pour payer une case interdite → Défaite ❌.
3. Il termine tous ses mouvements sans atteindre "E" → Défaite ❌.
N.B : Le joueur peut atteindre la case finale "E" sans terminer son parcours (il reste encore des
mouvements à effectuer). Dans ce cas, le jeu s’arrête et il gagne directement en dépit du reste des
mouvements.
💰 Récompense :
Si le joueur gagne, on considère le parcours comme une séquence de 0 et 1 :
- 1 pour les cases (1, 0) et la case (E, "0")
- 0 pour les cases (0, X)
La séquence est ensuite convertie d’un nombre binaire vers un entier décimal.
Exemples de parcours
✅ Exemple 1 : ❌ Exemple 2 :
Victoire avec récompense Défaite
Matrice : Matrice :
(1,0) (0,20) (1,0) (1,0) (0,20) (1,0)
(1,0) (1,0) ("E",0) (1,0) (1,0) (1,0)
(0,10) (0,30) (1,0)
("E",0) (0,30) (1,0)
Chemin de parcours : "00010212" Chemin de parcours : "122111"
Score initial : 100 Score initial : 100
➡ Déroulement : ➡ Déroulement :
- case (0,0) :libre ✅ - case (1,2) :libre ✅
- case (0,1) : interdit (pénalité= 20)➜ -20 pts - case (2,1) : interdit (pénalité= 30)➜ -30 pts
- case (0,2) :libre ✅ - case (1,1) :libre ✅
- case (1,2) : E ➜ Victoire Chemin de parcours est terminé, mais "E" n’est
➜ Mission réussie avec un score de 80 points pas atteinte à la fin → ❌ défaite.
chemin = [1, 0, 1, 1] → binaire "1011" = 11 ➜ Le programme affichera :
Récompense : 11 points bonus. Mission échouée
➜ Le programme affichera :
Mission réussie avec un score de 80 points
Récompense : 11 points bonus
Nous proposons d’écrire l’algorithme d’un programme qui permet de simuler ce jeu.
Pour ce faire il s’agit :
- De saisir le chemin de parcours.
- Remplir une Matrice M d’ordre n (3≤ n ≤ 30).
Remarques
- Chaque case est formée par deux champs : ty et pen.
le champ ty : est choisi aléatoirement par le programme et prend "0" ou "1"
le champ pen :
o est un entier entre 10 et 3O choisi aléatoirement par le programme dans le cas où
le champ ty prend la valeur "0"
o prend la valeur 0 dans le cas où le champ ty prend la valeur "1"
- Après le remplissage de la matrice le programme choisi aléatoirement deux entiers x et y qui
représentent successivement le numéro de la ligne el le numéro de la colonne de la case "E" : donc il
affecte au champ ty de cette case la valeur "E" et au champ pen la valeur 0 et le jeu commence…
- D’afficher le résultat final du parcours selon le procédé décrit précédemment :
- Mission échouée : si le joueur n’atteint pas la case"E"
- Si le joueur atteint la case "E", on affiche :
Mission réussie avec un score de [nombre] points
Récompense : [nombre] points bonus
Travail demandé :
1) Ecrire l’algorithme du programme principal en le décomposant en modules.
2) Ecrire les algorithmes et les tableaux de déclaration des objets relatifs aux modules envisagés