Fibonacci en C

Más ejercicios resueltos

Si deseas revisar más ejercicios resueltos, haz click en el siguiente botón. 

A continuación presentamos 5 soluciones diferentes al problema de la la serie de Fibonacci en ANSI C. Si deseas ver el enunciado del problema, haz click en el siguiente enlace. Si deseas entender el diseño algorítmico detrás de las soluciones presentadas, te invitamos a visitar el siguiente enlace.

A continuación presentaremos la implementación de las 5 soluciones propuestas. En primer lugar revisaremos las soluciones usando estructuras algorítmicas iterativas, posteriormente presentamos alternativas de solución usando el paradigma de programación modular. Finalmente, analizamos el problema desde la perspectiva de la programación dinámica.

Versión usando la instrucción while

La primera versión que presentaremos será diseñada usando una estructura algorítmica iterativa con entrada controlada. La analizaremos paso a paso.

Lectura de datos

Y empezamos con el primer paso, la lectura de los datos de entrada. Realizamos la lectura del valor de n.  La lectura de datos en ANSI C la realizamos con la función \texttt{scanf}. Recuerde que para poder usar esta función, se debe incluir el archivo de cabecera \texttt{stdio.h} (Standard Input Output). Usaremos la variable \texttt{n} para leer el valor de n. Esta variable representará la cantidad de términos que debemos imprimir. Será fundamental para el control de flujo de la iteración.

#include<stdio.h>

int main() {
    int n;
    printf("Ingrese número de términos: ");
    scanf("%d", &n);

    return 0;
} 

Validación de datos de entrada

El segundo paso corresponde con la validación de los datos de entrada, para esto usamos la estructura selectiva doble, la cual se implementa en ANSI C a través de la instrucción \texttt{if-else}. Para que podamos realizar la impresión de los términos, pues la cantidad deberá ser mayor que cero. En caso que esto no se cumpla, emitiremos un mensaje informativo al usuario.

#include<stdio.h>

int main() {
    int n;
    printf("Ingrese número de términos: ");
    scanf("%d", &n);

    if (n <= 0)
        printf("Debe ingresar un número mayor que cero");
    else {

    }
    return 0;
} 

Impresión de los dos primeros números

Tal como menciona el enunciado, los dos primeros  términos de la serie son fijos, por lo tanto usamos una selectiva simple para imprimirlos. En realidad, la primera selectiva (con la condición \texttt{n>=1}) la podemos omitir pues si es que el flujo se dirige hacia el bloque \texttt{else} es por que \texttt{n>0}, entonces siempre se cumplirá que \texttt{n>=1}

#include<stdio.h>

int main() {
    int n;
    printf("Ingrese número de términos: ");
    scanf("%d", &n);

    if (n <= 0)
        printf("Debe ingresar un número mayor que cero");
    else {
        if (n >= 1)
            printf("0 ");
        if (n >= 2)
            printf("1 ");
    }
    return 0;
} 

Control de flujo para los demás términos de la serie

A partir del tercer término, debemos calcular los mismos usando los dos términos anteriores. El cálculo de términos se repetirá tantas veces como términos falten imprimir. ¿Cuántos términos faltan imprimir? Pues deseamos imprimir n términos y ya se han impreso 2 pues faltan imprimir n-2 términos. Estos son los términos del 3 hasta el n¿Cómo repetimos un cálculo varias veces? Pues a través de una estructura algorítmica iterativa. Por lo tanto controlaremos una iteración para que el flujo se realice n-2 veces.  

Procederemos ahora a realizar el control de flujo de la iteración, usaremos para ello un ciclo iterativo con entrada controlada. Usaremos un control por variable el cual se configura usando los siguientes pasos:

  1. Inicializamos la variable de control. En este caso hemos definido la variable de control \texttt{i} y la hemos inicializado con el valor de \texttt{3}. La inicializamos con este valor pues queremos recorrer el rango [3..n]
  2. Controlamos el flujo usando la variable de control. Como queremos que se impriman \texttt{n-2} términos de la serie, la variable de control \texttt{i} debe actualizarse con  \texttt{n-2} valores, desde \texttt{3}, su valor inicial, hasta \texttt{n}, su valor final. Por lo tanto la condición de repetición será \texttt{i<=n}. Mientras esto sea verdad, se seguirá repitiendo. 
  3. Actualizamos el valor de la variable de control. Debemos cambiar la variable de control para que el ciclo iterativo no se haga infinito. Debemos garantizar que en algún momento en el tiempo, la condición se evalúe como falsa. Por lo tanto debemos incrementar \texttt{i} para que llegue a ser mayor que \texttt{n} y el ciclo termine. Por condiciones del problema, se incrementará en 1 a esta variable.
#include<stdio.h>

int main() {
    int n;
    printf("Ingrese número de términos: ");
    scanf("%d", &n);

    if (n <= 0)
        printf("Debe ingresar un número mayor que cero");
    else {
        if (n >= 1)
            printf("0 ");
        if (n >= 2)
            printf("1 ");
        int i = 3;
        while (i <= n) {

            i++;
        }
    }
    return 0;
} 

Cálculo del término actual de la serie

Vamos a proceder con el cálculo del término actual de la serie y su correspondiente impresión. ¿Donde realizamos el cálculo y la impresión? Dentro de la iteración. Esto debido a que mientras se va a calculando se debe imprimir. ¿Cómo hacemos el cálculo? Pues, para eso se requiere de los dos términos anteriores. Para dicho fin, hemos creado las variables \texttt{anterior}\texttt{actual}. Estas variables las hemos definido como \texttt{long}. El motivo de esto radica en que los términos de la serie de Fibonacci suelen crecer en magnitud muy rápidamente.

 La variable \texttt{anterior}, como su nombre lo indica, contiene el valor anterior de la serie de Fibonnaci en relación al termino actual que deseamos calcular. Lo hemos inicializado con el valor de \texttt{0} que corresponde con el primer término de la serie de Fibonacci. La variable \texttt{actual} contiene el valor actual del término que estamos calculando de la serie de Fibonacci. Lo hemos inicializado con el valor de \texttt{1} que corresponde con el segundo término de la serie de Fibonacci. 

Como podrán notar, las variables han sido inicializadas considerando que el término actual es el número 2. Pero, ¿por qué los inicializamos con esos valores? Esto se ha realizado así, pues vamos a calcular de forma repetitiva a partir del tercer termino. La idea es que dentro de la iteración, estos valores se actualice.

Vamos a enfocarnos en este paso en el cálculo o actualización del valor actual del término. Para obtener el valor actual, hemos actualizado el valor de la variable \texttt{actual} con el valor de \texttt{actual+anterior}. Lo que estamos haciendo en realidad es actualizar el valor actual con el valor de los dos términos anteriores. El único detalle es que seguimos utilizando esas mismas variables. No hemos usado variables adicionales.

  • Cuando \texttt{i} tiene el valor de \texttt{3}\texttt{anterior} contiene el valor de \texttt{0}\texttt{actual} el valor de \texttt{1}. Al realizar esta operación \texttt{actual} contendría ahora el valor de \texttt{1}
  • Cuando \texttt{i} tiene el valor de \texttt{4}\texttt{anterior} contendrá el valor de \texttt{1}\texttt{actual} el valor de \texttt{1}. Al realizar la  operación de actualización  \texttt{actual} contendrá el valor de \texttt{2}
  • Cuando \texttt{i} tiene el valor de \texttt{5}\texttt{anterior} contendrá el valor de \texttt{1}\texttt{actual} el valor de \texttt{2}. Al realizar la  operación de actualización  \texttt{actual} contendrá el valor de \texttt{3}.
  • Cuando \texttt{i} tiene el valor de \texttt{6}\texttt{anterior} contendrá el valor de \texttt{2}\texttt{actual} el valor de \texttt{3}. Al realizar la  operación de actualización  \texttt{actual} contendrá el valor de \texttt{5}.
#include<stdio.h>

int main() {
    int n;
    printf("Ingrese número de términos: ");
    scanf("%d", &n);

    if (n <= 0)
        printf("Debe ingresar un número mayor que cero");
    else {
        if (n >= 1)
            printf("0 ");
        if (n >= 2)
            printf("1 ");
        long anterior = 0;
        long actual = 1;
        int i = 3;
        while (i <= n) {
            actual = actual + anterior;
            printf("%ld ", actual);
            i++;
        }
    }
    return 0;
} 

Actualización de las variables

El último paso es actualizar la variable \texttt{anterior}. La variable se debe actualizar con el valor de la serie de Fibonacci anterior. Por lo tanto debe actualizarse con el valor de \texttt{actual} antes que se modifique. Pero, ¿cúando hago la actualización? Si la hago antes de actualizar \texttt{actual}, luego perderé el valor de esta variable y fallará el cálculo del término actual. Si lo hago después de actulizar \texttt{actual}, ya no podré actualizar \texttt{anterior} con el valor actual anterior pues justamente acaba de ser cambiado. ¿Qué hacemos entonces? Pues, la solución es copiar el valor de la variable \texttt{actual} antes de hacer la actualización de la misma. De esta forma, el valor estará disponible luego de la actualización. La variable que mantiene la copia la hemos denominado \texttt{copia\_actual}, la actualizamos antes del cálculo del término actual y la usamos luego para actualizar el valor de la variable \texttt{anterior}

#include<stdio.h>

int main() {
    int n;
    printf("Ingrese número de términos: ");
    scanf("%d", &n);

    if (n <= 0)
        printf("Debe ingresar un número mayor que cero");
    else {
        if (n >= 1)
            printf("0 ");
        if (n >= 2)
            printf("1 ");
        long anterior = 0;
        long actual = 1;
        int i = 3;
        while (i <= n) {
            long copia_actual = actual;
            actual = actual + anterior;
            anterior = copia_actual;
            printf("%ld ", actual);
            i++;
        }
    }
    return 0;
} 

Versión usando la instrucción for

Esta versión la implementaremos con la instrucción \texttt{for}. Esta instrucción es en realidad una instrucción con entrada controlada. La diferencia que existe con la instrucción \texttt{while} es únicamente en la sintaxis. Con la instrucción \texttt{for} la inicialización, la condición de parada y la actualización, se realiza todo en una misma línea. 

En esta versión básicamente se itera con la variable de control \texttt{i} desde el valor de 3 hasta n incrementando en cada paso o iteración a \texttt{i} con el valor de 1. En cada iteración, actualizamos el término de la serie de Fibonacci y lo imprimimos.

#include<stdio.h>

int main() {
    int n;
    printf("Ingrese número de términos: ");
    scanf("%d", &n);

    if (n <= 0)
        printf("Debe ingresar un número mayor que cero");
    else {
        if (n >= 1)
            printf("0 ");
        if (n >= 2)
            printf("1 ");
        long anterior = 0;
        long actual = 1;
        int i;
        for (i = 3; i <= n; i++) {
            long copia_actual = actual;
            actual = actual + anterior;
            anterior = copia_actual;
            printf("%ld ", actual);
        }
    }
    return 0;
} 

Versión usando la instrucción do..while

Ahora veamos una versión en la cual usamos la estructura iterativa con salida controlada. En ANSI C la implementamos con la instrucción \texttt{do-while}. En este programa también usaremos la variable  \texttt{i} para el control de flujo. Inicializamos la variable de control \texttt{i} con el valor de 2. A diferencia de la versión anterior, no podemos inicializar \texttt{i} con el valor de 3 ya que al realizarse un control en la salida, la iteración debe necesariamente ejecutarse por lo menos una vez.

Esta estructura algorítmica iterativa, siempre imprime por lo menos una término. Y, ¿qué término es ese? Pues, el término 2. Por ese motivo, solamente se ejecuta si es que \texttt{n>=2}. La lógica del programa es muy similar a la versión anterior.

#include<stdio.h>

int main() {
    int n;
    printf("Ingrese número de términos: ");
    scanf("%d", &n);

    if (n <= 0)
        printf("Debe ingresar un número mayor que cero");
    else {
        printf("0 ");
        if (n >= 2) {
            long anterior = 0;
            long actual = 1;
            int i = 2;
            do {
                long copia_actual = actual;
                actual = actual + anterior;
                anterior = copia_actual;
                printf("%ld ", actual);
                i++;
            } while (i <= n);
        }
    }
    return 0;
} 

Versión usando Programación Modular

La serie de Fibonacci es uno de los problemas clásicos en la computación que se analizan cuando se comienzan a revisar las estructuras iterativas y el paradigma de programación modular. En las siguientes secciones presentaremos distintos programas utilizando el paradigma de la programación modular, así como una versión realizada usando la técnica de programación dinámica.

Función principal

Realizaremos la implementación de la función principal. Esta será la misma para la versión recursiva. Tiene básicamente 3 objetivos:

  •  Leer el dato de entrada.
  • Validar el dato leído.
  • Iterar invocar a la función que va a realizar el cálculo del factorial.
 

Para la lectura de datos se utiliza la instrucción \texttt{scanf}. El dato leído será almacenado en la variable \texttt{n}. La validación la realizaremos con una selectiva doble. Se emitirá un mensaje informativo si es que el número es \texttt{<=0}.

Una vez que se han validado los datos, se procede a invocar a la función \texttt{fibonacci}. La función \texttt{fibonacci} retorna el valor del término de la serie de Fibonacci cuyo número de término se pasa como parámetro.

#include<stdio.h>

int main() {
    int n;
    printf("Ingrese número de términos: ");
    scanf("%d", &n);

    if (n <= 0)
        printf("Debe ingresar un número mayor que cero");
    else {
        int i;
        for (i = 1; i <= n; i++)
            printf("%ld ", fibonacci(i));
    }
    return 0;
} 

Función Fibonacci

La función \texttt{fibonacci} recibe como parámetro el número \texttt{n}. Se asume que este número \texttt{n} es mayor que cero. Este parámetro \texttt{n} indica el número del término que se solicita. La función retorna el n-ésimo término de la serie de Fibonacci.

La función se ha implementado con una iterativa con salida controlada. Es muy similar a la versión iterativa presentada anteriormente. Analice con cuidado esta versión con la anterior y notará la diferencia. Como siempre comentamos, existen muchas maneras de llegar a la misma solución.

#include<stdio.h>

long fibonacci(int n) {
    if (n <= 2)
        return n - 1;
    long anterior = 0;
    long actual = 1;
    int i = 2;
    do {
        long copia_actual = actual;
        actual = actual + anterior;
        anterior = copia_actual;
        i++;
    } while (i < n);
    return actual;
} 

Versión recursiva

La siguiente versión a implementar es la versión recursiva. Quizás sea la más simple de entender pues prácticamente es la representación en ANSI C de la definición recursiva. Los algoritmos recursivos suelen ser simples de implementar pero en muchas ocasiones no son tan eficientes como las implementaciones iterativas.

long fibonacci(int n) {
    if (n <= 2)
        return n - 1;
    return fibonacci(n - 1) + fibonacci(n - 2);
} 

Versión usando Programación Dinámica

Algoritmos como la determinación de un término de la serie de Fibonacci, poseen una característica especial, para hallar el valor de fib_n, debe calcularse fib_{n-1} y fib_{n-2}. Las versiones que hemos realizado con programación modular, poseen este problema. Y es un problema que, en algunas ocasiones, genera la utilización de función. 

Esto no ofrecería ningún problema si es que la función se ejecuta una sola vez, pero ¿qué pasa cuando en un programa necesitamos invocar varias veces a la función fibonacci? Pues, en ese caso las soluciones implementadas con programación modular no serian eficientes. Por ejemplo, imagínese que hacemos las invocaciones a las funciones \texttt{fibonacci(10)}\texttt{fibonacci(5)}. En este caso hipotético se repetirían muchos cálculos, algunos más de una vez.

¿Cómo evitamos recalcular tantas veces los términos de la serie de Fibonacci? Pues existe una técnicas de programación llamada programación dinámica que justamente busca reducir el tiempo de ejecución de los algoritmos. Esto lo logra reusando resultados obtenidos previamente. Estos resultados suelen ser almacenados en arreglos o matrices. 

Función principal

Vamos a implementar la función principal para el determinación de los términos de la serie de Fibonacci. Hay ligeros cambios en relación a las versiones anteriores. Los dos primeros objetivos son los mismo pero el tercer y cuarto son diferentes.

  •  Leer el dato de entrada.
  • Validar el dato leído.
  • Invocar al módulo que va a realizar la inicialización del arreglo.
  • Retornar el valor de la serie de Fibonacci usando el arreglo inicializado.
 
 
El primer gran cambio que vemos es que no existe una función \texttt{fibonacci}. Entonces ¿cómo se hace para hallar el valor del término de la serie? Pues en lugar de ello se usa un arreglo, al que convenientemente hemos denominado \texttt{fibonacci}. Dicho arreglo va a contener el valor de los términos de la serie de forma que \texttt{fibonacci[1]} contendrá el valor de \texttt{0}, \texttt{fibonacci[2]} contendrá el valor de \texttt{1} y en general \texttt{fibonacci[n]} contendrá el valor de fib_n.

 

Resulta muy sencillo el retornar los términos de la serie pero, ¿cómo se inicializa dicho arreglo? Pues este es en realidad el problema de la programación dinámica. Debemos llenar el arreglo con el valor de los términos de la serie antes de utilizar dicho arreglo. Esta inicialización la debemos hacer una única vez durante todo el programa.

El arreglo ha sido declarado con la instrucción \texttt{long fibonacci[MAX\_TERMINOS+1]}. Esto significa que el arreglo tendrá 94 elementos. Los índices válido para el arreglo serán [0..93]. Para este problema, no usaremos el índice 0. Creamos un arreglo cuyo máximo índice es el valor de 93 debido a que es el máximo término que Fibonacci que se puede representar en ANSI C.

#include<stdio.h>
#define MAX_TERMINOS 93

int main() {
    int n;
    long fibonacci[MAX_TERMINOS + 1];

    printf("Ingrese número de términos: ");
    scanf("%d", &n);

    if (n <= 0 || n > 93)
        printf("Debe ingresar un número en el rango [0..93]");
    else {
        inicializar_arreglo(fibonacci);
        int i;
        for (i = 1; i <= n; i++)
            printf("%ld ", fibonacci[i]);
    }
    return 0;
} 

Inicialización del arreglo

A continuación presentamos el algoritmo para inicializar el arreglo. Básicamente lo que hacemos es inicializar el primer elemento (asumiendo el primer elemento el que se encuentra en la posición 1 y no en la 0) con el valor de \texttt{0}, el segundo con el valor de \texttt{1}. Luego en un ciclo iterativo, que en realidad puede ser usando cualquiera de las versiones previamente analizadas, se actualizan los demás elementos del arreglo. En dicha actualización siempre se usan los dos elementos anteriores.

void inicializar_arreglo(long *fibonacci) {
    fibonacci[1] = 0;
    fibonacci[2] = 1;
    int i;
    for (i = 3; i <= MAX_TERMINOS; i++)
        fibonacci[i] = fibonacci[i - 1] + fibonacci[i - 2];
} 

Conclusión

Hemos presentado en este artículo, 5 alternativas de solución al clásico problema de la serie de Fibonacci usando ANSI C. Se ha controlado el flujo usando estructuras selectivas e iterativas usando tanto ciclo con entrada controlada como salida controlada. Además se ha presentado versiones de la solución trabajando con el paradigma de programación modular, la  recursión así como la programación dinámica. Podrá descargar la solución propuesta en el repositorio GitHub de iterando++ a través del siguiente enlace

Hemos preparado otros artículos adicionales en donde describimos al detalle la implementación de este problema PSeInt y en otros lenguajes de programación. Te invitamos a leer los siguientes artículos de iterando++

Si quieres profundizar en el lenguaje ANSI C, no hay mejor libro que C Programming Language de Brian Kernighan  y Dennis Ritchie. Es un libro clásico escrito por el creador del lenguaje C. Uno de los libros favoritos de los que inician en ANSI C es  C Programming Absolute Beginner’s Guide de Greg Perry y Dean Miller.

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *