Corrigé feuille d'exercices n°2

exo1 : recherche de nombres premiers par le crible d'Erathostène.

> premier := proc(n :: integer)
local i, j, a, b, k, compteur;
a := array(2..n);
for i from 2 to n do a[i] := true od; # on intialise le tableau
compteur := 0;
for i from 2 to n do
# si i est un nombre premier, on met à "faux" les multiples de i
if a[i]
then
compteur := compteur+1; # pour compter le nombre de nombres premiers
for j from i to n/i do a[i*j] := false od;
fi;
od;
b := array(1..compteur); # création du tableau de sortie des résultats
k := 1;
for i from 2 to n do # on remplit le tableau des résultats
if a[i] then b[k] := i; k := k+1 fi;
od;
return(b) # on sort le résultat.
end;

>

> print(premier(100));

Exo 2 : exponentiation rapide
Version récursive :

> expor := proc(x, n::integer)
if n=1 then x
elif n mod 2 = 0
then expor(x,n/2)^2
else x*expor(x,(n-1)/2)^2
fi;
end;

expor(2,11);

Version itérative

> expoi := proc(x,n::integer)
local p, m, res;
m:= n;
p := x; res := 1;
while m <> 0 do
if m mod 2 = 0
then p := p*p; m := m/2;
else res := p*res; p:=p*p; m := (m-1)/2
fi;
od;
return(res);
end;

> expoi(2,11);

Exo 3 : multiplication du paysan russe. Le principe est le même que celui de l'exponentiation rapide.

Version récursive :

> russer := proc(p :: integer, q :: integer)
if q = 0 then return(0)
elif q mod 2 = 0 then return(russer(p+p,q/2))
else return(p+russer(p+p,(q-1)/2))
fi;
end;

> russer(34,78);

Version itérative

> russei := proc(a::integer,b::integer)
local p, q, res;
p := a;
q := b; res := 0;
while q <> 0 do
if q mod 2 = 0
then p := p+p; q := q/2;
else res := p+res; p:=p+p; q := (q-1)/2
fi;
od;
return(res);
end;

> russei(34,78);

Exo 4 : fonction <<retourne>>, les indices du tableaux sont supposés allés de 0 à n-1 (où n et la longueur du tableau)

> longueur := proc(a :: array)
return(nops(convert(a,list)));
end;

> retourne := proc(a :: array)
local i, n ,b;
n := longueur(a);
b := array(0..n-1);
for i from 0 to n-1 do
b[i] := a[n-1-i];
od;
return(b)
end;

Si on veut <<retourner sur place>> le tableau a, la fonction s'écrit :

> echange := proc(a::array,i::integer, j :: integer)
local c;
c:= a[i]; a[i] := a[j]; a[j] := c;
end;

> retourne := proc(a :: array)
local i, n;
n := longueur(a);
for i from 0 to (n-1)/2 do
echange(a,i,n-1-i);
od;
return(a)
end;

Exo 5 : fonction << EcartType >> sur un tableau a indéxé de 0 à n-1 (où n et la longueur du tableau)

> moyenne := proc(a::array)
local n, s, i;
n := longueur(a); s := 0;
for i from 0 to n-1 do s := s + a[i] od;
return(evalf(s/n));
end;

> EcartType := proc(a::array)
local n, m, i, s;
m := moyenne(a);
n := longueur(a);
s := 0;
for i from 0 to n-1 do s := s + (a[i]-m)^2 od;
return(sqrt(s/n));
end;