EVALUATION EN ALGORITHMIQUE TEST 13 / XX

Exercice 01 : Généralités 5pts

Exécution d’un PseudoCode :

ALGORITHME 01

ALGORITHME 02

fonction F1 ( n : entier , a : entier ): entier;

Début

si(n=0)alors

F1 <- a ;

sinon

F1 <- F1(n-1,n*a);

fsi

Fin;

Questions :

Dénichez les potentielles erreurs dans cet algorithme. 0.5pts
Pour a=2 et n = 4 , dire ce que réalise cet algorithme. 1pts

fonction F2 (x : flottant, n : entier) : flottant
res : flottant ;
debut
si (n == 0) alors
res = 1;
sinon
res = F2(x, n DIV 2)
si ( n MOD 2 == 0) alors // n est pair
res = res * res
sinon // n est impair
res = res * res * x
fin si
fin si
F2 <- res ;
fin;

Questions :

Dénichez les potentielles erreurs dans cet algorithme. 0.5pts
Pour n =4 et x=8 dire ce que réalise cet algorithme. 1pts

Donner le type et le résultat des expressions suivantes, ou dire si elles ne sont pas bien formées.

12 / 3
12 div 3
11 div 3 div 2
1.0 * 2 + 3 - 4 (50 < 3 * 8) faux ou non faux et vrai
(12 > 24) + (2 + 4 = 12) 12 > 3 > 4
3.5 + 7 > 4 > faux non (12 < > 3 * 16.8 / 4) et vraie

EXERCICE 02 : 5pts

Algorithme RechercheOriginale ;

Fonction : recherche(tab, valeur)
Action : recherche la valeur « valeur » dans le tableau « tab »
Début
i ⟵ 0
i_val ⟵ -1
nb ⟵ Longueur(tab)
TantQue i < nb Faire
Si tab[i] = valeur Alors
i_val ⟵ i
FinSi
i ⟵ i + 1
FinTantQue
Renvoyer i_val
Fin

Décrire le fonctionnement de l’algorithme pour les valeurs tab = [1, 8, 3, 54, 95] et val = 3.
Cet algorithme ressemble a quel algorthime de trie classique ?
Démontrer que l’algorithme se termine.
Démontrer que l’algorithme est correct.
Peut-on executer cet algorithme sur un tableau qui n'est pas trie?

Problème : La Librairie Genius 10pts

Les étudiants du GROUPE toujours très curieux désirent pour un expose en algorithmique et Langage C , manipuler en mémoire centrale d’un ordinateur en ensemble de Livre . Les informations concernant un Livre sont : le code, nom, l’auteur, description, prix, quantité et la notation du livre ( de 0 à 5 ) .

Proposer une structure de donnée adéquate permettant de manipuler ces données en mémoire. (en Algo et en C )
Proposer une fonction permettant de rechercher un Livre par son code dans l’ensemble. (en Algo et en C )
Proposer une fonction permettant d’insérez un Livre dans l’ensemble des Livres. (en Algo )
Proposer une fonction permettant compter tous les Livres dont le nom est : GENIUS dans l’ensemble des Livres. (en Algo et C )
Proposer une fonction permettant classer tous les Livres par ordre croissant dans l’ensemble des produits (utiliser le trie insertion) ceci par la notation. (en Algo )
Proposer une fonction permettant de supprimer tous les Livres dont le code est pris en paramètre de la Fonction dans l’ensemble des Livres. (en Algo )
Proposer une fonction permettant de modifier le prix d’un Livre dans l’ensemble des Livres. (en Algo )
Proposer une fonction permettant d’afficher tous les produits les plus vendues dans l’ensemble des Livres. (Nb : un Livre qui a eu du succès auprès des étudiants est un Livre qui a reçu une notation supérieure à 2.5, on s’attarderas pas sur la gestion de la notation mais plutôt sur sa valeur brute.) (en Algo et C )
Proposer une fonction permettant de sauvegarder de façon permanente les données relatives à l’ensemble des Livres. (en Algo )
Donnez la différence entre un Tableau et un Fichier en Algo.

Par Joel_Yk | Contact :+237652027193

Correction :

EVALUATION EN ALGORITHMIQUE TEST 13 / XX

Exercice 01 : Generalites (5 pts)

A) Execution d’un PseudoCode

ALGORITHME 01 : Fonction F1

a) Potentielles erreurs (0.5 pt)

Erreur d’appel recursif : dans le code, on ecrit F1 <- F1(n-1, n*a) mais on a mis F1(n-1,n*a) comme si F1 etait une procedure. Il faut bien utiliser Retourner ou affecter le resultat correctement.
Risque de non-termination si n < 0 : si n est negatif, on ne va jamais atteindre n = 0. Il faut imposer la precondition n >= 0.
Ambiguite sur le calcul : le parametre a est modifie par n*a, cela fait grandir tres vite la valeur, risque de depassement (overflow).
Notation : on melange style “F1 <- ...” et “appel fonction” ; en pseudo-code propre on ecrit plutot Retourner.

Version corrigee (pseudo-code soft)

Fonction F1(n : entier, a : entier) : entier
Debut
  Si (n = 0) Alors
    Retourner a
  Sinon
    Retourner F1(n - 1, n * a)
  FinSi
Fin

b) Pour a = 2 et n = 4, que realise F1 ? (1 pt)

On calcule :

F1(4,2) = F1(3, 4*2) = F1(3,8)
F1(3,8) = F1(2, 3*8) = F1(2,24)
F1(2,24) = F1(1, 2*24) = F1(1,48)
F1(1,48) = F1(0, 1*48) = F1(0,48)
F1(0,48) = 48

Donc F1(4,2) = 48.

Interpretation : la fonction multiplie progressivement par n, puis (n-1), ... jusqu’a 1. Elle calcule donc :

F1(n, a) = a * n! (si n >= 0).

ALGORITHME 02 : Fonction F2

a) Potentielles erreurs (0.5 pt)

Melange de syntaxes : utilisation de ==, =, et <- dans un meme pseudo-code. Il faut une syntaxe unique.
Manque de “Retourner” : on affecte F2 <- res a la fin, mais on peut faire un Retourner res directement.
Precondition : l’exposant n doit etre entier et en general n >= 0. Si n est negatif, l’algo ne correspond pas a la puissance entiere classique.

Version corrigee (pseudo-code soft)

Fonction F2(x : reel, n : entier) : reel
Var r : reel
Debut
  Si (n = 0) Alors
    Retourner 1
  Sinon
    r <- F2(x, n DIV 2)
    Si (n MOD 2 = 0) Alors
      Retourner r * r
    Sinon
      Retourner r * r * x
    FinSi
  FinSi
Fin

b) Pour n = 4 et x = 8, que realise F2 ? (1 pt)

Cette fonction calcule x^n par exponentiation rapide (diviser n par 2, puis carre).

F2(8,4) : n pair, donc = F2(8,2)^2
F2(8,2) : n pair, donc = F2(8,1)^2
F2(8,1) : n impair, donc = F2(8,0)^2 * 8 = 1^2 * 8 = 8
F2(8,2) = 8^2 = 64
F2(8,4) = 64^2 = 4096

Donc F2(8,4) = 4096 = 8^4.

B) Types et resultats d’expressions

12 / 3 : type reel, resultat = 4.0
12 div 3 : type entier, resultat = 4
11 div 3 div 2 : type entier, evaluation gauche->droite : (11 div 3) = 3 puis (3 div 2) = 1, resultat = 1
1.0 * 2 + 3 - 4 (50 < 3 * 8) faux ou non faux et vrai :
- Expression 4(50 < 24) n’est pas bien formee : il manque un operateur entre 4 et (...)
- Ensuite on melange arithmetique et booleens sans parenthesage clair.
- Conclusion : expression non bien formee.
(12 > 24) + (2 + 4 = 12) 12 > 3 > 4 :
- (12 > 24) est booleen, on ne peut pas l’additionner directement.
- 12 > 3 > 4 est en general non bien forme en pseudo-code (il faut ecrire (12 > 3) ET (3 > 4)).
- Conclusion : non bien formee.
3.5 + 7 > 4 > faux non (12 < > 3 * 16.8 / 4) et vraie :
- Melange de comparaisons chainees et de booleens non structure.
- <> oui existe, mais le reste est confus (non, vraie, faux sans parenthesage).
- Conclusion : non bien formee.

EXERCICE 02 : Recherche (5 pts)

Algorithme RechercheOriginale

Rappel : cet algorithme parcourt le tableau et memorise la position chaque fois qu’il trouve la valeur. Donc il renvoie la derniere occurrence.

1) Execution pour tab = [1, 8, 3, 54, 95] et val = 3

i=0 : tab[0]=1 ≠ 3, i_val=-1
i=1 : tab[1]=8 ≠ 3, i_val=-1
i=2 : tab[2]=3 = 3, i_val=2
i=3 : tab[3]=54 ≠ 3, i_val=2
i=4 : tab[4]=95 ≠ 3, i_val=2

Retour : i_val = 2

2) Cet algorithme ressemble a quel algorithme de tri classique ?

Aucun tri. Il ressemble plutot a une recherche sequentielle (lineaire), pas a un tri.

3) Demontrer que l’algorithme se termine

La variable i commence a 0.
A chaque iteration : i <- i + 1 (i augmente strictement).
La boucle s’arrete quand i = nb (nb est fini).

Donc l’algorithme termine toujours.

4) Demontrer que l’algorithme est correct

Invariant : a tout instant, i_val contient l’indice de la derniere occurrence de “valeur” parmi tab[0..i-1], ou -1 si aucune occurrence n’a ete vue.
Quand tab[i] = valeur, on met i_val <- i, donc i_val devient la derniere occurrence vue jusque-la.
Quand la boucle finit (i = nb), on a examine toutes les cases, donc i_val est la derniere occurrence dans tout le tableau, ou -1 si absente.

5) Peut-on executer cet algorithme sur un tableau non trie ?

Oui. C’est une recherche sequentielle, elle ne depend pas du tri du tableau.

Par Joel_Yk | Contact : +237652027193

Problème : La Librairie Genius 10pts

Proposer une structure de donnée adéquate permettant de manipuler ces données en mémoire. (en Algo et en C ) .

CORRECTION : (En algo)

Const N=100 ;

Type livre= enregistrement

code : chaine de caractère ;

nom : chaine de caractère ;

auteur :chaine de caractere ;

descript : chaine de caractère ;

prix : réel ;

quantité : réel ;

notation : réel ;

Fin ;

tabliv= tableau[1…N] de livre ;

Proposer une fonction permettant de rechercher un Livre par son code dans l’ensemble. (en Algo et en C )

CORRECTION : (en algo)

Fonction rechercheliv(t :tabliv , code :chaine de caractère) : entier ;

Var i :entier ;

Debut

iß1 ;

tantque( i<=N et t[i].code<>code)faire

ißi+1 ;

fintantque

si(i=N+1) alors

recherchelivß-1 ;

sinon

recherchelivß i ;

finsi

fin ;

Proposer une fonction permettant d’insérez un Livre dans l’ensemble des Livres. (en Algo )

CORRECTION :

Procedure insertliv(var t :tabliv, L :livre) ;

Var i, case : entier ;

Debut

Si(rechercheliv(t , livcode)=-1) alors

iß1 ; caseß0 ;

tantque(i<=N et case=0) faire

si(t[i].code= ’’ ’’) alors

t[i].codeßL.code ;

t[i].nomßL.nom ;

t[i].auteurßL.auteur ;

t[i].descriptß L.descript ;

t[i].prixßL.prix ;

t[i].quantiteßL.quantite ;

t[i].notationßL.notation ;

caseßcase+1 ;

finsi

ißi+1 ;

fintantque

si(case=0) alors

ecrire(’’insertion impossible car le tableau est plein’’) ;

sinon

ecrire(’’insertion reussie’’) ;

finsi

sinon

ecrire(’’l’element existe déjà dans le tableau’’) ;

finsi

fin ;

Proposer une fonction permettant compter tous les Livres dont le nom est : GENIUS dans l’ensemble des Livres. (en Algo et C )

CORRECTION : (en algo)

Fonction compteliv(t :tabliv) :entier ;

Var i, cpt :entier ;

Debut

Cptß0 ;

Pour i de 1 à N faire

Si(t[i].nom= ‘’Genuis’’) alors

CptßCpt+1 ;

Finsi

Finpour

Comptelivßctp ;

Fin ;

Proposer une fonction permettant classer tous les Livres par ordre croissant dans l’ensemble des produits (utiliser le trie insertion) ceci par la notation. (en Algo )

CORRECTION :

Procedure trinotation(var t :tabliv) ;

Var cle :livre ; i,j :entier ;

Debut

Pour i de 2 à N faire

cle.notationßt[i].notation ;

cle.codeßt[i].code ;

cle.nomßt[i].nom ;

cle.auteurßt[i].auteur ;

cle.descriptßt[i].descript ;

cle.prixßt[i].prix ;

cle.quantiteßt[i].quantite ;

jßi-1 ;

tantque(cle.notation<t[j].notation et j>0)faire

t[j+1].codeßt[j].code ;

t[j+1].nomßt[j].nom ;

t[j+1].auteurßt[j].auteur ;

t[j+1].descriptßt[j].descript ;

t[j+1].prixßt[j].prix ;

t[j+1].quantiteßt[j].quantite ;

t[j+1].notationßt[j].notation ;

tßj-1 ;

fin tantque

t[j+1].notationßcle.notation ;

t[j+1].codeßcle.code ;

t[j+1].nomßcle.nom ;

t[j+1].auteurßcle.auteur ;

t[j+1].descriptßcle.descipt ;

t[j+1].prixßcle.prix ;

t[j+1].quantiteßcle.quantite ;

finpour

pour i de 1 à N faire

ecrire(t[i].code) ;

ecrire(t[i].nom) ;

ecrire(t[i].auteur) ;

ecrire(t[i].descript) ;

ecrire(t[i].prix) ;

ecrire(t[i].quantite) ;

ecrire(t[i].notation) ;

finpour

fin ;

Proposer une fonction permettant de supprimer tous les Livres dont le code est pris en paramètre de la Fonction dans l’ensemble des Livres. (en Algo )

CORRECTION :

Procedure supliv(var t :tabliv , code : chaine de caractere) ;

Var i :entier ;

Debut

ißrechercheliv(t,code) ;

si(i<>-1) alors

t[i].codeß’’ ‘’ ;

t[i].nomß’’ ‘’ ;

t[i].auteurß’’ ‘’ ;

t[i].descriptß’’ ‘’ ;

t[i].prixßNIL ;

t[i].quantiteßNIL ;

t[i].notationßNIL ;

sinon

ecrire(‘’l’element n’existe pas’’) ;

finsi

fin ;

Proposer une fonction permettant de modifier le prix d’un Livre dans l’ensemble des Livres. (en Algo )

CORRECTION :

Procedure modifprix(var t :tabliv , l :libre ) ;

Var i :entier ;

Debut

Ißrechercheliv(t , l.code) ;

Si(i<>-1)alors

t[i].prixßl.prix

sinon

ecrire(‘’le livre n’existe pas’’) ;

finsi

fin ;

Proposer une fonction permettant d’afficher tous les produits les plus vendues dans l’ensemble des Livres. (Nb : un Livre qui a eu du succès auprès des étudiants est un Livre qui a reçu une notation supérieure à 2.5, on s’attarderas pas sur la gestion de la notation mais plutôt sur sa valeur brute.) (en Algo et C )

CORRECTION :

Procedure affichlivre(t :tabliv ) ;

Var i :entier ;

Debut

Pour i de 1 à N faire

Si (t[i].notation>2,5)alors

Ecrire(t[i].code) ;

Ecrire(t[i].nom) ;

Ecrire(t[i].auteur) ;

Ecrire(t[i].descript) ;

Ecrire(t[i].prix) ;

Ecrire(t[i].quantite) ;

Ecrire(t[i].notation ) ;

Finsi

Finpour

Fin ;

Proposer une fonction permettant de sauvegarder de façon permanente les données relatives à l’ensemble des Livres. (en Algo )

CORRECTION :

Type fichliv=fichier de livre ;

Procedure sauvegarde(f :fivhliv , t :tabliv)

Var i :entier ;

Debut

Ouvrire(f) ;

iß1 ;

Tantque( non(fin(f)) et i<=N)faire

ecrire(f,t[i]) ;

ißi+1 ;

fintantque

fermer(f) ;

ecrire(‘’sauvegarde terminer’’) ;

fin ;

Donnez la différence entre un Tableau et un Fichier en Algo.

CORRECTION :

La différence entre un tableau et un fichier est que dans un tableau les traitements se font dans la mémoire vive (la RAM) par conséquent les informations ne sont pas définitives or dans un fichier les traitements de font dans une mémoire morte (ROM, disquette…) donc les informations sont enregistrer de façon définitives ;

GROUPE GENIUS REPETITION Contact : +237 652027193

Coordonnateur : Mr Joël_yankam ngueguim