Exercices

Exercices

Résolution de systèmes linéaires

Cet exercice reprend celui de résolution de systèmes linéaires présenté comme exercice du chapitre sur la programmation impérative (3).

En utilisant le module Printf, écrire une fonction affiche_systeme qui aligne les colonnes du système.


# type vect = float array 
 type mat = vect array 
 type syst = { m:mat ; v:vect } ;;
type vect = float array
type mat = vect array
type syst = { m: mat; v: vect }

# let affiche_systeme s =
   let w = Array.length s.m.(0) 
   and h = Array.length s.m in 
   let  c = h / 2 in 
     for i = 0 to h - 1 do 
       Printf.printf "| ";
       for j = 0 to w - 1 do 
         Printf.printf " %8.2f " s.m.(i).(j)
       done;
       Printf.printf " |";
       if i = c then Printf.printf " * " else Printf.printf "   ";
       Printf.printf "| x_%-2d |" i;
       if i = c then Printf.printf " = " else Printf.printf "   ";
       Printf.printf "| %8.2f |\n" s.v.(i)
   done;
   Printf.printf "\n" ;;
val affiche_systeme : syst -> unit = <fun>

Tester cette fonction sur les exemples donnés page ??.


# let ax3 = { m = [| [| 10.0  ;  7.0  ;  8.1  ;  7.2  |] 
                  ; [|  7.08 ;  5.04 ;  6.0  ;  5.0  |]
                  ; [|  8.0  ;  5.98 ;  9.89 ;  9.0  |]
                  ; [|  6.99 ;  4.99 ;  9.0  ;  9.98 |] |] ;
             v =    [| 32.0  ; 23.0  ; 33.0 ; 31.0 |]   } ;;
val ax3 : syst =
  {m=
    [|[|10; 7; 8.1; 7.2|]; [|7.08; 5.04; 6; 5|]; [|8; 5.98; 9.89; ...|];
      ...|];
   v=...}
# affiche_systeme ax3 ;;
|     10.00      7.00      8.10      7.20  |   | x_0  |   |    32.00 |
|      7.08      5.04      6.00      5.00  |   | x_1  |   |    23.00 |
|      8.00      5.98      9.89      9.00  | * | x_2  | = |    33.00 |
|      6.99      4.99      9.00      9.98  |   | x_3  |   |    31.00 |

- : unit = ()

Recherche de nombres premiers

Le crible d'Eratosthène est un algorithme simple à programmer pour la recherche de nombres premiers dans un intervalle d'entiers donné dont la borne inférieure doit être un nombre premier. La méthode est la suivante :

Énumérer, dans une liste, toutes les valeurs de l'intervalle.
Ôter de la liste toutes les valeurs multiples du premier élément.
Ôter de la liste et conserver ce premier élément ;
Recommencer en 2. tant que la liste n'est pas vide.

Voici les étapes de réalisation d'un programme qui implante cet algorithme :

Écrire une fonction interval qui construit un intervalle d'entiers représenté sous la forme d'une liste.
On reprend la fonction interval des exercices du chapitre précédent.
```
# let interval order next a b = 
   let rec aux a = 
     if not (order a b) then [a] else  a :: aux  (next a) 
   in aux a ;;
val interval : ('a -> 'b -> bool) -> ('a -> 'a) -> 'a -> 'b -> 'a list =
  <fun>
```
Écrire la fonction eras qui calcule les nombres premiers d'un intervalle d'entiers commençant à 2 selon l'algorithme du crible d'Eratosthène.
```
# let rec eras l  = match l with 
   [] -> []
 | p::q -> p :: (eras (List.filter (fun x -> x mod p <> 0) q)) ;;
val eras : int list -> int list = <fun>
```
Écrire une fonction era_go qui prend un entier et retourne la liste de tous les nombres premiers plus petits que cet entier.
```
# let era_go n = eras (interval (<) (fun x -> x + 1) 2 n) ;;
val era_go : int -> int list = <fun>
```

On cherche à écrire un exécutable premiers que l'on lancera en tapant la commande premiers n, où n est un entier. Cet exécutable affichera les nombres premiers plus petits que n. Pour cela il faut utiliser le module Sys et regarder s'il y a un paramètre passé. Fichier principal premiers.ml :


# let usage () = Printf.printf "Usage: premiers n\n";;
val usage : unit -> unit = <fun>

# let main () = 
   if Array.length (Sys.argv) < 2 then usage()
   else 
     let n = int_of_string Sys.argv.(1) in 
     if n < 2 then usage()
     else 
       let r = era_go n in 
       List.iter (fun x -> Printf.printf "%d " x) r;
       Printf.printf "\n" ;;
val main : unit -> unit = <fun>


main() ;;

Construction de l'exécutable :

$ ocamlc -o premiers premiers.ml

$ ocamlopt -o premiers premiers.ml

Test de l'exécutable :

$ premiers 
Usage: premiers n
$ premiers 50
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 
$ premiers 100
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97

Affichage de bitmaps

Les bitmaps sauvegardés comme color array array sont volumineux. Comme les 24 bits de couleur sont rarement utilisés, il est possible alors de coder un bitmap de manière plus légère. Pour cela on analysera le nombre de couleurs d'un bitmap. Si ce nombre est petit (par exemple inférieur à 256) on pourra coder chaque pixel sur 1 octet, représentant le numéro de la couleur dans une table des couleurs de ce bitmap.

Écrire une fonction analyse_couleurs explorant une valeur de type color array array et qui retourne la liste de toutes les couleurs rencontrées dans ce tableau de couleurs.


# let analyse_couleurs c = 
   let l = ref [] in 
   for i = 0 to (Array.length c) - 1 do 
     for j = 0 to (Array.length c.(0)) -1  do 
       if not(List.mem c.(i).(j) !l) then l:= c.(i).(j) :: !l
     done ;
   done ;
   List.rev !l ;;
val analyse_couleurs : 'a array array -> 'a list = <fun>

À partir de cette liste, construire une table de correspondance des couleurs. On prendra un vecteur de couleurs. L'indice du tableau correspondra au numéro d'ordre de la couleur, son contenu à la couleur. Écrire la fonction trouve_indice qui retourne l'indice d'une valeur stockée dans un tableau.
```
# let construire_table l = Array.of_list l ;;
val construire_table : 'a list -> 'a array = <fun>

# exception Find of int;;
exception Find of int

# let trouve_indice c t = 
   let aux () = 
     for i=0 to Array.length t do 
       if c = t.(i) then raise (Find i)
     done ;
     raise Not_found
   in 
     try aux () with Find i -> i ;;
val trouve_indice : 'a -> 'a array -> int = <fun>
```

À partir de cette table, écrire une fonction de conversion, encode, d'un color array array en string. Chaque pixel est alors représenté par un caractère.


# let encode caa t =
   if Array.length t > 255 then failwith "trop de couleurs (> 255)"
   else  
     let h = Array.length caa 
     and w = Array.length caa.(0) in 
     let s = String.create (h * w)  in 
     let ns = ref 0 in 
     for i = 0 to h-1 do 
       for j = 0 to w-1 do 
         let ci = trouve_indice caa.(i).(j) t in 
         s.[!ns] <- char_of_int ci ;
         incr ns
       done
     done ;
     s ;;
val encode : 'a array array -> 'a array -> string = <fun>

Définir un type image_tdc comportant une table de correspondance des couleurs et un vecteur de chaînes permettant de coder de manière plus petite un bitmap (ou tableau de couleurs).
```
# type image_tdc = { tdc : Graphics.color array; image : string; 
                    largeur : int; hauteur : int};;
type image_tdc =
  { tdc: Graphics.color array;
    image: string;
    largeur: int;
    hauteur: int }
```

Écrire la fonction to_image_tdc de conversion d'un color array array vers ce type.


# let to_image_tdc caa = 
   let t = construire_table (analyse_couleurs caa)  in 
   let s = encode caa t in 
     { tdc = t; image = s; 
       largeur = Array.length caa.(0); hauteur = Array.length caa} ;;
val to_image_tdc : Graphics.color array array -> image_tdc = <fun>

Écrire la fonction sauve_image_tdc de sauvegarde de ces valeurs vers un fichier.
```
# let sauve_image_tdc im nom  = 
   let oc = open_out nom in 
   Marshal.to_channel oc im [] ;;
val sauve_image_tdc : 'a -> string -> unit = <fun>
```
Comparer la taille du fichier obtenu par rapport à la sauvegarde du tableau de couleurs équivalent. Elle est plus petite, d'un facteur 4!!!

Écrire la fonction from_image_tdc de conversion inverse.


# let from_image_tdc im = 
   let r = Array.create_matrix im.hauteur im.largeur Graphics.black in 
   let ns = ref 0 in 
   for i = 0 to im.hauteur -1 do 
     for j = 0 to im.largeur -1 do 
       r.(i).(j) <- im.tdc.(int_of_char  im.image.[!ns]) ;
       incr ns
     done
   done ;
   r ;;
val from_image_tdc : image_tdc -> Graphics.color array array = <fun>

L'utiliser pour visualiser une image sauvegardée dans un fichier sous forme d'une valeur de type bitmap_tdc.


# let visu name  = 
   let ic = open_in name in 
   let im = Marshal.from_channel ic in 
   let caa = from_image_tdc im in 
   let b = Graphics.make_image caa in 
   let size = (string_of_int (Array.length caa.(0))) 
              ^ "x" ^ (string_of_int (Array.length caa)) in
   Graphics.open_graph (":0 " ^ size) ;
   Graphics.draw_image b 0 0 ;
   b ;;
val visu : string -> Graphics.image = <fun>