PSI∗ (1)
Corrigé colle d’informatique n◦ 1. > indiceplusgrand := proc(a :: array)
> local n, i, m, k;
> n := longueur(a);
Dans toutes les fonctions que vous avez à écrire, il faut faire apparaître
> m := a[0]; k := 0;
les paramètres d’entrée ainsi que le type de ces paramètres d’entrée. Par
> for i from 1 to n-1 do
exemple, pour la fonction genere suivante, proc(n :: integer) nous dit
> if a[i] > m then m := a[i]; k := i fi
que la fonction genere à un paramètre d’entrée qui est du type entier. On
> od;
exclura, sauf mention contraire, l’usage des variables globales.
> return(k);
1. Il faut faire attention au fait que rand(1..400) est une fonction et que pour > end;
avoir la valeur de cette fonction il faut ajouter «()».
> genere := proc(n :: integer) 4. Dans le programme moyenne, la variable s permet de stocker les sommes
> local t, i; partielles. À chaque passage dans la boucle, on ajoute le ième élément à s.
> t := array(0..n-1); En fin de boucle s contient la somme des éléments du tableau a. Il ne reste
> for i from 0 to n-1 do plus qu’à diviser s par la longueur du tableau pour avoir la valeur moyenne
> t[i] := rand(0..400)() du tableau.
> od; > moyenne := proc(a :: array)
> return(t); > local s, i, n;
> end; > n := longueur(a);
2. On mémorise le plus grand élément dans la variable m, on parcourt tout le > s := 0; # initialisation de s
tableau et l’on compare le ième élément avec m. Si le ième élément est plus > for i from 0 to n-1 do
grand que m on stocke sa valeur dans m sinon on ne fait rien. En fin de boucle, > s := m + a[i]
m contient le plus grand élément. > od;
> return(evalf(m/n)); # on retourne la valeur moyenne du tableau
> plusgrand := proc(a :: array) > end;
> local n, m, i;
> n := longueur(a); 5. Pas de difficulté supplémentaire pour cette fonction. Il faut seulement bien
> m := a[0]; faire attention à s’arrêter au bon moment dans la boucle pour ne pas avoir
> for i from 1 to n-1 do de débordement de tableau.
> if a[i] > m then m := a[i] fi
> od; > maxsucc := proc(a :: array)
> return(m); > local n, i, m;
> end; > n := longueur(a);
> m := abs(a[1]-a[0]);
3. On reprend le programme précédent en ajoutant une variable k dans laquelle > for i from 1 to n-2 do
on stocke l’indice du plus grand élément. Lors du parcours du tableau, si le > if abs(a[i+1]-a[i]) > m then m := abs(a[i+1]-a[i]) fi;
ième élément est plus grand que m on stocke sa valeur dans m et i dans > od;
k sinon on ne fait rien. En fin de boucle, k contient l’indice du plus grand > return(m)
élément. > end;
1/4
6. > ecrete := proc(a::array, seuil :: integer) > # On repère l’indice du plus petit élément
> local n, b, i; > elif a[i] < a[imin] then imin := i
> n := longueur(a); > fi;
> b := array(0..n-1); > od;
> for i from 0 to n-1 do > return(croiss)
> if a[i] > seuil then b[i] := seuil else b[i] := a[i] fi; > end;
> od;
> return(b);
> end; 9. Programmation de l’algorithme d’Euclide pour trouver les nombres premiers
compris entre 2 et n.
7. On remarque tout d’abord que l’amplitude maximale est donnée par la diffé-
rence entre le plus grand et le plus petit des éléments du tableau. On reprend > premier := proc(n :: integer)
le principe de la fonction plusgrand, en utilisant deux variables, M pour > local i, j, a, b, k, compteur;
stocker le plus grand élément du tableau et m pour stocker le plus petit. > a := array(2..n);
> # on intialise le tableau
> amplitude := proc(a :: array)
> for i from 2 to n do a[i] := true od;
> local n, i, m, M;
> compteur := 0;
> n := longueur(a);
> for i from 2 to n do
> m := a[0]; M := a[0];
> # si i est un nombre premier,
> for i from 1 to n-1 do
> # on met à "faux" les multiples de i
> if a[i] > M then M := a[i]
> if a[i]
> elif a[i] < m then m := a[i] fi;
> then
> od;
> # pour compter le nombre de nombres premiers
> return(M-m);
> compteur := compteur+1;
> end;
> for j from i to n/i do a[i*j] := false od;
8. La fonction croissance_max demande un peu plus de réflexion et de subtili- > fi;
tés. Pour passer de i à i + 1, on regarde si le taux de croissance entre l’élément > od;
courant et le plus petit élément entre les indices 0 et i est plus grand que la > # création du tableau de sortie des résultats
meilleure croissance trouvée jusqu’ici et sinon on regarde si le ième élément > b := array(1..compteur);
ne serait pas plus petit que celui en position imin. > k := 1;
> # on remplit le tableau des résultats
> croissance_max := proc(a :: array) > for i from 2 to n do
> local n, i, croiss, imin; > if a[i] then b[k] := i; k := k+1 fi;
> croiss := 0; # Pour stocker la meilleure croissance > od;
> imin := 0; # pour stocker le plus petit élément du tableau > return(b) # on sort le résultat.
> n := longueur(a); > end;
> for i from 1 to n-1 do >
> if a[i] - a[imin] > croiss then croiss := a[i] - a[imin];
2/4
10. Exponentiation rapide dans sa version récursive : 11. Multiplication du paysan russe : Le principe est le même que celui de l’expo-
nentiation rapide.
> expor := proc(x, n::integer) Version récursive :
> if n=1 then x
> elif n mod 2 = 0 > russer := proc(p :: integer, q :: integer)
> then expor(x,n/2)^2 > if q = 0 then return(0)
> else x*expor(x,(n-1)/2)^2 > elif q mod 2 = 0 then return(russer(p+p,q/2))
> fi; > else return(p+russer(p+p,(q-1)/2))
> end; > fi;
> end;
Exponentiation rapide dans sa version itérative :
Version itérative :
> expoi := proc(x,n::integer)
> local p, m, res; > russei := proc(a::integer,b::integer)
> m:= n; > local p, q, res;
> p := x; res := 1; > p := a;
> while m <> 0 do > q := b; res := 0;
> if m mod 2 = 0 > while q <> 0 do
> then p := p*p; m := m/2; > if q mod 2 = 0
> else res := p*res; p:=p*p; m := (m-1)/2 > then p := p+p; q := q/2;
> fi; > else res := p+res; p:=p+p; q := (q-1)/2
> od; > fi;
> return(res); > od;
> end; > return(res);
> end;
3/4
12. fonction «retourne», les indices du tableaux sont supposés allés de 0 à n − 1 13. fonction «EcartType» sur un tableau a indexé de 0 à n−1 (où n et la longueur
(où n et la longueur du tableau) du tableau)
>longueur := proc(a :: array) >moyenne := proc(a::array)
> return(nops(convert(a,list))); > local n, s, i;
> end; > n := longueur(a); s := 0;
> for i from 0 to n-1 do s := s + a[i] od;
> retourne := proc(a :: array) > return(evalf(s/n));
> local i, n ,b; > end;
> n := longueur(a);
> b := array(0..n-1); > EcartType := proc(a::array)
> for i from 0 to n-1 do > local n, m, i, s;
> b[i] := a[n-1-i]; > m := moyenne(a);
> od; > n := longueur(a);
> return(b) > s := 0;
> end; > for i from 0 to n-1 do s := s + (a[i]-m)^2 od;
> return(sqrt(s/n));
Si on veut «retourner sur place» le tableau a, c’est à dire, ne pas créer un > end;
nouveau tableau, la fonction s’écrit :
# la fonction <<echange>> permute 2 éléments dans un tableau.
> 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;
4/4 E. Le Nagard - colle_info_01(03)cor (composé avec TEX le 18/10/2003)
