Maple - TD no 1 (Corrigé)
 |
Maple - TD no 1 (Corrigé) |
Exercice 1 -
1. Somme des n premiers entiers : somme:=proc(n) > local res, i: > res:=0: > for i from 1 to n do > res:=res+i > od: > res: > end;
2. On peut par exemple écrire : prod:=proc(n) > local res, i: > res:=1: > for i from 3 to n by 3 do > res:=res*i > od: > res: > end:
3. On doit cette fois utiliser une boucle while : p2:=proc(n) > local i: > i:=0: > while 2^i <= n do > i:=i+1 > od: > 2^i: > end: 1
Exercice 2 -
1. Calcul itératif de la factorielle : fact1:=proc(n) > local res, i: > res:=1: > for i from 1 to n do > res:=res*i > od: > res: > end: On constate que l'on a besoin d'une unique variable intermédiaire (res), et non pas de n variables intermédiaires ! Inutile de remplacer > res:=1: > for i from 1 to n do > res:=res*i > od: > res: par > res[0]:=1: > for i from 1 to n do > res[i]:=res[i-1]*i > od: > res[n]:
2. On appelle récursivement la procédure que l'on dé nit. Il ne faut pas oublier le cas d'arrêt lorsque n = 0. fact2:=proc(n) > local res: > if n=0 then > res:=1 > else > res:=fact2(n-1)*n > fi: > res: > end:
Exercice 3 -
On suit le comportement de la procédure décrit dans l'énoncé : power2:=proc(n) > local res: > if n=0 then > res:=1 > elif irem(n,2)=0 then > res:=(power2(n/2))^2 2 > else > res:=2*(power2((n-1)/2))^2 > fi: > res: > end:
Exercice 4 -
1. La procédure naïve parcourt la séquence en mémorisant à chaque étape : le minimum des distances de s[i] à p pour les i déjà visités (dans la variable min) ; l'indice i pour lequel ce minimum est atteint (dans la variable res). On peut par exemple initialiser min et res pour i = 1. proche1:=proc(s,p) > local n, min, res, i, aux: > n:=nops(s): > min:=abs(s[1]-p): > res:=1: > for i from 2 to n do > aux:=abs(s[i]-p); > if aux < min then > min:=aux: > res:=i > fi > od: > s[res]: > end: On calcule la longueur de s, ce qui peut se faire en O(n). On fait un nombre constant d'opérations pour chaque i allant de 2 à n, ce qui est également en O(n). Cet algorithme est donc linéaire.
2. On suit l'algorithme donné dans l'énoncé : proche2:=proc(s,p,n) > local res, milieu, a, b, i, s1, s2: > if n = 1 then > res:=s[1] > else > milieu:=iquo(n,2): > a:=s[milieu]: > b:=s[milieu+1]: > if a > p then > s1:=[seq(s[i],i=1..milieu)]: > res:=proche2(s1,p,milieu) > elif b < p then > s2:=[seq(s[i],i=milieu+1..n)]: > res:=proche2(s2,p,n-milieu) > elif p-a > b-p then > res:=b 3 > else > res:=a > fi > fi: > res: > end: Notons C(n) = C 0 (q) la complexité pour une liste de longueur n = 2q . On a la formule de récurrence suivante : C(1) = 1 ⇔ C 0 (0) = 1 C(n) 6 C(n/2) + 1 si n > 2 ⇔ C 0 (q) 6 C 0 (q − 1) + 1 si q > 1 Si n > 2, on a uniquement une borne supérieure : en e et, dans le cas où a < p < b, la procédure s'arrête immédiatement (pas d'appel récursif). La suite (C 0 (q))q∈N est inférieure ou égale à une suite arithmétique de raison 1 et de premier terme 1, donc pour tout q ∈ N : C 0 (q) 6 q + 1 Or, pour tout n ∈ N puissance de 2 : C(n) = C 0 (log(n)) Donc, pour tout n ∈ N puissance de 2 : C(n) 6 log(n) + 1 Cet algorithme est donc en O(log(n)).
1. Somme des n premiers entiers : somme:=proc(n) > local res, i: > res:=0: > for i from 1 to n do > res:=res+i > od: > res: > end;
2. On peut par exemple écrire : prod:=proc(n) > local res, i: > res:=1: > for i from 3 to n by 3 do > res:=res*i > od: > res: > end:
3. On doit cette fois utiliser une boucle while : p2:=proc(n) > local i: > i:=0: > while 2^i <= n do > i:=i+1 > od: > 2^i: > end: 1
Exercice 2 -
1. Calcul itératif de la factorielle : fact1:=proc(n) > local res, i: > res:=1: > for i from 1 to n do > res:=res*i > od: > res: > end: On constate que l'on a besoin d'une unique variable intermédiaire (res), et non pas de n variables intermédiaires ! Inutile de remplacer > res:=1: > for i from 1 to n do > res:=res*i > od: > res: par > res[0]:=1: > for i from 1 to n do > res[i]:=res[i-1]*i > od: > res[n]:
2. On appelle récursivement la procédure que l'on dé nit. Il ne faut pas oublier le cas d'arrêt lorsque n = 0. fact2:=proc(n) > local res: > if n=0 then > res:=1 > else > res:=fact2(n-1)*n > fi: > res: > end:
Exercice 3 -
On suit le comportement de la procédure décrit dans l'énoncé : power2:=proc(n) > local res: > if n=0 then > res:=1 > elif irem(n,2)=0 then > res:=(power2(n/2))^2 2 > else > res:=2*(power2((n-1)/2))^2 > fi: > res: > end:
Exercice 4 -
1. La procédure naïve parcourt la séquence en mémorisant à chaque étape : le minimum des distances de s[i] à p pour les i déjà visités (dans la variable min) ; l'indice i pour lequel ce minimum est atteint (dans la variable res). On peut par exemple initialiser min et res pour i = 1. proche1:=proc(s,p) > local n, min, res, i, aux: > n:=nops(s): > min:=abs(s[1]-p): > res:=1: > for i from 2 to n do > aux:=abs(s[i]-p); > if aux < min then > min:=aux: > res:=i > fi > od: > s[res]: > end: On calcule la longueur de s, ce qui peut se faire en O(n). On fait un nombre constant d'opérations pour chaque i allant de 2 à n, ce qui est également en O(n). Cet algorithme est donc linéaire.
2. On suit l'algorithme donné dans l'énoncé : proche2:=proc(s,p,n) > local res, milieu, a, b, i, s1, s2: > if n = 1 then > res:=s[1] > else > milieu:=iquo(n,2): > a:=s[milieu]: > b:=s[milieu+1]: > if a > p then > s1:=[seq(s[i],i=1..milieu)]: > res:=proche2(s1,p,milieu) > elif b < p then > s2:=[seq(s[i],i=milieu+1..n)]: > res:=proche2(s2,p,n-milieu) > elif p-a > b-p then > res:=b 3 > else > res:=a > fi > fi: > res: > end: Notons C(n) = C 0 (q) la complexité pour une liste de longueur n = 2q . On a la formule de récurrence suivante : C(1) = 1 ⇔ C 0 (0) = 1 C(n) 6 C(n/2) + 1 si n > 2 ⇔ C 0 (q) 6 C 0 (q − 1) + 1 si q > 1 Si n > 2, on a uniquement une borne supérieure : en e et, dans le cas où a < p < b, la procédure s'arrête immédiatement (pas d'appel récursif). La suite (C 0 (q))q∈N est inférieure ou égale à une suite arithmétique de raison 1 et de premier terme 1, donc pour tout q ∈ N : C 0 (q) 6 q + 1 Or, pour tout n ∈ N puissance de 2 : C(n) = C 0 (log(n)) Donc, pour tout n ∈ N puissance de 2 : C(n) 6 log(n) + 1 Cet algorithme est donc en O(log(n)).
