Exercice 01 : Généralités sur les Concepts Algorithmique /4pts
Analyse & Exécution d’un Pseudocode : /4pts
ALGORITHME 01
Fonction SN1(y : entier, z : entier): entier;
Début
si ((y DIV 2) * 2 = y et (z DIV 2) * 2 = z) alors
Retourner(y*z)
fsi
si (y<=1) alors
Retourner(z) ;
sinon
Retourner(y * SN1(y-1, z ));
fsi
Fin;
Questions :
- Dénichez les potentielles erreurs dans cet algorithme. 0.25pt
- Pour (y=5 et z = 5) et (y = 4 et z = 4), dire ce que réalise cet algorithme. (1+1)2pts
SOLUTION :
le point virgule dans le premier (si)
Exécution :
Cas 1 : y = 5 et z = 5
Premier appel : SN1(5, 5)
y=5 (impair), z=5 (impair).
Condition (y DIV 2) * 2 = y : Faux.
Condition y <= 1 : Faux.
Appel récursif : Retourner(5 * SN1(4, 5)).
Deuxième appel : SN1(4, 5)
y=4 (pair), z=5 (impair).
Condition (y DIV 2) * 2 = y : Vrai pour y, mais Faux pour z.
Condition y <= 1 : Faux.
Appel récursif : Retourner(4 * SN1(3, 5)).
Troisième appel : SN1(3, 5)
y=3 (impair), z=5 (impair).
Condition (y DIV 2) * 2 = y : Faux.
Condition y <= 1 : Faux.
Appel récursif : Retourner(3 * SN1(2, 5)).
Quatrième appel : SN1(2, 5)
y=2 (pair), z=5 (impair).
Condition (y DIV 2) * 2 = y : Vrai pour y, mais Faux pour z.
Condition y <= 1 : Faux.
Appel récursif : Retourner(2 * SN1(1, 5)).
Cinquième appel : SN1(1, 5)
y=1, z=5.
Condition y <= 1 : Vrai.
Retourne z = 5.
Retour des appels récursifs :
SN1(2, 5) retourne 2×5=10.
SN1(3, 5) retourne 3×10=30.
SN1(4, 5) retourne 4×30=120.
SN1(5, 5) retourne 5×120=600.
Résultat final : La fonction retourne 600.
Cas 2 : y = 4 et z = 4
Premier appel : SN1(4, 4)
y=4 (pair), z=4 (pair).
Condition (y DIV 2) * 2 = y : Vrai.
Retourne y×z=4×4=16.
Résultat final : La fonction retourne 16.
Résumé des Résultats
| Valeurs de y et z |
Résultat |
| y = 5, z = 5 |
600 |
| y = 4, z = 4 |
16 |
Conclusion Concrète
La fonction SN1 :
- Si y et z sont pairs, retourne directement y×z.
- Sinon, utilise une récursion pour multiplier y ! par z.
En d'autres termes, elle calcule un produit dépendant de la parité de y et z, et utilise la récursion pour multiplier y ! par z.
Exécution à la main :
Fonction SN2( K : entier) : entier ;
var X: entier ;
Début
X <- K;
tantque(K > 1) faire
K <- K – 2 ;
ftq
si(K = 1) alors
retourner X*X*X;
sinon
retourner X*X;
fin;
Questions :
- Dénichez les potentielles erreurs dans cet algorithme. 0.25pt
- Que fait la fonction SN2 (expliquer son prototype puis dire ce qu’elle fait) ? 0,75pt
SOLUTION :
Fsi
Exécution :
Prototype de la Fonction SN2
Le prototype de la fonction SN2 est le suivant:
Fonction SN2(K : entier) : entier;
- Paramètre d'entrée : K : Un entier passé en argument à la fonction.
- Valeur de retour : La fonction retourne un entier.
Ce que fait la Fonction SN2
La fonction SN2 effectue les étapes suivantes :
- Initialisation : La variable X est initialisée avec la valeur de K.
- Boucle tantque : La boucle continue tant que K>1. À chaque itération, K est décrémenté de 2 (K <- K - 2).
- Condition finale : Après la boucle, la fonction vérifie si K = 1. Si K = 1, la fonction retourne X^3 (c'est-à-dire X×X×X). Sinon, la fonction retourne X^2 (c'est-à-dire X×X).
Explication Concrète
La fonction SN2 détermine si la valeur initiale de K est impaire ou paire en réduisant K de 2 à chaque itération jusqu'à ce que K soit inférieur ou égal à 1.
- Si K devient égal à 1 après la boucle, cela signifie que la valeur initiale de K était impaire. Dans ce cas, la fonction retourne X^3.
- Si K devient égal à 0 après la boucle, cela signifie que la valeur initiale de K était paire. Dans ce cas, la fonction retourne X^2.
Exemples
Cas 1 : K = 5 (impair)
Initialisation : X=5.
Boucle tantque :
- Itération 1 : K=5−2=3.
- Itération 2 : K=3−2=1.
La boucle s'arrête car K=1.
Condition finale : K=1, donc la fonction retourne X^3=5^3=125.
Résultat : La fonction retourne 125.
Cas 2 : K = 4 (pair)
Initialisation : X=4.
Boucle tantque :
- Itération 1 : K=4−2=2.
- Itération 2 : K=2−2=0.
La boucle s'arrête car K=0.
Condition finale : K=0, donc la fonction retourne X^2=4^2=16.
Résultat : La fonction retourne 16.
Résumé des Résultats
| Valeur de K |
Parité |
Résultat |
| K = 5 |
Impaire |
125 |
| K = 4 |
Paire |
16 |
Conclusion
La fonction SN2 :
- Prend un entier K en entrée.
- Réduit K de 2 jusqu'à ce que K≤1.
- Retourne : X^3 si K était impair. X^2 si K était pair.
En d'autres termes, elle calcule le cube de K si K est impair, et le carré de K si K est pair.
Les affirmations suivantes sont-elles correctes ?
Répondre par Vrai ou Faux dans un mini-tableau (0.25*8) 2pts/ (Mauvaise(s) réponse(s) – 0,25pt)
- Dans une boucle POUR l’incrémentation s’effectue toujours en fin de boucle.
- Les actions internes d’une boucle REPETER peuvent ne pas être exécutées.
- Les actions d’une boucle POUR sont toujours exécutées après le test.
- Une fonction Récursive peut qu’avoir que des cas de bases dans sa définition propre.
- La recherche Dichotomique se fait toujours sur un tableau non trié.
- Un invariant de boucle est une propriété qui est vraie avant mais pas après chaque itération.
- Une action (bloc d’instruction) qui se répète jusqu’à ce qu’une condition soit remplie correspond à une boucle Répéter...Jusqu'à.
- Dans une boucle TANTQUE, le test est effectué avant chaque itération.
| 1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
| V |
F |
F |
F |
F |
F |
V |
V |
Exercice 02 : Structures Conditionnelles, Répétitives /4pts (1+1+1+1)
1) Ecrire 02 fonctions récursives fact(n) pour le calcul du factorielle d’un entier n et exp(x,n) pour la puissance d’un nombre réel x élevé à un entier positif n.
Fonction fact(n : entier) : entier;
Début
si (n = 0) alors
retourner 1;
sinon
retourner n * fact(n - 1);
fsi
Fin;
Fonction exp(x : réel, n : entier) : réel;
Début
si (n = 0) alors
retourner 1;
sinon
retourner x * exp(x, n - 1);
fsi
Fin;
2) Proposer une fonction : sin(x,n) via le développement limité de : sin(x)=x-x^3/3!+x^5/5!-x^7/7!+⋯+((-1)^n ) x^(2n+1)/((2n+1)! ) Et la question (1).
Fonction sin(x : réel, n : entier) : réel;
var i : entier;
somme, terme : réel;
Début
somme <- 0;
pour i de 0 à n faire
terme <- ((-1)^i) * (exp(x, 2*i+1) / fact(2*i+1));
somme <- somme + terme;
fpour
retourner somme;
Fin;
Exercice 03 : Tableau, Enregistrement et Fichier /pts
Les étudiants d’info 1 souhaitent manipuler en mémoire centrale de l’ordinateur de l’hôpital du district de Dschang un ensemble de Médicament (400 Médicaments). Les informations concernant un Médicament sont : le code (entier), nom (chaine), libellé(chaine), prix(réel), quantité(réel), la date de Fabrication (Date) et la notation du Médicament (Bien (VRAI) et Mal (FAUX)). (Nb : le choix de l’utilisation des fonctions ou procédures, type de retour, paramètre formel dépendra de votre capacité à analyser le sujet !)
1) Proposer une structure de donnée adéquate permettant de représenter un Médicament.
Type Medicament = Enregistrement
code : entier;
nom : chaine;
libelle : chaine;
prix : réel;
quantité : réel;
dateFabrication : Date;
notation : Booléen;
Fin;
2) Proposer une structure de donnée adéquate permettant de manipuler ces Médicaments donnés en mémoire.
Type TableauMedicaments = Tableau[1..400] de Medicament;
3) Proposer une fonction/procédure (rechercherMedoc) permettant de rechercher un Médicament par son code dans l’ensemble et retourner sa position.
Fonction rechercherMedoc(t : TableauMedicaments, codeRecherche : entier) : entier;
var i : entier;
Début
pour i de 1 à 400 faire
si t[i].code = codeRecherche alors
retourner i;
fsi
fpour
retourner -1; // Si non trouvé
Fin;
4) Donner la différence entre un fichier et un tableau du point de vue informatique.
Un tableau est une structure de données qui stocke des éléments de même type en mémoire centrale, permettant un accès direct et rapide à chaque élément via un indice. Un fichier, en revanche, est une collection de données stockées sur un support de stockage externe (comme un disque dur), qui peut contenir des données de différents types et nécessite des opérations d'entrée/sortie pour accéder aux données.
Etudes de Cas : /8pts (1+0.5+0.5+0.5+1+0,5+0,5+0,5+1+0,5+1+0,5)
L’idée de cet exercice n’est pas de vous faire Trier toute les étoiles présentes dans la Galaxie rassurez-vous, mais de juger vos compétences en Algorithmique nous allons aider Adam étudiant du niveau 1 informatique à répondre aux questions lors d’un entretien dans une entreprise de la ville de Dschang.
Correction Étude de Cas : Algorithme TriGalaxie
1. Démontrer ou réfuter que l’algorithme TriGalaxie trie correctement
Tableau donné : V = {28, 56, 2, 7, -7, 14, 507}
L’instant Genius ? :
L'algorithme TriGalaxie utilise une procédure Etoile pour trier les éléments pairs et impairs séparément. Après deux appels à Etoile (un pour les indices pairs et un pour les indices impairs), il effectue un tri complet du tableau.
Exécution :
1. Premier appel à Etoile(t, VRAI) :
- Trie les éléments aux indices pairs.
- Pour V = {28, 56, 2, 7, -7, 14, 507}, les indices pairs sont 2, 4, 6.
- Les éléments correspondants sont 56, 7, 14.
- Après tri, V = {28, 7, 2, 14, -7, 56, 507}.
2. Deuxième appel à Etoile(t, FAUX) :
- Trie les éléments aux indices impairs.
- Les indices impairs sont 1, 3, 5, 7.
- Les éléments correspondants sont 28, 2, -7, 507.
- Après tri, V = {-7, 7, 2, 14, 28, 56, 507}.
3. Tri final (nébuleuse) :
- Trie l'ensemble du tableau.
- Résultat final : V = {-7, 2, 7, 14, 28, 56, 507}.
Conclusion :
L'algorithme trie correctement le tableau.
2. Connaissez-vous d’autres algorithmes de tri ?
Réponse : Oui, il existe plusieurs algorithmes de tri. En voici deux (je donne d’autres exemples de réponse car il peut avoir des étudiants du niveau 2 ) :
- Pour étudiant du Niveau 1 : Tri Sélection, Tri Bulle, Tri Insertion
- Pour étudiant Niveau 2 : Tri Fusion, Tri Rapide
3. Etoile est une fonction ou une procédure ?
Réponse : Etoile est une procédure, car elle ne retourne aucune valeur. Elle ne modifie pas directement le tableau passé en paramètre.
4. Type de passage utilisé pour Etoile
Réponse : Le passage est par référence/ variable/ adresse (indiqué par var dans la déclaration de t). Cela signifie que les modifications apportées à t dans Etoile affectent le tableau original.
5. Rôle de la condition : (i DIV 2) * 2 = i ET (j DIV 2) * 2 = j
Réponse : Cette condition vérifie si les indices i et j du tableau sont pairs.
6. Signification du premier appel : Etoile(t, VRAI)
Réponse : Le premier appel à Etoile(t, VRAI) trie les éléments du tableau aux indices pairs.
7. Signification du deuxième appel : Etoile(t, FAUX)
Réponse : Le deuxième appel à Etoile(t, FAUX) trie les éléments du tableau aux indices impairs.
8. Rôle des deux boucles POUR après Écrire(" Une Nébuleuse ")
Réponse : Ces boucles effectuent un tri complet du tableau en comparant et en échangeant tous les éléments pour s'assurer que le tableau est entièrement trié.
9. Peut-on remplacer les boucles POUR par une boucle TANTQUE ?
Réponse : Oui, on peut remplacer les boucles POUR par des boucles TANTQUE. Voici la version modifiée :
Procédure Etoile(var t: tableau [1..N] de Entier, sky : Booléen);
Var val, i, j: Entier;
Début
i <- 1;
TantQue (i <= N - 1) Faire
j <- i + 1;
TantQue (j <= N) Faire
Si (sky=VRAI ET (i DIV 2) * 2 = i ET (j DIV 2) * 2 = j) OU
(NON (sky) ET (i DIV 2) * 2 <> i ET (j DIV 2) * 2 <> j) Alors
Si t[i] > t[j] Alors
val <- t[i];
t[i] <- t[j];
t[j] <- val;
Fin Si
Fin Si
j <- j + 1;
Fin TantQue
i <- i + 1;
Fin TantQue
Fin;
10. Autre façon d’écrire le test : NON (sky)
Réponse : Le test NON (sky) peut être écrit comme : sky = FAUX.
11. Différence entre une boucle POUR et une boucle TANTQUE
Réponse :
- Boucle POUR : Le nombre d'itérations est connu à l'avance. La variable de contrôle est automatiquement incrémentée/décrémentée.
- Boucle TANTQUE : Le nombre d'itérations n'est pas connu à l'avance. La condition est vérifiée avant chaque itération.
12. Fonction supplémentaire pour réduire les instructions
Réponse : On peut créer une fonction Echanger pour éviter de répéter le code d'échange des éléments :
Procédure Echanger(var a : Entier, var b : Entier);
Var temp : Entier;
Début
temp <- a;
a <- b;
b <- temp;
Fin;
Utilisation :
val <- t[i];
t[i] <- t[j];
t[j] <- val;
Echanger(t[i], t[j]);
