« INFO401 corr TD TP » : différence entre les versions
Aller à la navigation
Aller à la recherche
(→Le TD2) |
mAucun résumé des modifications |
||
| (54 versions intermédiaires par 10 utilisateurs non affichées) | |||
| Ligne 1 : | Ligne 1 : | ||
==Préliminaires== |
|||
Pour afficher correctement dans le wiki, allez voir un peu comment on fait. Vous pouvez regarder par exemple sur le [[INFO401 | wiki du cours]] ou directement sur des articles de [http://fr.wikipedia.org/wiki/Accueil Wikipedia]. La documentation de mediawiki se trouve [http://meta.wikimedia.org/wiki/Aide:Éditeur ici]. |
|||
Un truc important : pour rentrer du code Caml, il faut mettre les balises <tt><nowiki><source lang="ocaml">...</source></nowiki>"</tt> autour de votre code. Allez par exemple voir le début de la section sur [[#Le TD1 et le TP0 | le TD1 et TP0]]. |
|||
Vous pouvez aller discuter des corrections dans les sujets de discussions associes... |
|||
==Le TD1 et le TP0== |
|||
Pour vous montrer un exemple de ce que j'attends, voila la correction de la fonction factorielle. (C'était facile...) J'ai volontairement mis beaucoup de commentaires... |
|||
<u>La fonction factorielle (TD1, exercice 2, question 2)</u> |
|||
Le but est de calculer la fonction <math>!n = 1\times2\times \cdots \times n</math> par récurrence. La version typée est verbeuse de la fonction correspondante en Caml donne : |
|||
<source lang="ocaml"> |
|||
(* fonction factorielle : c'est la factorielle habituelle des mathématiciens... *) |
|||
let rec fact (n:int) : int = |
|||
if (n>1) |
|||
then n * (fact (n-1)) |
|||
else 1 (* rq : pour que le programme ne boucle pas sur les valeurs négatives, on renvoie 1 dés que n<1 *) |
|||
</source> |
|||
Comme la fonction est récursive, il ne faut pas oublier le <tt>rec</tt> au début de la définition. |
|||
On aurait pu faire une autre version, qui fonctionne différemment sur les nombres négatifs : |
|||
<source lang="ocaml"> |
|||
let rec fact' = function |
|||
n when (n>0) -> n * fact' (n-1) |
|||
| n when (n<0) -> n * fact' (n+1) |
|||
| _ -> 1 (* si n n'est ni plus petit que 0 ni plus grand que 0, n est égal à 0, et on renvoie donc 1 *) |
|||
</source> |
|||
J'ai volontairement mis une version qui contient plusieurs choses que nous n'avons pas encore vues en cours : |
|||
* utilisation de "<tt>function</tt>" plutôt que <tt>fun</tt>, |
|||
* le symbole "<tt>|</tt>", |
|||
* le mot clé "<tt>when</tt>". |
|||
Vous devriez pouvoir comprendre ce que fait la fonction. Sinon, voici une version que vous auriez pu écrire : |
|||
<source lang="ocaml"> |
|||
let rec fact_bis = fun n -> |
|||
if (n=0) |
|||
then 1 |
|||
else begin |
|||
if (n>0) |
|||
then n*fact_bis (n-1) |
|||
else n*fact_bis (n+1) (* dans ce cas, n est forcement négatif *) |
|||
end |
|||
</source> |
|||
<u> Les fonctions sommes </u> |
|||
Il s'agit ici d'écrire la fonction qui va additionner les carrés des entiers de 1 jusqu'à un nombre donné. |
|||
Cela donne : |
|||
<source lang="ocaml"> |
|||
let rec somme_carre b = |
|||
if (b=0) then 0 |
|||
else (b*b) + somme_carre (b-1);; |
|||
</source> |
|||
Ensuite on nous demande de calculer la somme des cubes des entiers de 1 jusqu'à un nombre donné. On pourrait faire le même programme en remplaçant b*b par b*b*b, mais on va définir une fonction puissance (car elle n'existe pas d'origine sous Caml), qui nous servira aussi pour la suite... : |
|||
<source lang="ocaml"> |
|||
let rec puissance x a = |
|||
if (a = 0) then 1 |
|||
else x * puissance x (a-1);; |
|||
</source> |
|||
On doit maintenant calculer la somme des <math>i^i</math>, i variant de 1 à un nombre donné : |
|||
<source lang="ocaml"> |
|||
let rec somme_puissance b = |
|||
if (b=0) then 0 |
|||
else (puissance b b) + somme_puissance (b-1);; |
|||
</source> |
|||
On peut définir une unique fonction qui permettrait de faire toutes ces sommes, celle-ci aura pour argument une fonction quelconque : |
|||
<source lang="ocaml"> |
|||
let rec somme_fonction n f = (* f étant une fonction *) |
|||
if (n=0) then f 0 |
|||
else f n + somme_fonction (n-1) f;; |
|||
</source> |
|||
cette fonction est de type "<tt>int -> fun -> int</tt>" |
|||
<u> Nombres pairs et impairs (TP0 Partie 2 Question 2) </u> |
|||
Il faut écrire les fonctions récursives pairs et impairs, qui renvoient vrai si le nombre est pair (respectivement impair) et faux si le nombre est impair (respectivement pair); |
|||
Ici nous devons déclarer simultanément les deux fonctions, car chacune fait appel à l'autre lors de son exécution. |
|||
Cela donne : |
|||
<source lang="ocaml"> |
|||
let rec pair n = |
|||
if (n=0) then true |
|||
else impair (n-1) |
|||
and impair n = |
|||
if (n=0) then false |
|||
else pair (n-1);; |
|||
</source> |
|||
<u> Suite de Fibonacci </u> |
|||
La suite de fibonacci est tel que u<sub>0</sub>=0 u<sub>1</sub>=1 et u<sub>n+2</sub>=u<sub>n+1</sub>+u<sub>n</sub>. |
|||
<source lang="ocaml"> |
|||
let rec fib n = |
|||
if (n=0) then 0 |
|||
else if (n=1) then 1 |
|||
else fib (n-1) + fib (n-2);; |
|||
</source> |
|||
La plus grande valeur que l'on peut obtenir sans que cela soit trop long est 24157817, ce qui correspond à fib 37. |
|||
Nous trouvons qu'il faut déjà 88 additions pour calculer fib 10. |
|||
:'''Rq :''' fib de 37 prend effectivement beaucoup de temps. Il faut 39088168 additions avant d'en arriver à bout. Il est possible de faire une version de Fibonacci qui va très vite et qui calcule <tt>fib 37</tt> en seulement 36 additions... |
|||
: Comment ? |
|||
<u> Dragon ! </u> |
|||
<i> Le dragon est une créature mythique, présente dans de nombreuses cultures. |
|||
On peut déterminer deux grands types de dragons : le dragon occidental et le dragon oriental</i> |
|||
La fonction dragon a pour but de dessiner un dragon, pour cela on utilise une fonction récursive qui admet pour argument le nombre n d'itération de la fonction, et les coordonnées de 2 points. A chaque itération, la fonction calcule pour chaque segment, un nouveau point et le relie ensuite aux deux autres. |
|||
On obtient en tout 2<sup>n</sup> segments entremêlés, qui forment un dragon. |
|||
Let's go ! |
|||
<source lang="ocaml"> |
|||
let rec dragon (n:int) (a:int) (b:int) (c:int) (d:int) : unit = |
|||
if (n = 0) then (moveto a b ; lineto c d) |
|||
else begin |
|||
let x = (a+c+d-b)/2 in |
|||
let y = (b+d+a-c)/2 in |
|||
dragon (n-1) a b x y ; |
|||
dragon (n-1) c d x y |
|||
end ;; |
|||
</source> |
|||
:'''Rq : ''' votre version du dragon est bien, mais pas très précises. (Je chipote un peu...) Pour les paramètres (<tt>dragon 11 100 100 400 400</tt>), de nombreux carrés ne sont pas bien tracés. |
|||
:Comment expliquez-vous cela, et comment pouvez-vous le corriger ? |
|||
::Pour améliorer la précision je suggère de passer les coordonnées en type Float. --[[Utilisateur:Nicolas|Nicolas]] 31 janvier 2009 à 11:42 (CET) |
|||
==Le TD2== |
|||
'''Question 5 :''' |
|||
D'après la fonction récursive Fibonacci définit par <br /> |
|||
f(0)=0 <br /> |
|||
f(1)=1 <br /> |
|||
f(n+2)=f(n+1)+f(n), <br /> |
|||
comment compter le nombre d'appels récursifs en Caml? <br /> |
|||
let rec fib n = |
|||
if (n<2) then (n,0) |
|||
else let t = fib (n-1) in |
|||
let s = fib (n-2) in |
|||
(fst t + fst s , snd t + snd s + 1) |
|||
==Le TP1 - début== |
|||
--- à venir --- |
|||