Up  

Module Cdst


module Cdst: sig  end
MIAS 24: Devoir sur table du 26 Nov. 2003

Pages engendrées avec l'outil ocamldoc




Exo. I



Quest. I.1

val pi : float
valeur approchée du nombre pi

Quest I.2

val cart_of_pol : float -> float -> float * float
(cart_of_pol d t) renvoie les coordonnées cartésiennes corespondant aux coordonnées polaires d'angle t et de mesure d.

Quest I.3: voir ci-dessus Cdst.cart_of_pol


Quest I.4

val spirale : unit -> unit
spirale() écrit sur la sortie standard les coordonnées cartésiennes des points d'une spirale d'Archimède donnés par la suite de coordonnées polaire d'angle variant de 0 à 13pi/2 avaec un pas de pi/60
val spirale_a : unit -> unit
Variante: utilise une boucle for


Exo. II



Quest II.1

val add_elt : 'a -> 'a list -> 'a list
(add_elt e s) ajoute l'élément e à la liste s s'il n'y figure pas déjà.

Jeu de tests pour add_elt

let s = (add_elt 1 []);;

let s = (add_elt 1 s);;

let s = (add_elt 2 s);;

let s = (add_elt 3 s);;

let s = (add_elt 3 s);;

let s = (add_elt 2 s);;

let s = (add_elt 1 s);;

val add_elt_a : 'a -> 'a list -> 'a list
Variante: utilise List.mem

Quest II.2

val set_of_list : 'a list -> 'a list
set_of_list xs renvoie l'ensemble (i.e. liste sans redondance) des éléments de xs

Jeu de tests pour set_of_list

let s = (set_of_list []);;

let s = (set_of_list [1;2;3]);;

let s = (set_of_list [1;1;2;3]);;

let s = (set_of_list [1;2;3;1]);;

let s = (set_of_list [1;2;2;3]);;

let s = (set_of_list [1;2;3;2]);;

let s = (set_of_list [3;1;2;3]);;

let s = (set_of_list [1;3;2;3]);;

val set_of_list_a : 'a list -> 'a list
Variante: utilise Cdst.add_elt (Quest II.1)
val set_of_list_b : 'a list -> 'a list
Variante: fonction locale récursive terminale
val set_of_list_c : 'a list -> 'a list
Variante: utilise l'itérateur List.fold_left

Quest II.3

val union : 'a list -> 'a list -> 'a list
(union s1 s2) revoie l'union des ensembles s1 et s2

Jeu de tests pour union

(union [] [])

(union [] [1;2;3])

(union [1;2;3] [])

(union [1;2;3] [1;2;3])

(union [1;2;3] [2;4;6])

(union [1;3;5] [2;4;6])

val union_a : 'a list -> 'a list -> 'a list
Variante: récursive terminale; utilise s2 comme accumaulatuer
val union_b : 'a list -> 'a list -> 'a list
Variante: utilise l'itérateur List.fold_left
val inter : 'a list -> 'a list -> 'a list
(inter s1 s2) renvoie l'intersection des ensembles s1 et s2

Jeu de tests pour inter

(inter [] [])

(inter [] [1;2;3])

(inter [1;2;3] [])

(inter [1;2;3] [1;2;3])

(inter [1;2;3] [2;4;6])

(inter [1;3;5] [2;4;6])

val inter_a : 'a list -> 'a list -> 'a list
Variante: fonction locale récursive terminale.
val inter_b : 'a list -> 'a list -> 'a list
Variante: fonction locale récursive terminale; utilise le caractère fonctionnel du if.
val inter_c : 'a list -> 'a list -> 'a list
Variante: utilise l'itérateur List.filtre: les éléments de s1 inter s2 sont les élements de s1 qui sont aussi dans s2.


Exo. III



Quest. III.1


type bin_seq1 = bool list
Première possibilité: codage d'une suite par une liste (1).


type bin_seq2 = bool array
Deuxième possibilité: codage d'une suite par un tableau (2).


Quest. III.2 on donnera des solution pour les deux codages (1) et (2).


Codage avec des listes (1)

val nb_occ_elt1 : 'a -> 'a list -> int
(nb_occ_elt1 e s) renvoie le nombre d'occurrences de e dans la suite binaire s.

Jeu de tests pour nb_occ_elt1 (nb_occ_elt1 1 [])

(nb_occ_elt1 1 [1])

(nb_occ_elt1 1 [1;1])

(nb_occ_elt1 1 [1;2;1])

(nb_occ_elt1 1 [2;3;4])

(nb_occ_elt1 1 [1;2;3;4])

(nb_occ_elt1 1 [2;3;4;1])

val nb_occ_elt1_a : 'a -> 'a list -> int
Variante: utilise la fonctionnalité de if.
val nb_occ_elt1_b : 'a -> 'a list -> int
Variante: utilise l'itérateur List.fold_left.
val nb_occ_elt1_c : 'a -> 'a list -> int
Variante: utilise l'itérateur List.iter ainsi qu'une référence locale.

Codage avec des tableaux (2)

val nb_occ_elt2 : 'a -> 'a array -> int
(nb_occ_elt2 e s) renvoie le nombre d'occurrences de e dans la suite binaire s.
val nb_occ_elt2_a : 'a -> 'a array -> int
Variante: utilise l'itérateur Array.iter.

Quest III.3


Codage avec des listes (1)

val alt_seq1 : 'a list -> bool
(alt_seq1 s) renvoie true si et seulement si s est une suite binaire alternée.

Jeu de tests pour alt_seq1

(alt_seq1 [])

(alt_seq1 [0])

(alt_seq1 [1])

(alt_seq1 [0;1])

(alt_seq1 [1;0])

(alt_seq1 [0;1;0])

(alt_seq1 [1;0;1])

(alt_seq1 [0;1;0;1])

(alt_seq1 [1;0;1;0])

(alt_seq1 [0;1;0;0])

(alt_seq1 [1;0;0;1])


Codage avec des tableaux (2)

val alt_seq2 : 'a array -> bool
(alt_seq2 s) renvoie true si et seulement si s est une suite binaire alternée.
val alt_seq2_b : 'a array -> bool
Variante: utilise une boucle while: la fonction retourne false dès que la suite n'est plus alternée.

Commentaire: solution préférable ici.


Quest. III.4


Codage avec des listes (1)

val nb_sub_hom1 : 'a -> 'a list -> int
(nb_sub_hom1 e s ) renvoie le nombre de sous-suites e-homogènes de s.

Algorithme: on explore (quand c'est possible) les éléments deux par deux, on compte +1 lorsque l'on "sort" d'une (sous)suite de e.


Jeu de tests pour nb_sub_hom1

(nb_sub_hom1 1 [])

(nb_sub_hom1 1 [1])

(nb_sub_hom1 1 [1;1])

(nb_sub_hom1 1 [1;1;1])

(nb_sub_hom1 1 [1;0])

(nb_sub_hom1 1 [1;1;0])

(nb_sub_hom1 1 [1;1;1;0])

(nb_sub_hom1 1 [0;1])

(nb_sub_hom1 1 [0;1;1])

(nb_sub_hom1 1 [0;1;1;1])

(nb_sub_hom1 1 [1;0;1])

(nb_sub_hom1 1 [1;1;0;1])

(nb_sub_hom1 1 [0;1;0])

(nb_sub_hom1 1 [0;1;1;0])

(nb_sub_hom1 1 [0;1;1;0;1])

val nb_sub_hom1_a : 'a -> 'a list -> int
Variante: réécriture (racourcie) des tests
val nb_sub_hom1_b : 'a -> 'a list -> int
Variante: utilise une référence locale (compteur).
val nb_sub_hom1_c : 'a -> 'a list -> int
Variante: utilise un if unilatère.
val nb_sub_hom1_d : 'a -> 'a list -> int
Variante: utilise deux références locales: un compteur et un booléen qui sert à déterminé la valeur du dernier élément traité (e ou non).
val nb_sub_hom1_e : 'a -> 'a list -> int
Variante: factorisation des tests.
val nb_sub_hom1_f : 'a -> 'a list -> int
Variante: autre algorithme: alterner un traitement pour les éléments différents de e et un second pour les éléments égaux à e.

Utilise des définitions (locales) mutuellement récursives.


Codage avec des tableaux (2)

val nb_sub_hom2 : 'a -> 'a array -> int
(nb_sub_hom2 e s) renvoie le nombre de sous-suites e-homogènes de s.
val nb_sub_hom2_a : 'a -> 'a array -> int
Variante: l'autre algorithme avec des boucles while.

Quest. III.5


Codage avec des listes (1)

val max_sub_hom1 : 'a -> 'a list -> int
(max_sub_hom1 e s) renvoie la longueur de la plus longue sous-suite e-homogène de s.

Jeu de tests pour max_sub_hom1 analogue à nb_sub_hom1


Codage avec des tableaux (2)

val max_sub_hom2 : 'a -> 'a array -> int
(max_sub_hom2 e s) renvoie la longueur de la plus longue sous-suite e-homogène de s.