Faculté des Sciences METZ

DESS GMP 86-87

15.12.87

CONTROLE D'INFORMATIQUE

Question 1:

Que fait ce programme ? (seule indication donnée : on utilise la méthode dite de Monte-Carlo).

Procédures et fonctions non standard utilisées:

Program Atrouver(Input,Output);
 
VAR truc1,truc2:real;
    z,zz,zzz,zzzz:integer;
 
(*$I c:graph2d.inc *)
 
Function F1(X2,X1:real):boolean;
  var i:real;
  begin
    i:=sqr(X1)+sqr(X2);
    f1:=i<=1
  end;
 
begin
  zzzz:=0;
  zz:=0;
  ginit(1);
  gechelleort(0,1,0,1);
  repeat
    write('?');
    read(zzz);
    for z:=1 to zzz do begin
      zz:=zz+1;
      truc1:=Random;
      truc2:=Random;
      if F1(truc1,truc2) then begin
        zzzz:=zzzz+1;
        gotoxy(1,25);
        write(zz:4,' -> ',4*(zzzz/zz):12:10);
        gcouleur(3);
        gpoint(truc1,truc2)
      end else begin
        gcouleur(2);
        gpoint(truc1,truc2)
      end
    end
  until zzz=0;
  gfin
end.

Question 2:

Ce programme devrait rechercher les nombres premiers (divisibles par aucun entier excepté 1 et lui-même). Pour cela on utilise un tableau dans lequel pour chaque entier on indique s'il est premier ou non. Au départ on les suppose tous possibles. On commence à éliminer les nombres pairs (sauf 2 qui est premier). Puis pour chaque nombre impair inférieur à NB on exclut tous les multiples (un sur deux car les pairs sont déjà éliminés). Il ne reste plus à la fin qu'à imprimer les nombres non éliminés.

Programme Nombres Premiers (Input,Output);
 
CONST Maximum:=32 000;
TYPE  Tableau = array[1..Maximum]of boulean;
VAR   Premier:tableau,
      nb,fin,pas,multiple:integer;
BEGIN
  Print('Tester jusqu'où ? ');
  readln(nb);
  for i=1 to nb do premier(i):=(i/2)=o;
  premier[2]:=0;
  i: =3;
  fin:=int(sqr(nb);
  while i=<fin do begin
    if premier[i] do begin
      pas:=ix2;
      multiple:=i*i;
      while multiple<=nb do
        premier[i]:=false
        multiple:=multiple+pas
      end
    end;
    i=i+2
  end
  writeln('la liste des nombres premiers trouvés, de 1 à ';nb;' est : );
  for i:=1 to nb do if premier[i] then write(i,' ')
end

Question 3:

On cherche à intégrer dans un programme existant la procédure INTERSEC qui permet de traiter les intersections de droites et cercles. Soient les déclarations globales suivantes :

TYPE tsorte=(segment,cercle);
     tcoor=record x,y:real end;
     tseg=record
            pt1,pt2:tcoor;
            case sorte:tsorte of
              segment:();
              cercle:(centre:tcoor)
          end;

La procédure INTERSEC, que vous devez écrire, comporte deux arguments d'entrée de type TSEG, et doit rendre comme arguments de sortie un entier (entre 0 et 3) qui donnera le nombre de points d'intersection (3=infinité) et deux de type TCOOR qui donnent (si ils existent) les coordonnées des points d'intersection.

Rappel mathématique :

Une droite passant par xd,yd et xf,yf a pour équation générale :

(Y-YD)*(XF-YF) = (X-XD)*(YF-YD)

un cercle de centre xc,yc et de rayon r a pour équation

(X-XC)2 + (Y-YC)2 = R2

Cas droite-droite :

a X + b Y = c
a'X + b'Y = c'

     |a   b |
   D=|a'  b'|=ab'-a'b.

Si D=0 pas de solution sinon une solution :

      |c   b |           |a   c |
   x= |c'  b'|/D    et y=|a'  c'|/D

Cas droite-cercle :

Y=aX+b (sauf XD=XF) donc
(X-xc)2 + (aX+b-yc)2 = r2 d'où (1-a2)X2 -2xc(b-yc)X +xc2+(b-yc)2-r2 = 0

à résoudre par la méthode du déterminant, puis trouver Y par l'équation de la droite

Cas cercle-cercle : on développe les 2 équations de cercles :

X2 - 2.xc.X + xc2 + Y2 -2.yc.Y +yc2 = r2
X2 - 2.xc'.X + xc'2 + Y2 -2.yc'.Y +yc'2 = r'2

en soustrayant les 2 équations on obtient

X(2xc'-2xc) +xc2-xc'2 -Y (2yc'-2yc) +cy2-cy'2 =r2-r'2

que l'on peut mettre sous la forme Y=aX+b (sauf yc=yc'), on se ramène au cas droite-droite

Remarque : j'ai prévu de noter les questions 1 et 2 sur 6, la 3 sur 8


suivant pistes de solution retourretour au sommaire des sujets P. TRAU