ÉVALUATION EN ALGORITHMIQUE TEST  20 / XX  

Examen Corriges en Algorithme

Exercice 1 : Généralités   6.25pts

1. Définition : Algorithmique, constante, instruction. 0,75pt
2. Donner la différence fondamentale entre Boucle REPETER & la Structure SI?0,5pt
3. Qu’est-ce qu’une boucle infinie ? Donnez un exemple.0,5pt
4. Les affirmations suivantes sont-elles correctes ? (0.5*3) 1.5pts

1. Dans une boucle POUR le test s’effectue toujours.
2. Les actions internes d’une boucle REPETER peuvent ne pas être exécutées.
3. Les actions d’une boucle POUR sont toujours exécutées.

5.Donner la signification des mots clés suivant en algorithmique : mod, div, abs( ), donne un exemple d’algorithme ou vous les utilises. ((0.25*3)+0,5) 1.25pts

6. Soit l’algorithme suivant : (0,5 + 1,25) 1,75pt

• Algorithme InvariantGenius ;
• Var  s, i: entier
• Début
  • • Lire (n) ;
    • s ← 0 ;
    • Pour i de 1 à n faire
    •    s ← s + i ;
    • Fin_Pour
    • Ecrire (s) ;
• Fin.

Note : Un bon invariant de boucle doit satisfaire trois propriétés : Initialisation: l'invariant de boucle doit être vrai avant la première exécution de la boucle. Maintenance: si l'invariant est vrai avant une itération de la boucle, il devrait l'être également après l'itération. Terminaison: Lorsque la boucle est terminée, l'invariant doit nous dire quelque chose d'utile, quelque chose qui nous aide à comprendre l'algorithme.

UUUUUUUUUUUUUU

Question : (a) C’est quoi un invariant de boucle ? (b) L'invariant de boucle pour cet Algorithme est  S=$\sum _{k=0}^{\mathrm{i-1}}k$pourquoi ?

Exercice 2 : Ecriture des Algorithmes

Ecrire un algorithme qui demande successivement 20 nombres à Bob étudiants du Groupe Genius, et qui lui dise ensuite quel était le plus grand parmi ces 20 nombres : Si Bob entre par exemple :  1 2 45 6 78 9 10 23 8 4 78 90 13 100 78 9 0 1 -3 90. Notre algorithme doit pouvoir lui dire que 100 est le nombre le plus grand.

Exercice 3 : Exécution Manuelle d’un Algorithme 5pts

PROBLEME : L’Algorithme d’Euclide Pour le PGCD & le PPCM 5.5pts

Le PGCD (Plus Grand Commun Diviseur) et le PPCM (Plus Petit Commun Multiple) sont des concepts fondamentaux en mathématiques. Le PGCD est utilisé pour trouver le plus grand diviseur commun de deux entiers, tandis que le PPCM permet de déterminer le plus petit multiple commun de deux entiers. L'algorithme d'Euclide est couramment utilisé pour calculer le PGCD, et le théorème de Bézout est essentiel pour comprendre les relations entre les nombres en jeu.

1. Calcul du PGCD avec l'algorithme d'Euclide :

L'algorithme d'Euclide est une méthode efficace pour calculer le PGCD de deux entiers, a et b. Il consiste en une série de divisions successives jusqu'à ce que le reste soit nul. Voici les étapes :

Étape 1 : Divisez a par b et trouvez le reste (r₁). Remarque : a doit être plus grand queb.

Étape 2 : Remarquez que PGCD(a, b) = PGCD(b, r₁). Vous pouvez répéter ces étapes jusqu'à ce que rₙ soit égal à zéro. Le dernier quotient non nul sera le PGCD(a, b).

Mathématiquement, ces étapes peuvent être formulées comme suit :

• Étape 1 : a = bq₁ + r₁, où q₁ est le quotient et r₁ est le reste.
• Étape 2 : PGCD(a, b) = PGCD(b, r₁) = PGCD(r₁, r₂) = ... = rₙ, où rₙ est le dernier reste non nul.

2. Calcul du PPCM :

Une fois que vous avez calculé le PGCD de deux entiers a et b, le PPCM peut être calculé en utilisant la formule suivante : PPCM(a, b) = (a * b) / PGCD(a, b).

Exemple : Il s'agit de trouver le PPCM de 3080 et 1100. On calcule le PGCD de 3080 et 1100 par l'algorithme d'Euclide. On trouve : (PGCD(3080 ; 1100) = 220.
Donc  .

Question : Concevez un Algorithme qui réalise cela en fonction du principe énonce.