let ht = Hashtbl.create 100;; (* Fibonacci com memoização com base numa tabela de hash memoização: capacitar uma função com uma memória dos calculos que já fez. Nunca calcula duas vezes o mesmo valor. Se já foi calculado, devolve directamente o valor previamente calculado. Se não foi calculado, calcula-se, grava-se na "memória" e devolve-se o valor propriamente dito *) let rec fibt n = if n<0 then failwith "Input Negativo" else try Hashtbl.find ht n with Not_found -> if n <= 1 then (Hashtbl.add ht n 1; 1) else let valor = fibt (n-1) + fibt (n-2) in (Hashtbl.add ht n valor;valor) let () = Printf.printf "%d\n" (let x = int_of_string Sys.argv.(1) in try fibt x with Failure _ -> fibt (- x)) (* $ time fib_memo 100010 4039261411255876802 real 0m0.052s user 0m0.039s sys 0m0.009s $ time fib_memo 10000 -83367563645688771 real 0m0.013s user 0m0.005s sys 0m0.006s Temos aqui um belo integer overflow! isso deixa também suspeitar (com razão) que o resultado anterior está errado! *)
This document was generated using caml2html