Version OCaml avec memoization
Allez hop, je suis en forme! Pour rigoler, une version avec mémoization (sale, en impératif, tout ça tout ça !)
Code:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63
|
type tree = subtree list
and subtree = { tag : int;
son : tree}
let memo = ref (Array.make_matrix 0 0 None)
let init_memo n =
memo := Array.make_matrix (n + 1) (n + 1) None
let extract_memo n cut =
!memo.(n).(cut)
let insert_memo n cut l =
!memo.(n).(cut) <- Some l
let rec build_tree n cut =
if (cut = 0) then []
else
match extract_memo n cut with
| None ->
let sub_tree = build_sub_tree n cut in
let res = sub_tree :: (build_tree n (cut - 1)) in
insert_memo n cut res;
res
| Some r -> r
and build_sub_tree n cut =
if n = cut then
{tag = cut; son = []}
else
let n' = n - cut in
{ tag = cut;
son = build_tree n' (min cut n') }
let build_all_tree n = build_tree n n
let print_list l =
let rec print_interieure fst = function
[] -> ()
| t::q ->
if not fst then print_string ", ";
print_int t;
print_interieure false q in
print_string "[";
print_interieure true l;
print_string "]\n"
let count = ref 0
let rec print_subtree l st =
if st.son = [] then (print_list (st.tag :: l); incr count)
else print_tree (st.tag :: l) st.son
and print_tree l = function
| [] -> ()
| st :: q -> print_subtree l st; print_tree l q
let _ = init_memo (int_of_string Sys.argv.(1))
let t = build_all_tree (int_of_string Sys.argv.(1))
(*let _ = print_tree [] t
let _ = print_int !count
*) |
Toujours sur la même bécane, la génération de l'arbre prend 0,26 secondes pour n = .... 1000 :)
Après la question qui se pose c'est : qu'est ce que veut dire "déterminer" dans le défi de base.
Allez, il est 2h du mat par chez moi, je file au lit