(* * QUESTION 1 *) let rec bad_fibonnaci a b = fun | 0 -> a | 1 -> b | n -> (bad_fibonnaci a b (n-1)) + (bad_fibonnaci a b (n-2));; bad_fibonnaci 1 1 15;; (* * QUESTION 2 *) type 'a Result = None | Value of 'a;; let results = make_vect 1000 None;; let rec mem_fibonnaci a b x = match results.(x) with | Value(r) -> r | None -> let r = match x with | 0 -> a | 1 -> b | n -> (mem_fibonnaci a b (n-1)) + (mem_fibonnaci a b (n-2)) in results.(x) <- Value(r); r;; mem_fibonnaci 1 1 35;; (* * QUESTION 3 *) let mineur n lst = let tbl = make_vect (n+1) None in tbl.(0) <- Value([]); let rec aux = function [] -> () | h::t -> for i = (n-h) downto 0 do match tbl.(i) with | None -> () | Value(v) -> tbl.(i+h) <- Value(h::v) done; aux t in aux lst; let i = ref n in while tbl.(!i) = None do decr i done; match tbl.(!i) with | None -> failwith "should not happen" | Value(v) -> !i,v;; mineur 21 [2;3;4;6;7];; (* * QUESTION 5 *) let rec fold f i = function | [] -> i | h::t -> fold f (f i h) t;; let paquebot lst = let n = fold (prefix +) 0 lst in let g,l = mineur (n/2) lst in n-2*g, l;; paquebot [1;2;3;4;5;6;7;8;9];; (* * QUESTION 6 *) type Event = Cloud of int * float | Build of int;; let altitude = function | Cloud(a,_) -> a | Build(a) -> a;; let superman e a lst = let i = ref 0 and l = ref lst and a_max = fold max a (map (fun x -> altitude (snd x) + 2) lst) in let positions = make_matrix 2 (a_max+1) None in positions.(0).(a) <- Value e; let check_life () = let b = ref false in for j = 0 to a_max do if positions.(!i mod 2).(j) <> None then b := true; done; !b in let reset () = for j = 0 to a_max do positions.((!i + 1) mod 2).(j) <- None done; in let update i j e = if j >= 0 && j <= a_max && e >= 0. then match positions.(i).(j) with | None -> positions.(i).(j) <- Value(e) | Value(e') when e' < e -> positions.(i).(j) <- Value(e) | _ -> () in let rec update_events () = match !l with | [] -> () | (x, ev)::t when x <> !i -> () | (_, Cloud(a, s))::t -> ( match positions.(!i mod 2).(a) with | None -> () | Value(e) -> positions.(!i mod 2).(a) <- Value(e+.s) ) | (_, Build(a))::t -> for j = 0 to a do positions.(!i mod 2).(j) <- None done in let run_step () = reset(); for j = 0 to a_max do match positions.(!i mod 2).(j) with | None -> () | Value(e) -> update ((!i+1) mod 2) (j+1) (e-.1.); update ((!i+1) mod 2) (j-1) (e); done; incr i; update_events (); in while check_life() do run_step() done; !i-1;; superman 10. 10 [];;