SERIE 5 PCSI 2014 - 2015 CLASSES PREPARATOIRES AUX GRANDES ECOLES : CPGE Option : Physique Chimie et Sciences de l’Ingénieur (PCSI) Etablissement : CPGE vérification du code Enseignante : OMAR IBN LKHATTAB SERIE N°5 L.OUSTOUH Exercice 1 : On considère l’algorithme suivant : Données : un entier naturel a et un entier b Résultat : un entier p p 0 m 0 Tant que m < a Faire p p + b m m+ 1 Fin Tant que 1. Donner la valeur finale de p lorsque (a; b) = (3; 5) et (a; b) = (4;-3). Que semble faire cet algorithme ? 2. Justifier que cet algorithme se termine. Quelle est la valeur de m à la fin de la boucle ? 3. Vérifier que «p = m*b» est un invariant de boucle et prouver la conjecture faite à la première question. 4. Estimer la complexité. Exercice 2 : On considère l’algorithme suivant. Données : un nombre a et un entier naturel n Résultat : un nombre p p 1 b a m n Tant que m > 0 Faire Si m mod 2<>0 Alors p p*b Fin Si b b*b mm div 2 Fin Tant que L.OUSTOUH 1/2 CPGE ISMAILIA SERIE 5 PCSI 2014 - 2015 1. Donner la valeur finale de p lorsque (a; n) = (3; 6) et (a; n) = (4; 5). Que fait cet algorithme ? 2. Justifier que l’algorithme se termine. Quelle est la valeur de m à la fin de la boucle . 3. Vérifier que «pbm = an » est un invariant de boucle. 4. estimer la complexité Exercice 3 : On représentera un polynôme P = par la liste [p0; p1; : : : ; pn] de ses coefficients. On considère l’algorithme suivant : Données : la liste [p0; : : : ; pn] des coefficients d’un polynôme P un nombre x Résultat : un nombre r r 0 Pour i n à 0 pas -1 Faire r r*x + pi Fin Pour 1. Donner la valeur finale de r lorsque P = 2 + 3X - X2 + 3X3 et x = 3. 2. Montrer que «r = »est un invariant de boucle. 3. Que fait cet algorithme ? 4. estimer la complexité Page 2 sur 2