Exercises

Resolution of Linear Systems

1. By using the Printf module, write a function print_system that aligns the columns of the system.

   
   # 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>
   
   
   

   
   
   
2. Test this function on the examples given on 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 = ()
   
   
   

Search for Prime Numbers

1. Enumerate, in a list, all the values on the range.
2. Remove from the list all the values that are multiples of the first element.
3. Remove this first element from the list, and keep it as a prime.
4. Restart at step 2 as long as the list is not empty.

1. Write a function range that builds a range of integers represented in the form of a list. 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>
   
   
   

   
   
   
2. Write a function eras that calculates the prime numbers on a range of integers starting with 2, according to the algorithm of the Sieve of Eratosthenes.

   
   # 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>
   
   
   

   
   
   Write a function era_go that takes an integer and returns a list of all the prime numbers smaller than this integer.

   
   # let era_go n = eras (interval (<) (fun x -> x + 1) 2 n) ;;
   val era_go : int -> int list = <fun>
   
   
   

   
   
   
3. We want to write an executable primes that one will launch by typing the command primes n, where n is an integer. This executable will print the prime numbers smaller than n. For this we must use the Sys module and check whether a parameter was passed. 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
   

   ou

   $ 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 
   

Displaying Bitmaps

1. Write a function analyze_colors exploring a value of type color array array and that returns a list of all the colors found in this image.

   
   # 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>
   
   
   

   
   
   
2. From this list, construct a palette. We will take a vector of colors. The index in the table will correspond to the order of the color, and the contents are the color itself. Write the function find_index that returns the index of a value stored in the array.

   
   # 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>
   
   
   

   
   
   
3. From this table, write a conversion function, encode, that goes from a color array array to a string. Each pixel is thus represented by a character.

   
   # 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>
   
   
   

   
   
   
4. Define a type image_tdc comprising a table that matches colors to a vector of strings, allowing the encoding of a bitmap (or color array) using a smaller method.

   
   # 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 }
   
   
   

   
   
   
5. Write the function to_image_tdc to convert a color array array to this 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>
   
   
   

   
   
   
6. Write the function save_image_tdc to save the values to a file.

   
   # 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>
   
   
   

   
   
   
7. Compare the size of the file obtained with the saved version of an equivalent palette. Elle est plus petite, d'un facteur 4!!!
   
   
8. Write the function from_image_tdc to do the reverse conversion.

   
   # 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>
   
   
   

   
   
   
9. Use it to display an image saved in a file. The file will be in the form of a value of 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 (" " ^ size) ;
      Graphics.draw_image b 0 0 ;
      b ;;
   val visu : string -> Graphics.image = <fun>