Allez hop, je suis en forme! Pour rigoler, une version avec mémoization (sale, en impératif, tout ça tout ça !)
Toujours sur la même bécane, la génération de l'arbre prend 0,26 secondes pour n = .... 1000
Code : Sélectionner tout - Visualiser dans une fenêtre à part
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 *)
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
Partager