(* Compter le nombre de façons de construire un mur de briques de longueur 32 et de hauteur 10, avec des briques de longueur 2 et 3 *) let width = 32 let height = 10 let add2 r = (r lsl 2) lor 0b10 let add3 r = (r lsl 3) lor 0b100 let rows = ref [] let rec fill w r = if w = width then rows := r :: !rows else if w < width then begin fill (w + 2) (add2 r); fill (w + 3) (add3 r) end let () = fill 2 0; fill 3 0 let () = Printf.printf "%d rangées\n" (List.length !rows) let rec sum f = function [] -> 0 x :: r -> f x + sum f r let size = 1 lsl 16 let table = Array.make size [] let hash (x,y) = x lxor (x lsr 16) + 5003 * y let bucket k = (hash k) land (size - 1) let add k v = let i = bucket k in table.(i) <- (k, v) :: table.(i) let find k = let rec lookup = function [] -> raise Not_found (k', v) :: r -> if k' = k then v else lookup r in lookup table.(bucket k) let rec count r h = if h = 1 then 1 else sum (fun r' -> if r land r' = 0 then memo_count r' (h-1) else 0) !rows and memo_count r h = try find (r,h) with Not_found -> let v = count r h in add (r,h) v; v let sol = sum (fun r -> count r height) !rows let () = Printf.printf "solution = %d\n" sol (* Local Variables: compile-command: "ocamlopt -o wall wall.ml && time ./wall" End: *)
This document was generated using caml2html