Université Pierre Marie Curie
Maîtrise d'informatique --- AlgoProg
Mise à niveau Objective Caml
T.M.E 2

E. Chailloux   P. Manoury

2-3 Oct. 2002

1   Triangle de Pascal

Questions

1. définir une fonction print_triangle qui affiche le triangle de Pascal contenu dans une matrice carrée. On n'affiche que la partie pertinente de la matrice.
2. définir une fonction make_triangle telle que make_triangle n crée une matrice (carrée) contenant les valeurs d'un triangle de Pascal de hauteur n+1.
3. si le coeur vous en dit, améliorez ces deux fonctions de façon à ce qu'elle ne créent et n'utilisent que l'espace mémoire nécessaire : un tableau de tableaux de taille croissante.

2   Chaînes et chiffres

3   Saisie contrôlée

Question

1. définir une fonction read_bound_int telle que read_bound_int n lit sur l'entrée standard et retourne un entier compris strictement entre 0 et n. Lorsque la saisie n'est pas correcte, on redemande une entrée.
2. on se donne le type

   type play_or_quit = Quit | Play of int ;;
   

   Définir une fonction read_bound_int_or_q telle que read_bound_int_or_q n retourne ou bien Play i lorsque i est une valeur entière lue sur l'entrée standard comprise entre 0 et n ; ou bien Quit lorsque l'utilisateur a abandonné la saisie en tapant le caractère q.

4   Un ``chifoumi''

Question

1. définir une fonction chifoumi_compare telle que chifoumi_compare n1 n2 retourne -1 si n1 gagne sur n2, 0 si n1 est égal à n2 et 1 sinon.
2. définir la fonction chifoumi_game permettant à un humain de jouer au chifoumi contre la machine.
   • on pourra utiliser les fonctions de saisie de l'exercice préc'edent;
   • on pourra donner à la machine une stratégie stupide ; tirer un nombre au hasard (voir module Random).

5   Graphes abstraits

(* ========================================================================== *)
(* == Abstract data type for graphs: signature                             == *)
(* ========================================================================== *)


type t

(* `create()' creates a new empty graph                                       *)
val create: unit -> t 

(* `add_node g n' adds the node `n' tout the graph `g'.
   Does nothing if `n' is already a node of `g'                               *)
val add_node: t -> Node.t -> t  

(* `add_edge g n1 n2' adds the edge `(n1,n2)' to the graph `g'
   raise exception `Not_found' when `n1' or `n2' are not nodes of `g'         *)
val add_edge: t -> Node.t -> Node.t -> t 

(* `nodes_of g' give the list of nodes of graph `g'                           *)
val nodes_of: t -> Node.t list

(* `adj_of g n' returns the list of adjacents to `n' in `g'.
   raises `Not_found' when `n' is not a node in `g'.                          *)
val adj_of: t -> Node.t -> Node.t list

(* `has_adj g n1 n2' returns `true' iff `g' contains an edge from `n1' to `n2'*)
val has_edge: t -> Node.t -> Node.t -> bool

(* `eq g1 g2' returns true iff the two graphs are equals (ie. same set of nodes
   and, for each node, same set of adjacents)                                 *)
val eq: t -> t -> bool

(* `print g' prints to terminal a representation of the content of the `g'    *)
val print: t -> unit

Questions

1. donner une implantation de la signature ci-dessus
2. définir, en utilisant les fonctions du module défini ci-dessus, une fonction qui calcule la clôture réflexive d'un graphe.
3. compilez une petite application qui utilise ce module et cette fonction.

This document was translated from L^AT_EX by H^EV^EA.