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.

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 (13:19) From: Laurent Chéno Subject: Re: help an o'caml beginner
Le 26/07/00 à 11:51, beppu@lineo.com (John BEPPU) écrivait :

> Hi.

--- Please excuse my poor english ---
>
> Next, I wrote an iterative C version.
>
>     #include <stdio.h>
>
>     int fib(int n)
>     {
>         int val = 2;
>         int n1 = 2;
>         int n2 = 1;
>         int i;
>         if (n < 2)
>             return n;
>
>         for (i = 2; i < n; i++) {
>             val = n2 + n1;
>             n2 = n1;
>             n1 = val;
>         }
>         return val;
>     }
>
>     int main(char *argc, char **argv)
>     {
>         printf("%d\n", fib(atoi(argv[1])));
>         return 0;
>     }
>
> This was much faster than any of the recursive versions, because it
> doesn't have to recompute the same values over and over again.
>

the basic translation can be for example :

let fib n =
let val = ref 2
and n1  = ref 2
and n2  = ref 1
in
if n < 2 then n
else for i = 2 to n - 1 do
val := !n1 + !n2 ;
n2 := !n1 ;
n1 := !val
done ;
!val ;;

But I prefer a recursive and efficient version like this :

let fib n =
let rec fibaux n p q =
if n = 0 then p
else fibaux (n - 1) q (p + q)
in
fibaux n 0 1 ;;

this is a terminal recursion : try it !

--
Laurent Chéno                   Paris (France)
<http://pauillac.inria.fr/~cheno/>
--