Algoritmos y Estructuras de Datos.

 

Algoritmos y Estructuras de Datos: Conceptos Básicos

Variables y arreglos

La base de los temas que veremos durante esta serie son los conceptos de almacenamiento y manipulación de datos, por lo que me parece importante aclarar los conceptos de variable y arreglo ya que serán usados ampliamente a lo largo de la serie.

Variable

Como programadores usamos las computadoras para realizar ejecutar algoritmos, una serie de pasos enfocados en cumplir un objetivo. Si bien podemos ejecutar una serie de pasos que no requieran el almacenamiento de valores, lo mas probable es que nos encontraremos con la necesidad de almacenar un resultado, o los datos iniciales necesarios para realizar un calculo. Dicha información es almacenada en lo que conocemos como variables.

Una variable representa un espacio en la memoria de nuestra computadora en el cual podemos almacenar datos.

El nombre de la variable también conocido como identificador, está ligado aun espacio en la memoria de la computadora, de esa manera cuando nosotros usamos una variable en nuestro código, la computadora almacena o lee el valor de la dirección de memoria ligada al nombre de la variable.

Veamos el siguiente ejemplo:

Supongamos que deseamos obtener la suma de los números 4 + 5, usando pseudocódigo* podemos obtener el siguiente algoritmo:

inicio
   imprime 4 + 5
fin

Simple, ahora imaginemos que deseamos que nuestro algoritmo funcione para cualesquiera par de números, necesitaríamos obtener primero el valor de dichos números, llamémosles a y b para posteriormente obtener su suma, si implementamos esto en el pseudocódigo obtendríamos lo siguiente:

inicio
   leer a
   leer b
   imprimir a + b
fin

Al utilizar una variable, a y b en este caso, no nos ponemos a pensar en donde se almacenarán exactamente, sin embargo podemos suponer que la computadora guardara los valores en los primeros dos espacios en memoria libres que encuentre y ligara dichas direcciones a las variables a y b.

Arreglos

Si bien las variables las usaremos a diario como programadores, hay una estructura de datos creada para cubrir algunas de las desventajas de las variables o bien para darnos la posibilidad de manipular de manera mas sencilla las variables o memoria en nuestra computadora, esta estructura es el Arreglo de datos (Array).

Un arreglo es un contenedor de datos, el cual nos permite acceder de manera sencilla a cada uno de ellos mientras los mantenemos agrupados. Una de las ventajas del arreglo es que nos evita el tener que declarar cientos de variables usando cientos de nombres diferentes (uno para cada variable) agrupando todos los espacios de memoria que necesitemos bajo un identificador (nombre).

Ejemplo de almacenamiento en variables

Ejemplo de almacenamiento en arreglo

Los dos componentes básicos de un arreglo son su identificador y el indice, el identificador está ligado al espacio de memoria donde se encuentran todos los datos agrupados, el índice indica cuál de esos datos deseamos obtener o modificar.

Por lo general los indices del arreglo son números enteros en orden creciente, comenzando con el 0 y aumentando de uno en uno, esto varia según el lenguaje de programación con el que trabajemos.

Veamos el siguiente ejemplo:

Supongamos que deseamos salir a comer con nuestros compañeros, como no nos podemos poner de acuerdo cada día votamos por el platillo que comeremos y gana el que tenga más votos. Nuestra tarea es tomar los votos del día de hoy imprimir los votos de cada platillo. Cada voto es un numero entero mayor a uno que representa el platillo. Siempre hay 5 opciones de platillo, numerados del 1–5.

La idea es almacenar los votos por platillo en un arreglo, de tal forma que el indice representa el platillo y el valor los votos para dicho platillo.

En este ejemplo vemos que el platillo 1 obtuvo 15 votos, el platillo 2 obtuvo 20 votos, el platillo 3 obtuvo 25 y así sucesivamente. El platillo 0 al no existir tiene cero votos.

Usando pseudocódigo* podemos obtener el siguiente algoritmo:

inicio
   generar arreglo votos_por_platillo con 6 elementos
   hacer elementos de votos_por_platillo iguales a 0   mientras haya votos
      leer platillo_votado
      sumar 1 al indice platillo_votado en votos_por_platillo   imprime el indice 1 de votos_por_platillo
   imprime el indice 2 de votos_por_platillo
   imprime el indice 3 de votos_por_platillo
   imprime el indice 4 de votos_por_platillo
   imprime el indice 5 de votos_por_platillo
fin

Explicación:

En la primer linea creamos un arreglo de 6 elementos. Si bien los platillos están numerados del 1–5 recordemos que por convención el primer elemento de un arreglo tiene el indice 0, por eso si creamos un arreglo de 6 elementos tendremos el elemento 0 + los elementos del 1–5.

Ahora que tenemos el arreglo vamos a leer cada uno de los votos y aumentar en uno el contador correspondiente. Supongamos que los primeros 6 votos son los siguientes: 2, 3, 3, 4, 4, 5. Después de leer estos 6 votos obtenemos que el platillo 1 obtuvo 0 votos, el platillo 2 obtuvo , el platillo 3 obtuvo 2, el platillo 4 obtuvo 2 y el platillo 5 obtuvo 1.

Una vez que capturamos cada voto y lo sumamos en nuestro arreglo, lo unico que nos queda es imprimirlos. Recordemos que nuestro elemento 0 no lo estamos usando en este ejemplo, por lo que solamente debemos imprimir los votos de los platillos del 1–5.

Mejoremos un poco nuestro algoritmo

Por convención al manipular arreglos se utiliza la letra i como variable para indicar el indice del arreglo con el que deseamos trabajar. Podemos hacer uso de esto mejorar nuestro código y hacer que funcione para más casos.

En el ejemplo anterior solamente teníamos 5 platillos, supongamos que ahora cada vez que ejecutemos el algoritmo o nuestro pseudocódigo, tendremos una cantidad de platillos diferente. Para resolver esto haremos una serie de cambios en nuestro pseudocódigo.

1. En lugar de generar un arreglo con 6 elementos, vamos a leer la cantidad de platillos y a generar un arreglo con los espacios necesarios.
2. Recorreremos nuestro arreglo con un ciclo para imprimir los votos.

inicio
   leer cantidad_de_platillos  
   generar arreglo votos_por_platillo igual a cantidad_de_platillos
   hacer elementos de votos_por_platillo iguales a 0   mientras haya votos
      leer platillo_votado
      sumar 1 al indice platillo_votado en votos_por_platillo   hacer i igual a 0
   mientras i sea menor a cantidad_de_platillos
      imprime el indice i de votos_por_platillo
      aumenta i en 1
fin

Como podemos observar el pseudocódigo es muy similar, la principal diferencia es que agregamos un ciclo para imprimir, donde usamos la letra i para acceder a cada platillo comenzando con el platillo 0. Al aumentar la variable i después de imprimir los votos de un platillo, la aumentamos en 1, por lo que la segunda vez i sera igual a 1, en la siguiente i será igual a 2, después a 3, y así sucesivamente hasta que i sea igual a cantidad_de_platillos, lo que indicará que ya no hay más platillos por imprimir.

A simple vista no parece que hayamos quitado pasos a nuestro algoritmo para hacerlo más pequeño o simple a comparación del primero, sin embargo, los cambios que hicimos nos permiten evaluar 5, 10, 1000 o hasta un 1,000,000 de platillos sin tener que agregar mas lineas. A su vez el uso del arreglo nos permite tener un pseudocódigo estable, sin tener que declarar una variable independiente para almacenar los votos de cada platillo o escribir una linea para por cada elemento para imprimir los resultados.

En el siguiente post de la serie estaremos hablando de la complejidad computacional, y como esta nos ayuda para evaluar la eficiencia de nuestros algoritmos.

Tomado de: https://medium.com/@rodomg/algoritmos-y-estructuras-de-datos-504253460a85

escanear código para ir a la pagina fuente