Accueil     À propos     Téléchargement     Ressources     Contactez-nous

Ce site est rarement mis à jour. Pour les informations les plus récentes, rendez-vous sur le nouveau site OCaml à l'adresse ocaml.org.

Browse thread
help an o'caml beginner
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
 Date: 2000-07-28 (00:03) From: Michel Quercia Subject: Re: help an o'caml beginner
```Le Wed, 26 Jul 2000, John BEPPU a écrit :
> I tried out the recursive fibonacci number program
> ...
> Next, I tried to fumble my way through making an O'Caml version of
> this iterative algorithm, but I failed due to my lack of knowledge
> about this language.

Below are three translations of your iterative C code :

------------------------------------------------------------
(* iterative Caml code *)
let fib(n) =
let a = ref(1) and b = ref(1) in
for i=2 to n do
let x = !a + !b in
a := !b;
b := x
done;
!b
;;

-------------------------------------------------------------
(* recursive Caml code, fib2(n) returns (fib(n-1),fib(n)) *)
let rec fib2(n) =
if n <= 1 then (n,1)
else let (a,b) = fib2(n-1) in (b,a+b)
;;

let fib(n) = let (_,x) = fib2(n) in x;;

-------------------------------------------------------------
(* tail-recursive Caml code, fib3 a b n computes a*fib(n) + b*fib(n-1) *)
let rec fib3 a b n = if n <= 1 then a + b*n else fib3 (a+b) a (n-1);;
let fib(n) = fib3 1 0 n;;
--------------------------------------------------------

Note that there are also divide-and-conquer algorithms for computing Fibonacci
numbers that achieve logarithmic computing time with respect to the input.

> I wish the tutorial were available in HTML.

There is atutorial included in the html documentation.

Regards,
--
Michel Quercia
23 rue de Montchapet, 21000 Dijon
http://pauillac.inria.fr/~quercia
mailto:quercia@cal.enst.fr

```