CPI - 1ère Année - Année Universitaire 2011/2012 - (Semestre 1)
EMD1 d’ALGORITHMIQUE
Date : lundi 31 octobre 2010
Durée : 2 Heures
DOCUMENTS INTERDITS
EXERCICE 1 (10 points. Analyse 4pts, algorithme 6 pts) :
La multiplication squelettique est ce que l’on appelle un astérithme. C’est une
multiplication dans laquelle des chiffres sont remplacés par des astérisques et ou le
problème consiste à retrouver les trois nombres la composant.
Construire l’algorithme qui nous permet de résoudre la multiplication squelettique
particulière suivante :
4
x 59
= 7392
EXERCICE 2 (10 points. Analyse 4pts, algorithme 6 pts) :
Un nombre semi-premier est un nombre qui est le produit de deux nombres
premiers. Construire la solution qui nous permet d’afficher les n premiers nombres semi-
premiers.
Exemple : 15 est un nombre semi-premier, car 15 = 3 * 5, et 3 et 5 sont premiers
tous les deux.
Travail à Faire :
Un bonus de 2 points vous sera accordé si vous programmez l’algorithme de
l’exercice 1 (1/4 point sera ôté par erreur)
ATTENTION: Votre solution doit ABSOLUMENT et tenir compte du formalisme étudié en
cours !
De plus, deux (2) points seront déduits de la note pour toute copie non soignée.
Alors soignez votre travail et bon courage !
(EMD1_2011_2012.doc – CHERGOU –SI TAYEB)
EXERCICE 1
ANALYSE
On appellera X, le multiplicande ; Y , le multiplicateur et P , le produit de X par Y
X: 4
Y: 59
P : = 7392
La solution la plus simple est la suivante :
• On prend une variable qui va contenir VRAI si une solution est trouvée, au départ SOLUTION = FAUX
• On fait varier X = 14000, 14001, 14002, 14003,….. et pour chaque valeur de X :
o On vérifie si la deuxième position de X est égale à 4 , si c’est le cas :
On fait varier Y= 509, 519, 529, …(le pas est 10 car l’étoile occupe la position des
dizaines) , et pour chaque valeur de Y :
¾ On fait le produit P = X . Y
¾ Si P se termine par 392 ET débute par 7 alors nous avons trouvé la
solution, SOLUTION = VRAI
On s’arrêtera si (SOLUTION = Vrai) OU (Y > 599) (voir énoncé)
On s’arrêtera si (SOLUTION = VRAI) OU (X > 91999) (plus grande valeur possible de X )
• Si SOLUTION = Vrai , on écrit ( X, Y, P)
• Si SOLUTION = FAUX on écrit (Erreur dans l’énoncé)
ALGORITHME
ALGORITHME e11_1112
variables x,y,p : entier
solution : booléen
DEBUT
Solution ÅFAUX
X Å 14000
REPETER
SI (x div 1000) MOD 10 = 4 then
DSI
y Å 509
REPETER
pÅx*y
SI (p mod 1000 =392) ET (p div 1000000 = 7) ALORS solution := VRAI
y Å y+10
JUSQU’A (solution = VRAI) OU (y > 599)
FSI
x Å x+1
JUSQU’A (solution = VRAI) OU ( x > 91999)
SI solution = VRAI ALORS ECRIRE(x, ' * ', y,' = ',p)
SINON ECRIRE (' Erreur dans l''enonce')
FIN
Nota : Pour cet exercice d’autre solution sont possibles. On peut, par exemple, considérer que X est
composé de trois parties ( a = , b = 1 et c =) ou a et b prendront des valeurs différentes et ensuite
on construira le nombre X en concaténant les 9 nombres a, b et c . Et on fera la même chose pour le
nombre Y,…..
Mais cette solution sera plus longue à construire.
EXERCICE 2
ANALYSE
L’idée de base consiste à prendre un nombre X , tel que X = divseur * quot . On pourra dire que X est semi premier si Divseur
ET Quot sont tous les deux premiers. Pour cela :
• Donner N ( le nombre de nombres semi premiers à afficher)
• Nsp = 0 ( on initialise le compteur de nombres semi-premiers)
• On va faire varier X = 2,3,4,5,6,7,… et à chaque fois
On fait varier i = 2,3,4,…, X div 2 ( on va chercher tous les diviseurs de X)
o Si X mod I = 0 ( i est un diviseur de X)
¾ Divseur = i (divseur est le diviseur)
¾ Quot = X div i ( quot est le quotient)
¾ On va vérifier si Divseur est premier , pour cela :
On divise Divseur par j = 2,3,4,5
Et on s’arrête lorsque (Divseur Mod j = 0) OU (J> Divseur Div 2)
( si on a trouvé un diviseur alors Divseur n’est pas premier, ou alors on n’a trouvé aucun
diviseur , alors il est premier) donc
Si j > Divseur Div 2 , Divseur est premier , et dans ce cas on va vérifier si Quot est lui
aussi premier. Pour cela
- On divise Quot par j = 2,3,4,5
Et on s’arrête lorsque (QUOT Mod j = 0) OU (J> Quot Div 2)
- Si j > Quot div 2, Quot est lui aussi premier, alors
¾ On incrémente Nsp (on vient de trouver un nombre semi-premier)
¾ On écrit le nombre semi-premier X
On incrémente X. X= X+1 ( on prend un nouveau X)
Et on s’arrête lorsque Nsp = N ( on a trouvé et affiché les n premiers nombres semi-premiers)
ALGORITHME
ALGORITHME e11_1112
Variables n,nsp,i,x,j,quot, divseur : entier
DEBUT
Lire (n)
Nsp Å 0
XÅ2
Répéter
Pour I allant de 2 A x div 2 Faire
Dpour
Si x mod i =0 Alors
Dsi
Divseur Å i
Quot Å x div i
jÅ1
Répéter
j Å j+1
Jusqu’à (divseur mod j = 0) OU (j > divseur div 2)
Si j > divseur Div 2 Alors
Dsi
JÅ1
Répéter
j Å j+1
Jusqu’à (Quot mod j = 0) OU (j > quot div 2)
Si j > quot div 2 Alors
Dsi
Nsp Å nsp +1
Ecrire ( Divseur,' ',quot,' ', x)
Fsi
Fsi
Fsi
Fpour
x Å x +1
Jusqu’à nsp = n
FIN
PROGRAMME EXO1
program e11_1112;
uses crt;
var x,y,p: longint;
solution:boolean;
BEGIN
clrscr;
solution:=false;
x:=14000;
repeat
if (x div 1000) mod 10 = 4 then
BEGIN
y := 509;
repeat
p := x * y;
if (p mod 1000 =392) and (p div 1000000 = 7) then solution := true;
y := y+10;
until (solution = true) OR (y > 599);
END;
x := x+1;
until (solution = true) OR ( x > 91999);
if solution = true then write(x, ' * ', y,' = ',p)
else write (' Erreur dans l''enonce');
readln;
END.
ESI CPI 1 - Corrigé EMD 1 du 31 octobre 2011
BAREME
TOUT COPIE NON SOIGNEE DOIT SERA SANCTIONNEE ( max. – 2 points)
EXO_1 (10 points)
ANALYSE ALGORITHME
Boucle pour la construction de 1 1,5
X (initialisation,
incrémentation et test de fin )
Et vérification que le 2ième
chiffre de X est 4
Boucle pour la construction de 1 1,5
Y (initialisation,
incrémentation et test de fin )
Elle doit être imbriquée dans la
boucle des X
Vérification que P commence 1 1,5
par 7 et se termine par 392
Clarté et Structuration des 1
idées de l’analyse
Conformité de l’algorithme 1,5
avec l’analyse, structures de
contrôle appropriées,
respect du formalisme, soin
4 pts 6pts
EXO_2 (10 points)
ANALYSE ALGORITHME
Boucle générale des X 1/2 1
Recherche des diviseurs de X, 1 1.5
boucle imbriquée dans celle
des X. (X= diviseur * quotient)
Vérification que diviseur ET 1 1.5
quotient sont premiers
Emplacement, incrémentation 1/2 1
du compteur de nombres semi-
premiers.
Emplacement de l’écriture
Clarté et Structuration des 1
idées de l’analyse
Conformité de l’algorithme 1
avec l’analyse, structures de
contrôle appropriées,
respect du formalisme, soin
4 pts 6pts
PROGRAMMATION : dans le contexte et à corriger seulement si l’analyse et les algorithmes sont
terminés.
(-0.5 pt./erreur)
Il s’agit d’un BONUS, il faut donc qu’il soit mérité.