Muestro un ejemplo en C++ que devuelve la item n-ésimo de la sucesión de Fibonacci. Es un programa de línea de comandos que tiene 4 opciones: -v para el modo verbose, -h para la ayuda, -t para imprimir el tiempo que tarda en segundos y -n para calcular el n-ésimo número de Fibonacci.
Ejemplo de uso:
| $ ./fibo -vtn 15 #imprime los 15 primeros coeficientes |
El programa usa un algoritmo de tipo iterativo (los más sencillitos), y tiene una complejidad de O(n).
El código es el siguiente:
______________________________________________________
/* Fecha: 01/09/09 Programa: retorna la suma n-ésima de la sucesión de fibonacci */ #include <iostream> #include <string> #include <sstream> #include <time.h> #include <unistd.h> using namespace std; int main (int argc, char **argv) { /* variables */ double sum; double fibo_aux[2]; fibo_aux[0] = 0; fibo_aux[1] = 1; unsigned long num = -1; char oc; bool do_time = false, do_verbose = false, do_help = false; while ((oc = getopt(argc, argv, ":vn:ht")) != -1) { switch (oc) { case 'v': do_verbose = true; break; case 'h': cout << "./fibo [-options] [num]" << endl;
cout << "Options: \n\t -v : modo verbose \n\t
-h: esta ayuda\n\t -t : imprime el tiempo que tarda \n\t -n
<numero>: calcula fibonacci de orden <numero>" << endl; do_help = true; case 't': do_time = true; break; case 'n': stringstream buf(optarg); buf >> num; break; } } if (!do_help) { //Por defecto calcula los 10 primeros
//números de la sucesión de fibonacci if (num == -1) num = 10; long t1 = clock(); if (do_verbose) { cout << "f[0] = " << fibo_aux[0] << endl; cout << "f[1] = " << fibo_aux[1] << endl; } for (int i = 0; i <= num; i++) { sum = fibo_aux[0] + fibo_aux[1]; if ((do_verbose==1) && (i > 1)) { cout << "f[" << i << "] = " <<
fibo_aux[0] << endl; } if (num != i) { fibo_aux[0] = fibo_aux[1]; fibo_aux[1] = sum; } } long t2 = clock(); cout << "Fibonacci(" << num << ") = "
<< fibo_aux[0] << endl; if (do_time) { cout << "Tiempo total: " <<
(t2-t1)/(double)CLOCKS_PER_SEC << " segundos" << endl; } } return 0; }
_____________________________________________________

0 comentarios:
Publicar un comentario en la entrada