ÉVALUATION EN ALGORITHMIQUE TEST 21 / XX

Examen Corriges en Algorithme

Exercice 1: Définitions 0,5x6-3 pts

1) Définir: algorithme, programme

2) Quelle est la différence entre une fonction et une procédure?

3). Quelle est la différence entre variables globales et variables locales ? 4) Quelle est la différence entre paramètres formels et paramètres effectifs ?

5) Quelle est la différence entre le passage par valeur, le passage par adresse et le passage par référence?

Exercice 2: 3 pts

La méthode de Newton Raphson pour calculer la racine carrée d'un reel positif c est définie par l'itération: X=(Xk+C/Xk)/2, k=0,1,2, où l'estimation initiale xo est supposée donnée. On s'arrête lorsque Xk+1 -Xk <= prec. Pour une précision donnée prec. Ecrire un algorithme pour calculer et imprimer (afficher) la racine carrée d'un réel C par la méthode de Newton Raphson. Votre Algorithme devrait lire en entrée C. la précision Prec et l'estimation initiale x0. Il devrait aussi calculer et imprimer le nombre d'itérations utilisées pour obtenir la précision prec fixée.

Exercice 3: (5-1,5+1,5+2) pts

On souhaite écrire un algorithme qui prend une liste d'entiers en entrée et qui calcule la moyenne et la médiane de cette liste.

1) Ecrire une fonction qui prend en entrée une liste d'entiers et qui retourne la moyenne de ces entiers.

2) Ecrire une fonction qui prend en entrée une liste d'entiers et qui retourne la médiane de ces entiers. La médiane est définie comme la valeur se trouvant au milieu de la liste triée. Si la liste contient un nombre pair d'éléments, la médiane est la moyenne des deux valeurs du milieu.

3)Utiliser les fonctions que vous avez implémentées dans les volets précédents pour résoudre le problème suivant: vous recevez une liste d'entiers en entrée, et vous devez retotirner la différence entre la moyenne et la médiane de cette liste.

Problème: Algorithmes et problèmes de tri (9-1+2+2+2+2) pts

Partie A: Soit une liste de n éléments, une clé est associée à chaque élément et dont la valeur appartient à un ensemble totalement ordonné. Le résultat est une liste dont les éléments sont une permutation des éléments de la liste d'origine telles que les valeurs des clés sont croissantes quand on parcourt la lise séquentiellement. 1) Donner le principe et l'algorithme du tri bulles. 2) Appliquer cet algorithme au tableau suivant et donner le tableau trié (Faites ressortir toutes les étapes jusqu'à l'obtention du tableau trié) (101, 115, 30, 64, 47, 50,20)

Partie B: Si un vecteur est trie, l'algorithme de recherche par dichotomie est recommandé pour rechercher un élément dans le vecteur. On suppose que le vecteur est trié par ordre croissant; que lower et upper désignent les bornes inférieures et supérieures des indices du vecteur vect, et que key contienne la valeur à rechercher. Après avoir exécuté les instructions suivantes:

milieu (lowertupper) div 2; if key> vect[milieu] then lower milieur+1 else upper milieu-1;

Soit vect[milieu] key et on a trouvé l'élément recherché, soit on poursuit la recherche, mais dans l'une des moitiés du vecteur.

Ecrire deux procédures, une récursive et une itérative pour rechercher un élément key dans un vecteur vect contenant des réels. Chacune devant renvoyer true dans une variable booléenne found et l'indice de key dans vect si key est trouvé; sinon false.

Correction :

Exercice 01 : 03,5 pts - Questions de Cours

Définition : Algorithme est une suite finie et ordonnée d'instructions permettant de résoudre un problème précis. Programme est une séquence d'instructions écrites dans un langage de programmation spécifique, conçue pour être exécutée par un ordinateur afin d'accomplir un objectif particulier.
Différence : Une fonction est un bloc d'instructions qui retourne une seule valeur résultat à l'algorithme appelant, sans afficher la réponse. Une procédure est un bloc d'instructions nommé et déclaré dans l'entête de l'algorithme, appelé dans son corps à chaque besoin. En résumé, une fonction est un sous-algorithme qui, à partir de données, calcule et rend à l'algorithme un seul résultat, tandis qu'une procédure affiche généralement le(s) résultat(s) demandé(s).
Différence : Un sous-algorithme utilise les variables déclarées dans l'algorithme (appelées variables globales, connues dans tout l'algorithme). Il peut aussi avoir ses propres variables (les variables locales) déclarées dans l'espace qui lui est réservé. Cependant, elles ne peuvent être utilisées que dans ce sous-algorithme et nulle part ailleurs, car leur portée (visibilité) est limitée au bloc qui les contient. L'espace de ces variables locales n'est réservé que lorsque le sous-algorithme est appelé et est libéré dès la fin de l'exécution.
Différence : Les paramètres formels définissent le nombre et le type de valeurs que doit 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. 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.
Différence : Passage paramètres par valeur : Mode de transmission par défaut, avec 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. Le contenu des paramètres effectifs ne peut pas être modifié par les instructions de la fonction ou de la procédure, car on travaille 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. Passage paramètres par variable – référence-Adresse : Utilisation non seulement de la valeur de la variable, mais aussi de son emplacement dans la mémoire (par adresse). 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.

Exercice 02 : 03 pts Newton Raphson

            
            Algorithme NewtonRaphson;
            Var c, prec, x0, xn, pas : reel;
                k : entier;

            Debut
              Ecrire('Entrer votre réel :');
              lire(c);
              Ecrire('Entrer votre précision :');
              lire(prec);
              Ecrire('Entrer votre estimation :');
              lire(x0);
              k <- 0;

              Repeter
                xn <- (x0 + c / x0) / 2;
                pas <- x0;
                x0 <- xn;
                k <- k + 1;
              jusqu'a(abs(xn-pas)<=prec);

            Ecrire('La racine est ',xn,' et le nombre d''itérations est : ',k);
            Fin.

Exercice 3 : 05 pts Statistiques sur un tableau d'entiers

1) Calcul de la Moyenne :

            
            Const N=100 ;
            fonction CalculMoyenne(t : tableau[1..N] de entier) : reel
            Var somme : entier ; moyenne : reel ;

            Debut
                somme <- 0;
                Pour i de 1 a N Faire
                    somme <- somme+t[i];
                Fin Pour
                moyenne <- somme/N;
                CalculMoyenne <- moyenne;
            Fin ;

2) Calcul de la Médiane :

            
            fonction CalculMediane(t : tableau[1..N] de entier) : reel

            Debut
            TriBulle(t); Co Tri du tableau par ordre croissant (utilisation principe de l'algorithme de TriBulle du Probleme) fco
                Si (N mod 2 <> 0) Alors
                    mediane <- t[N/2];
                Sinon
                    mediane <- (t[(N/2)+1]+t[N/2])/2;
                FinSi
                CalculMediane <- mediane;
            Fin ;

3) Résolution du Problème (Différence entre Moyenne et Médiane) :

            
            fonction DifferenceMoyenneMediane(t : tableau[1..N] de entier) : reel
            Var moy, med, difference : reel ;

            Debut
                moy <- CalculMoyenne(t);
                med <- CalculMediane(t);
                difference <- (moy-med);
                DifferenceMoyenneMediane <- difference;
            Fin;

Voici la version HTML5 du code et de l'exécution du tri à bulles : ```html

Problème : 09 pts Algorithme de Tri et De Recherche

Partie A : Tri Bulle

1) Principe du Tri Bulle

Le tri à bulles est un algorithme de tri classique. Son principe est simple, et il est très facile à implémenter. On considère un tableau de nombres $T$, de taille $N$. L’algorithme parcourt le tableau, et dès que deux éléments consécutifs ne sont pas ordonnés, les échange. Après un premier passage, on voit que le plus grand élément se situe bien en fin de tableau. On peut donc recommencer un tel passage, en s’arrêtant à l’avant-dernier élément, et ainsi de suite. Au $i$-ème passage on fait remonter le $i$-ème plus grand élément du tableau à sa position définitive, un peu à la manière de bulles qu’on ferait remonter à la surface d’un liquide, d’où le nom d'algorithme de tri à bulles.

2) Algorithme du Tri Bulle

            
            Algorithme TriBulles;
                Const
                    N = 100;
                Var
                    t: tableau [1..N] de Entier;
                    val, j, i: Entier;
                Debut
                    Éecrire("Lecture des elements du tableau");
                    Pour i de 1 a N faire
                        Éecrire("Entrer le ", i, "eme element");
                        Lire(t[i]);
                    Fin Pour
                    i <- N;
                    Tant que (i > 1) Faire
                        Pour j de 2 a i faire
                            Si (t[j] < t[j-1]) Alors
                                val <- t[j];
                                t[j] <- t[j-1];
                                t[j-1] <- val;
                            Fin Si
                        Fin Pour
                        i <- i - 1;
                    Fin Tant Que
                    Éecrire("Le tableau trie est :");
                    Pour i de 1 a N faire
                        Éecrire(t[i]);
                    Fin Pour
                Fin.

3) Exécution du Tri Bulle sur un Tableau

Étape	Permutation	Valeur	Tableau après permutation	i	j
Initial	-	-	101 115 30 64 47 50 20	-	-
1	$t[2] \leftrightarrow t[1]$	$30 \leftrightarrow 115$	101 30 115 64 47 50 20	7	2
2	$t[3] \leftrightarrow t[2]$	$64 \leftrightarrow 115$	101 30 64 115 47 50 20	7	3
3	$t[4] \leftrightarrow t[3]$	$47 \leftrightarrow 115$	101 30 64 47 115 50 20	7	4
4	$t[5] \leftrightarrow t[4]$	$50 \leftrightarrow 115$	101 30 64 47 50 115 20	7	5
5	$t[6] \leftrightarrow t[5]$	$20 \leftrightarrow 115$	101 30 64 47 50 20 115	7	6
Après l'itération 1	-	-	101 30 64 47 50 20 115	-	-
6	$t[1] \leftrightarrow t[0]$	$30 \leftrightarrow 101$	30 101 64 47 50 20 115	6	1
7	$t[2] \leftrightarrow t[1]$	$64 \leftrightarrow 101$	30 64 101 47 50 20 115	6	2
8	$t[3] \leftrightarrow t[2]$	$47 \leftrightarrow 101$	30 64 47 101 50 20 115	6	3
9	$t[4] \leftrightarrow t[3]$	$50 \leftrightarrow 101$	30 64 47 50 101 20 115	6	4
10	$t[5] \leftrightarrow t[4]$	$20 \leftrightarrow 101$	30 64 47 50 20 101 115	6	5
Après l'itération 2	-	-	30 64 47 50 20 101 115	-	-
11	$t[2] \leftrightarrow t[1]$	$47 \leftrightarrow 64$	30 47 64 50 20 101 115	5	2
12	$t[3] \leftrightarrow t[2]$	$50 \leftrightarrow 64$	30 47 50 64 20 101 115	5	3
13	$t[4] \leftrightarrow t[3]$	$20 \leftrightarrow 64$	30 47 50 20 64 101 115	5	4
Après l'itération 3	-	-	30 47 50 20 64 101 115	-	-
14	$t[3] \leftrightarrow t[2]$	$20 \leftrightarrow 50$	30 47 20 50 64 101 115	4	3
Après l'itération 4	-	-	30 47 20 50 64 101 115	-	-
15	$t[2] \leftrightarrow t[1]$	$20 \leftrightarrow 47$	30 20 47 50 64 101 115	3	2
Après l'itération 5	-	-	30 20 47 50 64 101 115	-	-
16	$t[1] \leftrightarrow t[0]$	$20 \leftrightarrow 30$	20 30 47 50 64 101 115	2	1
Après l'itération 6	-	-	20 30 47 50 64 101 115	-	-
Tri final	-	-	20 30 47 50 64 101 115	-	-

Remplacez la partie commentée "" par les lignes correspondant à l'exécution du tri à bulles sur votre tableau.

Partie B : Recherche Dichotomique

1) Fonction Récursive :

Certains étudiants me diront mais Mr Joël une fonction ne retourne pas deux choses Hahaha et bien comme j’avais évoqué lors d’une séance de répétition au Groupe Genius et beuh oui une fonction peut retourner deux valeurs du moins on peut avoir dans le résultat d’une fonction 1 ou plusieurs informations ceci – grâce à nos enregistrements, Ah oui !

          
            type Resultat = Enregistrement
                              found : booleen ;
                              indice : entier ;
                            FinEnregistrement ;

            fonction RechercheDico(Vect: tabReel, Key: reel, lower: entier, upper: entier): Resultat;
            var
              r: Resultat;
              mil: entier;

            Debut

              co Cas de Base de notre recursivite fco
              Si (lower > upper) alors
                r.found <- faux ;
                r.indice <- -1 ;
                RechercheDico <- r ;
              Sinon
            Co Cas de recursions de notre recursivite, faites toujours l’effort de penser recursif Fco
                mil <- (lower + upper) div 2 ;
                Si (key = Vect[mil]) alors
                  r.found <- vrai ;
                  r.indice <- mil ;
                  RechercheDico <- r ;
                Sinon
                  Si (key > vect[mil]) alors
                    RechercheDico <- RechercheDico(Vect, key, mil + 1, upper);
                  Sinon
                    RechercheDico <- RechercheDico(Vect, key, lower, mil - 1);
                  Fsi
                Fsi
              Fsi

            Fin ;

2) Fonction Itérative :

        
          type Resultat = Enregistrement
                            found : booleen ;
                            indice : entier ;
                          FinEnregistrement ;

          fonction RechercheDico(Vect: tabReel, Key: reel, lower: entier, upper: entier): Resultat;
          var
            r: Resultat;
            mil: entier;
          Debut

            co En cas de mauvaise entree au niveau des Indices du Tableau ! fco
            Si (lower > upper) alors
              r.found <- faux ;
              r.indice <- -1 ;
              RechercheDico <- r ;
            Sinon
             co Alors ici nous appliquons notre veille recherche dichotomique de facon assez astucieuse fco
              r.found <- faux ;
              Tantque (lower <= upper et r.found < > vrai) faire
                mil <- (lower + upper) div 2 ;
                Si (key = Vect[mil]) alors
                  r.found <- vrai ;
                  r.indice <- mil ;
                Sinon
                  Si (key > vect[mil]) alors
                    lower <- mil + 1 ;
                  Sinon
                    upper <- mil - 1 ;
                  Fsi
                Fsi
              Ftq
              RechercheDico <- r ;
            Fsi
          Fin ;

La persévérance, c'est ce qui rend l'impossible possible, le possible probable et le probable réalisé.

Bonne chance pour le rattrapage, les amis.

Contact WhatsApp : +237 652027193 | Réalisé par Mr Joël_Yk