ÉVALUATION EN ALGORITHMIQUE TEST  19 / XX  

Examen Corriges en Algorithme

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

1. Exécution d’un PseudoCode :

Ecrire("Donner un entier composé de 3 chiffres :") ; 

lire(n) ;

c ← n div 100 ;

d ← (n mod 100) div 10 ;

u ← n mod 10 ;

s ← u+d+c ;

si (s>=10) alors

    d2 ← s div 10 ;

    u2 ← s mod 10 ;

    s2 ← u2+d2 ;

    si (s2>=10) alors

       d3 ←s2 div 10 ;

       u3 ←s2 mod 10 ;

       s3 ← u3+d3 ;

       Ecrire("S3=",s3);

    sinon

       Ecrire("S2=",s2) ;              

sinon

Ecrire(" s= ", s) ;

2.  Question de Cours :

1. Donner la différence entre un paramètre effectif et un paramètre formel.1pts 
2. Donner la différence entre le passage par valeur et le passage par adresse avec exemple a l’appui.1pts
3. Donner un algorithme du Calcule du PGCD de 02 nombres.1pts

Exercice 02 : Matrice de Toeplitz 5pts

En algèbre une matrice Toeplitz n×m , T est notée T=[tij]=[ti-j], pour 1≤i,j≤n ; ce qui implique que toutes les entrées le long de chacune des 2n-1 diagonales sont les mêmes. Toute matrice N × N mat est une matrice Toeplitz si T(i, j) = T(i+1, j+1) = T(i+2, j+2), et ainsi de suite... Ici, T(i, j) désigne l'élément T[i][j] dans la matrice. Une matrice Toeplitz (ou diagonale-constante) est une matrice dans laquelle chaque diagonale descendante de gauche à droite est constante, c'est-à-dire que tous les éléments d'une diagonale sont identiques. Pour eux l’idée est simple : parcourir la matrice une fois, et pour chaque élément (i, j), vérifier s'il est identique à son élément diagonal immédiat (i+1, j+1) ou non. Si un élément diffère de son élément diagonal immédiat, la matrice ne peut pas être Toeplitz. Une matrice de Toeplitz est une matrice dont les composantes des diagonales sont constantes. Il suffit donc pour connaitre une matrice de Toeplitz [n, m] de connaitre la première ligne (qui va donner les diagonales de 0 a n et la première colonne qui va donner les diagonales de 0 a n). Exemple :

m

n

9

5

1

0

4

9

5

1

7

4

9

5

2

7

4

9

T est Toeplitz :

 Questions :

1. Démontrer que l’addition de 02 matrices de Toeplitz donne une matrice Toeplitz.
2. Démontrer que la multiplication de 02 matrices de Toeplitz ne donne pas une matrice Toeplitz.
3. Démontrer que la multiplication d’une matrice de Toeplitz et d’un vecteur donne une matrice Toeplitz.
4. Ecrire une fonction permettant de vérifier si tous les éléments présents dans la diagonale descendante à partir de la position (i, j) dans la matrice sont tous identiques ou non.
5. Ecrire une fonction permettant de vérifier si une matrice donnée est une matrice Toeplitz ou non.

Probleme : 9pts

Un Groupe d'etudiant désire mettre sur pieds un programme informatique tout en un pour dissimuler des nombres décimaux dans une matrice N * N , dans le but que seul ceux du Groupe Genius pourront savoir exactement comment déchiffrer cette Matrice et trouver les nombres en questions Le Principe est simple : Remplir une Matrice nommée Secret de taille 4*4 par des entiers Binaires ( 0 ou 1 uniquement ).Chaque ligne de Secret représente la conversion Binaire d’un entier Nommée nbreB de la base 10. Ne se limitant juste pas au principe nous allons effectuer des opérations que nous allons par la suite stocker dans un Cd-Room.

1. Proposer un enregistrement permettant de représenter un Binaire Secret, qui est caractérisé par un champs secret qui est une matrice n*n, d’un champs Flag (indicateur de correspondance un booléen, son rôle seras évoqué plus bas).
2. Proposer une fonction déchiffrée qui prends en paramètre un BinaireSecret, stocke la valeur (décimale) de chaque ligne de secret dans un vecteur de taille n nommée top. (Tenir en compte que le bit de poids le plus fort ce trouve en Position secret[i,1]).
3. Proposer une fonction vérifier qui prends en paramètre un BinaireSecret et un Tableau de décimal (top). Puis tester si pour chaque valeur nbreB de la ligne de secret correspond bien à celle retrouve dans notre tableau, dans le cas d’une correspondance parfaite (ie correspondance totale entre secret et top) mettre la variable Flag à vrai sinon faux.
4. Proposer une fonction Trie_décimal qui prends en paramètre un vecteur de taille n nommée top et trie les éléments par ordre décroissant.
5.  Proposer une fonction Affiche_décimal qui prends en paramètre un vecteur de taille n nommée top et affiche les éléments sous la forme : [89,77,9,0,5].
6. Ecrire un Algorithme qui demande à un utilisateur lambda d’entrer des valeurs entières (0 ou 1 seulement), puis déterminer tout d’abord la correspondance Décimale de ses valeurs entrées pour chaque ligne de sa matrice, puis vérifier cette correspondance, trier par ordre décroissant les nombres décimaux résultants enfin afficher selon un format adéquat ses nombres.
7. Proposer une structure de donnée pour stocker ses informations sur un CD-ROOM, schéma à l’appui.

Exercice 01 :

Correction Partie A :

Dans l’algorithme 01 on dénote l’absence de déclaration de variable et de points virgule dans l’instruction si (ligne 9,10,12,13).

Alors cet algorithme permet de saisir un temps (heure et minute) lui ajoute 5 minutes puis l'affiche.

Exemples :heure : 10 minute : 20 après 5 minutes : 10:25
heure : 10 minute:57 après 5 minutes : 11: 02
heure : 23 minute:55 après 5 minutes : 00:00

Dans l’algorithme 02 on dénote l’absence de déclaration de variable et du Debut. Alors cet algorithme permet de saisir un entier de 3 chiffres puis affiche la somme S de ces 3 chiffres. Puis si S est composé de 2 chiffres alors faire leurs somme S2 enfin si S2 est composé de 2 chiffres alors faire leurs somme S3.

Exemple : pour 946  S=9+4+6=19   S2=1+9=10   S3=1+0=1

Correction : Partie B

Les paramètres formels sont la définition du nombre et du type de valeurs que devra recevoir le sous-algorithme pour se mettre en route avec succès. On déclare les paramètres formels pendant la déclaration du sous-algorithme. Hors Les paramètres effectifs sont des valeurs réelles (constantes ou variables) reçues par le sous-algorithme au cours de l’exécution du bloc principal. On les définit indépendamment à chaque appel du sous-algorithme dans l’algorithme principal.

Passage paramètres par valeur C’est le mode de transmission par défaut, il y a copie de la valeur, des paramètres effectifs dans les variables locales issues des paramètres formels de la procédure ou de la fonction appelée. Dans ce mode, le contenu des paramètres effectifs ne peut pas être modifié par les instructions de la fonction ou de la procédure ; car nous ne travaillons pas directement avec la variable, mais sur une copie. À la fin de l’exécution du sous-algorithme la variable conservera sa valeur initiale. Les paramètres dans ce cas sont utilisés comme données. Hors Passage paramètres par variable Ici, il s’agit non plus d’utiliser simplement la valeur de la variable, mais également son emplacement dans la mémoire (d’où l’expression « par adresse »). En fait, le paramètre formel se substitue au paramètre effectif durant le temps d’exécution du sous-programme et à la sortie il lui transmet sa nouvelle valeur. Un tel passage de paramètre se fait par l’utilisation du mot-clé Var.

Algorithme de PGCD

Algorithme PGCD ;

var : A,B,MyPGCD : entier ;

Debut

Ecrire ( ' Entrer La valeur d'un nombre  ' );

Lire ( A );

Ecricre ( ' Entrer La valeur d'un second nombre   ' );

Lire ( B);

tantque (  A < > B ) faire

si (  A <  B ) alors

B := B - A

sinon

 A := A - B ;

finsi

fintantque

MyPGCD := A;

Ecricre ( ' Le PGCD de  ', A , ' et ', B , ' est :  '  MyPGCD );

Fin.

Exercice 02 :

Probleme : 9pts

Proposer un enregistrement permettant de représenter un Binaire Secret, qui est caractérisé par un champs secret qui est une matrice n*n, d’un champs Flag (indicateur de correspondance un booléen, son rôle seras évoqué plus bas).

Proposer une fonction déchiffrée qui prends en paramètre un BinaireSecret, stocke la valeur (décimale) de chaque ligne de secret dans un vecteur de taille n nommée top. (Tenir en compte que le bit de poids le plus fort ce trouve en Position secret[i,1]).

Proposer une fonction vérifier qui prends en paramètre un BinaireSecret et un Tableau de décimal (top). Puis tester si pour chaque valeur nbreB de la ligne de secret correspond bien à celle retrouve dans notre tableau, dans le cas d’une correspondance parfaite (ie correspondance totale entre secret et top) mettre la variable Flag à vrai sinon faux.

Proposer une fonction Trie_décimal qui prends en paramètre un vecteur de taille n nommée top et trie les éléments par ordre décroissant.

Proposer une fonction Affiche_décimal qui prends en paramètre un vecteur de taille n nommée top et affiche les éléments sous la forme : [89,77,9,0,5].

Ecrire un Algorithme qui demande à un utilisateur lambda d’entrer des valeurs entières (0 ou 1 seulement), puis déterminer tout d’abord la correspondance Décimale de ses valeurs entrées pour chaque ligne de sa matrice, puis vérifier cette correspondance, trier par ordre décroissant les nombres décimaux résultants enfin afficher selon un format adéquat ses nombres.

Proposer une structure de donnée pour stocker ses informations sur un CD-ROOM, schéma à l’appui.