Wiki du LAMA (UMR 5127) - Contributions [fr]

INFO401 corr TD TP

2009-01-28T14:00:38Z

Thomas BILLOUD :

=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...

La fonction factorielle (TD1, exercice 2, question 2)

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>

 Les fonctions sommes 

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 i^i, 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 int-> fun -> int

 Nombres pairs et impairs (TP0 Partie 2 Question 2) 

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 éxé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>

 Suite de Fibonacci 

La suite de fibonacci est tel que u0=0 u1=1 et un+2=un+1+un.

<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éja 88 additions pour calculer fib 10.

 Dragon ! 

 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

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 2n 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>

Discussion:INFO421 : Programmation fonctionnelle

2009-01-21T12:45:07Z

Thomas BILLOUD :

== Comment commencer une discussion ==

Pour commencer une discussion, il suffit de cliquer sur le '''<tt>+</tt>''' en haut de la page. Vous pouvez alors rentrer un sujet de discussion et éditer le texte comme pour le wiki.

C'est mieux de signer vos intervention en utilisant l'avant dernier bouton d'édition, ou avec <tt><nowiki>--~~~~</nowiki></tt>.

:Pour répondre, il faut « modifier » la section correspondante...
:Par soucis de visibilité, il est parfois préférable de rajouter une marge à gauche (comme ici). Pour faire ça, il faut commencer votre ligne par un «<tt>:</tt>». (Ou un «<tt>::</tt>»...)

--[[Utilisateur:Hyvernat|Hyvernat]] 12 janvier 2009 à 13:47 (CET)

== Inscription sur le Wiki ==

Voila, c'est juste pour dire que je me suis inscrit...

--[[Utilisateur:Hyvernat|Hyvernat]] 21 janvier 2009 à 11:01 (CET)

Inscription sur le Wiki
--[[Utilisateur:LAYER|LAYER]] 21 janvier 2009 à 13:39 (CET)

inscription terminée --[[Utilisateur:Laurent corantin|Laurent corantin]] 21 janvier 2009 à 13:40 (CET)

:: Travail terminé! --[[Utilisateur:Caroline|Caroline]] 21 janvier 2009 à 13:42 (CET)

:: Inscription ok --[[Utilisateur:JulienMorel|JulienMorel]] 21 janvier 2009 à 13:43 (CET)

c bon

inscription sur le wiki --[[Utilisateur:Thomas BILLOUD|Thomas BILLOUD]] 21 janvier 2009 à 13:44 (CET)

inscription confirmée --[[Utilisateur:Costa jp|Costa jp]] 21 janvier 2009 à 13:44 (CET)

Discussion:INFO421 : Programmation fonctionnelle

2009-01-21T12:44:17Z

Thomas BILLOUD :

== Comment commencer une discussion ==

Pour commencer une discussion, il suffit de cliquer sur le '''<tt>+</tt>''' en haut de la page. Vous pouvez alors rentrer un sujet de discussion et éditer le texte comme pour le wiki.

C'est mieux de signer vos intervention en utilisant l'avant dernier bouton d'édition, ou avec <tt><nowiki>--~~~~</nowiki></tt>.

:Pour répondre, il faut « modifier » la section correspondante...
:Par soucis de visibilité, il est parfois préférable de rajouter une marge à gauche (comme ici). Pour faire ça, il faut commencer votre ligne par un «<tt>:</tt>». (Ou un «<tt>::</tt>»...)

--[[Utilisateur:Hyvernat|Hyvernat]] 12 janvier 2009 à 13:47 (CET)

== Inscription sur le Wiki ==

Voila, c'est juste pour dire que je me suis inscrit...

--[[Utilisateur:Hyvernat|Hyvernat]] 21 janvier 2009 à 11:01 (CET)

coucou c'est moi

Inscription sur le Wiki
--[[Utilisateur:LAYER|LAYER]] 21 janvier 2009 à 13:39 (CET)

inscription terminée --[[Utilisateur:Laurent corantin|Laurent corantin]] 21 janvier 2009 à 13:40 (CET)

:: Travail terminé! --[[Utilisateur:Caroline|Caroline]] 21 janvier 2009 à 13:42 (CET)

:: Inscription ok --[[Utilisateur:JulienMorel|JulienMorel]] 21 janvier 2009 à 13:43 (CET)

c bon

inscription sur le wiki --[[Utilisateur:Thomas BILLOUD|Thomas BILLOUD]] 21 janvier 2009 à 13:44 (CET)

Discussion:INFO421 : Programmation fonctionnelle

2009-01-21T12:38:12Z

Thomas BILLOUD :