(*********************) (* Correction du TP4 *) (*********************) (**** Question 1 ****) (* Premiere fonction : bug car le deuxieme filtrage n'est *) (* jamais regardé (le premier filtrage prend tout) *) (* 2eme fonction : il manque le cas x=1 *) (**** Question 2 ****) let rec len = function | [] -> 0 | t::q -> 1+len q;; len [1;2;3;4];; (**** Question 3 ****) let rec list_max = function | [x] -> x | t::q -> max t (list_max q) | [] -> failwith "Liste vide!";; list_max [2; 4; 1; 6; -1];; (**** Question 4 ****) let rec map f = function | [] -> [] | t::q -> (f t) :: (map f q);; map sqrt [0.; 1.; 2.; 3.; 4.];; (**** Question 5 ****) let vect_max v = let rec aux j = function | 0 -> v.(0) | i -> max v.(i) (aux (i-1)) in aux (vect_length v - 1);; vect_max [|3; 5; 7; 1; 9; 2; -5|];; (**** Question 6 ****) let swap_vect v i j = let tmp=v.(i) in v.(i)<-v.(j); v.(j)<-tmp;; let permute v = let rec aux i = if i>0 then ( swap_vect v i (random__int (i+1)); aux (i-1); ) in aux (vect_length v - 1); v;; permute [|1;2;3;4;5;6;7;8;9;10|];; (**** Question 7 ****) let rec insert_in x = function | [] -> [x] | t::q -> if x [] | t::q -> insert_in t (insert_sort q);; insert_sort [2;1;6;-2;5;2;5;-1;4;2;0];; (**** Question 8 ****) let rec u = function | 0 -> 1.0 | n -> u (n-1) /. v (n-1) and v = function | 0 -> 1.0 | n -> u (n-1) +. v (n-1);; (* ou encore *) let rec suites = function | 0 -> (1.0, 1.0) | n -> let (x,y) = suites (n-1) in (x/.y , x+. y);; u 20;; suites 20;; (**** Question 9 ****) let rec pgcd i j = if i=0 then j else if j=0 then i else match (i mod 2, j mod 2) with | (0,0) -> 2*pgcd (i/2) (j/2) | (1,0) -> pgcd i (j/2) | (0,1) -> pgcd (i/2) j | (1,1) -> pgcd (abs (j-i)) (min (abs i) (abs j)) | _ -> failwith "Bad argument";; pgcd (127*2329182) (127*7271827);; (**** Question 10 ****) type arbre = | vide | nd of int*arbre*arbre;; let rec search x = function | vide -> false | nd(y,g,d) -> if x=y then true else if x nd(x,vide,vide) | nd(y,g,d) -> if x () | nd(x,g,d) -> affiche g; print_int x; print_string ","; affiche d;; let rec arbre_of_list = function | [] -> vide | t::q -> insert t (arbre_of_list q);; let trie_list l = affiche (arbre_of_list l);; trie_list [2;5;3;2;5;3;2;1;0;7];; (**** Question 11 ****) #open "graphics";; open_graph "800x600+0+0";; for i=0 to 255 do for j=0 to 255 do set_color (rgb i 0 j); plot i j; done; done;; let dir = ref (0,2);; let avance() = let (x,y) = current_point() and (dx,dy) = !dir in lineto (x+dx) (y+dy);; let gauche() = let (dx,dy) = !dir in dir := (-dy,dx);; let droite() = let (dx,dy) = !dir in dir := (dy,-dx);; let rec dragon n b = if n=0 then avance() else ( dragon (n-1) true; if b then gauche() else droite(); dragon (n-1) false; );; let joli () = clear_graph(); moveto 300 200; dir := (1,0); dragon 18 true;; joli();;