# (* fabriquons une fonction qui calcule 2^n,
comme je suis deforme, je l'appelle exp *)
let rec exp = function
| 0 -> 1
| n -> 2*(exp (n-1))
;;
val exp : int -> int = <fun>
# exp 3;;
- : int = 8
# exp 64;;
- : int = 0
Conclusion: 2^64 vaut 0.
Reponse 2 :
Une rapide demonstration par recurrence montre que pour tout nombre entier n superieur a 64, 2^n vaut 0.
Reponse 3 :
%ocaml
[..]
# let rec fibo = function
| 0 -> 1
| 1 -> 1
| k -> (fibo (k-1)) + (fibo (k-2))
;;
val fibo : int -> int = <fun>
# fibo 1;;
- : int = 1
# fibo 10;;
- : int = 89
# fibo 100;;
- : int = 277887173
En un temps certain
Remarque : une fonction de complexité linéaire en l'entrée qui mettrait le meme temps que fibo sur l'entree 1 mettra egalement le meme temps certain sur l'entree 277887173.
Donc les fonctions a complexité linéaire sont à proscrire ?
[^] # Re: exponentiel => indecidable
Posté par 태 (site web personnel) . En réponse au journal couverture de code. Évalué à 1.
%ocaml
Objective Caml version 3.08.2
# (* fabriquons une fonction qui calcule 2^n,
comme je suis deforme, je l'appelle exp *)
let rec exp = function
| 0 -> 1
| n -> 2*(exp (n-1))
;;
val exp : int -> int = <fun>
# exp 3;;
- : int = 8
# exp 64;;
- : int = 0
Conclusion: 2^64 vaut 0.
Reponse 2 :
Une rapide demonstration par recurrence montre que pour tout nombre entier n superieur a 64, 2^n vaut 0.
Reponse 3 :
%ocaml
[..]
# let rec fibo = function
| 0 -> 1
| 1 -> 1
| k -> (fibo (k-1)) + (fibo (k-2))
;;
val fibo : int -> int = <fun>
# fibo 1;;
- : int = 1
# fibo 10;;
- : int = 89
# fibo 100;;
- : int = 277887173
En un temps certain
Remarque : une fonction de complexité linéaire en l'entrée qui mettrait le meme temps que fibo sur l'entree 1 mettra egalement le meme temps certain sur l'entree 277887173.
Donc les fonctions a complexité linéaire sont à proscrire ?