c) Si los tres son diferentes imprima el texto "Son diferentes".
Solución con estructuras repetitivas
1- Elabore un algoritmo que imprima los primeros N números pares.
2- Confeccionar un algoritmo que imprima los productos de la tabla del 5.
3- Entradas las seis notas de un alumno haga un algoritmo que imprima cual fue la mejor y cual la peor.
4- Se tiene una cantidad x de números enteros comprendidos en el intervalo de 0 a 100. Se desea hacer un algoritmo que imprima el menor y el mayor.
5- Dada una cantidad de 80 números diseñe un algoritmo que imprima cuantos de ellos son positivos y cuantos negativos.
Solución utilizando variables con subíndices
1- Dada una lista con 50 números, elabore un algoritmo que diga cuantos de ellos son positivos.
2- Conocidas dos listas, una con los nombres de los alumnos de una escuela y otra con sus respectivas notas de matemática. Diseñe un algoritmo que muestre los nombres de los suspensos.
3- Se tiene una lista ordenada ascendentemente que contiene 20 números. Confeccione un algoritmo que obtenga otra lista con los mismos números pero ordenada descendentemente.
4- Tenemos una lista con x cantidad de números positivos. Construya un algoritmo que nos muestre la diferencia entre el mayor y el menor de ellos.
5- Dada una lista de 100 números positivos, construya un algoritmo que cree dos listas más, una con los números que sean menores que 10 y otra con los mayores de 10.
6- Se tiene una lista con 50 números. Elabore un algoritmo que permita separar los que sean negativos en una lista y los positivos en otra.
Algoritmos básicos
Durante el estudio de la programación de máquinas computadoras, es muy útil el conocimiento y el análisis de algunos algoritmos básicos que dan soluciones a pequeños problemas y que aunque a veces dichas soluciones no sean de las más óptimas, por lo menos nos ayudan a comprender el principio de funcionamiento necesario.
Contar con una biblioteca llena de estos pequeños módulos es de mucha utilidad para todos los programadores, pues esto les permitirá ir estudiándolos a fondo así como podrán transformarlos con el fin de optimizarlos y lograr mejores rendimientos. En muchos casos veremos que se obtendrán varias versiones a partir de un mismo algoritmo, las cuales darán respuesta a las diferentes exigencias que se puedan presentar durante la solución de nuestros problemas.
Intercambio de valores entre dos variables.
El primer algoritmo básico que vamos a ver en este capítulo es el elaborado para intercambiar el valor de dos variables.
A continuación tenemos las variables A y B y queremos cambiar entre sí sus valores. Esto se muestra en el esquema 4.1 y como se puede ver, constituye un pequeño fragmento de algoritmo muy simple que nos muestra a simple vista como, para poder realizar esta tarea, tenemos que hacer uso de una tercera variable auxiliar (en este caso llamada AUX) debido al carácter destructivo que posee la asignación de valores. Antes de asignar a la variable A el valor de B, es necesario haber guardado previamente el valor de esta primera ya que de lo contrario se perdería.
Cálculo de la media o promedio.
Cuando trabajamos con listas de números, muchas veces nos vamos a ver en la necesidad de realizar una serie de operaciones rutinarias. Una de ellas, muy utilizada, es la de hallar el valor promedio o media, que no es más que sumar todos los valores y dividir este resultado por la cantidad total de ellos.
El algoritmo básico para el cálculo del promedio va a variar en dependencia de cómo se obtengan los datos desde el exterior. Vamos a presentar como ejemplo para este cálculo el caso de que los números ya están almacenados en memoria a través de una variable con subíndices. El fragmento de diagrama de bloques correspondiente se encuentra representado, de tres variantes diferentes, en el esquema 4.2.
Para poder calcular el valor promedio o media de un grupo de datos numéricos es necesario conocer la cantidad de estos que van a ser procesados.
En determinadas situaciones nos vamos a encontrar con el caso de que contamos ya de antemano con dicha cantidad o, al menos, tenemos la posibilidad de leerla desde algún dispositivo e incluso calcularla nosotros mismos. En los fragmentos del esquema 4.2 la cantidad de elementos almacenados se asume que está almacenada en la variable CANT.
Búsqueda de valores extremos.
Otra de las operaciones que se podrán ver muy a menudo con determinadas agrupaciones de datos numéricos es la de hallar sus valores máximo y mínimo. Los algoritmos para cada una de estas operaciones van a ser muy sencillos y prácticamente iguales.
El algoritmo del esquema 4.3.a permite hallar el valor máximo, mientras que el representado en 4.3.b permite hallar el valor mínimo. Se puede observar que la única diferencia entre ambos lo constituye el signo de comparación en la instrucción alternativa o de condición que aparece en el interior del ciclo repetitivo.
Ordenamiento.
El ordenamiento de los datos constituye un proceso muy común no sólo desde el punto de vista de la programación, sino también en la vida real. A diario nos vamos a poder encontrar con innumerables casos en los cuales se hace necesaria la tarea de presentar un grupo mayor o menor de datos de forma ordenada con el fin de realizar sobre estos alguna acción.
El ordenamiento puede ser de muchas formas. Según facilite la acción que se vaya a efectuar, puede ser por orden alfabético (en el caso de que se trate de palabras), ascendente o descendente, agrupado, y demás.
Un ejemplo práctico que podemos observar es la guía de teléfonos. En ella aparecen todos los números telefónicos ordenados según varios criterios.
En la informática también nos vamos a ver en determinados momentos obligados a realizar ordenamientos a grupos específicos de datos. Aunque durante el procesamiento de la información sea necesario a veces efectuar dicha tarea, va a ser en la presentación de los datos donde se hará más común el uso del ordenamiento
Para el ordenamiento de los datos vamos a poder contar con algunas variantes de algoritmos. El esquema 4.4 nos muestra el método más ampliamente conocido por todos los programadores, el llamado método de ordenamiento de burbuja (bubble).
Este método de ordenamiento presenta como característica principal su fácil comprensión así como lo sencillo de su programación, constituyendo esto una gran ventaja con relación a todos los demás métodos existentes. No obstante presenta la notable desventaja de que es considerado probablemente el más deficiente de todos ellos. Aquí su diseño se basa en dos ciclos repetitivos anidados, o sea, uno dentro de otro. El ciclo de afuera es por condición y el de adentro es por conteo.
En el esquema 4.5 se puede apreciar el mismo ordenamiento de tipo burbuja pero con alguna mejoría. Se adiciona la variable T que va a permitir interrumpir la búsqueda cuando la lista esté ordenada y todavía falten comparaciones por ejecutarse.
Otro método de ordenamiento lo podemos ver en el fragmento de algoritmo del esquema 4.6. Este es el llamado método de inserción simple, el cual es mejor que el de burbuja y su eficiencia va a ser directamente proporcional al nivel de ordenamiento que presenten los datos.
El esquema 4.7 nos muestra el fragmento de algoritmo que representa otro tipo de ordenamiento, este es el llamado ordenamiento de selección o de empuje hacia abajo.
En este método de ordenamiento los elementos sucesivos se van a seleccionar y colocar en una posición apropiada. El número más grande de la lista es colocado en la posición final, después acto seguido, se coge al segundo más grande y se coloca en el final menos uno y así sucesivamente.
Búsqueda.
La búsqueda de uno o varios elementos dentro de una lista de datos es una actividad muy común dentro del campo de la computación. Para el programador va a ser de mucha importancia el estudio, análisis y comprensión de los diferentes métodos y técnicas existentes.
El algoritmo de búsqueda más simple es el definido como búsqueda secuencial, el cual después de definido el argumento a buscar, recorre la lista completa comenzando por el primer elemento.
En el esquema 4.8 podemos ver uno de los algoritmos básicos que representan a este tipo de búsqueda. Este diseño se basa en el uso de un ciclo repetitivo por condición donde se usan dos variables controladoras que son I y E. La cantidad de elementos contenidos en la lista donde se realiza la búsqueda está almacenada en N y el elemento a buscar lo guarda la variable K. En el caso de que dicho elemento buscado sea encontrado entonces en la variable B se guardaría el valor del subíndice o lo que es lo mismo, la posición que ocupa este dentro de la lista ya que como se puede apreciar los datos se encuentran almacenados dentro de una variable con subíndices.
Para realizar una búsqueda secuencial en una lista cualquiera de datos no es necesario que estos estén ordenados. Este método no es muy eficiente ya que la cantidad de comparaciones que se harán estará en correspondencia con la posición que ocupe dentro de la lista el elemento buscado. En el caso de que dicho elemento no exista o se encuentre al final de la lista entonces el algoritmo realizará tantas comparaciones como elementos contenga la misma.
Otro método mucho más eficiente que el anterior lo constituye el de búsqueda binaria que está representado en el esquema 4.9. Este algoritmo sí necesita de forma obligatoria para su ejecución que los datos se encuentren de forma ordenada dentro de la lista.
Implementación de una pila estática.
La pila (conocida en muchas literaturas con su nombre en inglés stack) constituye una estructura simple de datos y desempeña un importantísimo papel en todos los lenguajes de programación a la vez que es considerado su concepto como uno de los más útiles dentro de la ciencia de la computación. Al igual que las variables con subíndices, la pila es una colección de datos ordenados.
Aunque los datos dentro de la pila se organicen de forma análoga a las variables con subíndices, la forma de operar con ellos no va a ser igual. En ella solamente se podrán realizar dos operaciones: inserción y extracción de datos, las cuales se efectuarán únicamente por uno de los extremos llamado parte o extremo superior de la pila. Veamos el esquema 4.10 donde se ha tratado de representar la estructura de una pila conteniendo cinco valores.
Para que resulte más fácil el entendimiento de la estructura y funcionamiento de una pila podemos hacernos la idea de que tenemos un grupo de libros colocados unos encima de otros. Para agregar más libros al grupo tendríamos que irlos colocando en el extremo superior uno a uno y en caso de querer extraer alguno habría que ir quitando libros, también de dicho extremo, hasta llegar al que queremos coger. Como podemos ver, para realizar ambas operaciones siempre será necesario utilizar un solo extremo de la pila, mientras el otro permanece inmóvil. El extremo de la pila que no se mueve se llama parte o extremo inferior.
Pasemos ahora a representar de forma gráfica las operaciones de inserción y extracción que pueden ocurrir en una pila y utilizaremos para esto el esquema 4.11.
En el esquema 4.11.a podemos ver una pila conteniendo 3 datos, en este caso el extremo superior (representado por una flecha) está indicando el último elemento que ha entrado a dicha estructura el cual está representado por la letra C. Si seguimos agregando más datos (esquemas 4.11.b y 4.11.c) vemos entonces que la pila crece y su extremo superior se desplaza hacia arriba para mantenerse indicando al último dato que haya entrado. El esquema 4.11.d nos muestra la operación inversa o sea, la extracción de un dato (en este caso el representado por E). Ahí se puede observar como ahora el extremo superior ha bajado hacia el dato siguiente.
Hasta ahora se ha podido apreciar como funcionan las operaciones de inserción y extracción en la pila cuando adicionamos un dato o cuando extraemos el último que ha entrado. ¿Qué pasaría si quisiéramos extraer un dato entrado con anterioridad? El esquema 4.11.e ilustra el resultado de este proceso ya que se puede ver como, para poder extraer el dato representado por C, hemos tenido que extraer también el representado por D. Si en vez de querer la extracción de C hubiésemos deseado el dato representado por A, entonces hubiésemos tenido que extraer los datos D, C y B.
Aunque la pila es realmente de naturaleza dinámica (o sea que su tamaño va a variar de acuerdo a las acciones de inserción y extracción) también es posible implementarla en nuestros algoritmos de forma estática para un mejor estudio y comprensión de su funcionamiento. Para ello vamos a utilizar la variable con subíndice o variable de tipo arreglo con longitud fija. En la práctica los programadores utilizan las variables de tipo puntero y las estructuras de listas enlazadas para crear las pilas ya que esto les permite ir ocupando realmente los espacios de memoria a medida que guardan los datos y liberando dichos espacios a medida que los sacan.
Lo primero que tenemos que hacer para crear nuestra pila estática es definir el tamaño que tendrá, este siempre estará en dependencia de las necesidades reales de nuestro problema a resolver. En este caso, para nuestro pequeño ejemplo demostrativo con una variable de arreglo de longitud de 10 números será más que suficiente.
Como se explicó anteriormente, en una pila solamente podemos realizar dos operaciones que son insertar y extraer un elemento, veamos entonces como se implementa la primera de dichas operaciones.
En el esquema 4.12 se puede apreciar el algoritmo que nos va a permitir poder insertar un elemento nuevo en nuetra pila demostrativa. Aquí la pila se ha representado por la variable con subíndice A, el valor nuevo a guardarcon la variable N y la parte o extremo superior se ha decidido representar con la variable I.
La primera operación es leer el valor que se quiere guardar (como se mencionó anteriormente representado por la variable N), acto seguido se realiza un chequeo para ver si es posible realizar esta operación y es que como la capacidad con que definimos nuestra pila estática es de 10 elementos lo que se hace no es más que ver si su extremo superior es igual a dicha capacidad predefinida. De cumplirse lo anterior entonces no nos quedaría otra opción que abortar la operación de inserción y comunicar que la misma no se puede realizar por estar la pila llena. En el caso contrario, o sea, que la variable indicadora del extremo superior sea menor que la capacidad de la pila entonces se incrementaría en 1 dicho extremo y guardaríamos el valor en la nueva posición obtenida. Cabe mencionar aquí que cuando nos encontremos trabajando con pilas dinámicas, como estas no tienen un tamaño fijo en cuanto al número de elementos a guardar se refiere, el chequeo también es posible realizarlo, el cual se hará comprobando la capacidad de memoria disponible para este fin.
Técnicas de optimización de algoritmos.
Lo que más desean los usuarios que se enfrentan a trabajar frente a las computadoras con nuestros programas es que estos se ejecuten día tras día sin ningún tipo de fallo. Pero esto no va a ser suficiente ya que muchas veces van a exigir que dicha ejecución sea también con rapidez.
Para lograr la perfección en nuestros algoritmos es necesario conocer y dominar las técnicas de optimización existentes, las cuales nos van a permitir que los programas se ejecuten más rápido y ocupen menos espacio en los diferentes medios de almacenamientos a usar. Todo esto, por supuesto, sin que afecte para nada las funciones que realizan.
Hay autores que plantean la necesidad de optimizar solamente cuando el usuario ve la mejoría y de no ser así ven el proceso como un gasto inútil de esfuerzo. Es por eso que recomiendan ante todo, a la hora de optimizar, que el programador aprenda a seleccionar los fragmentos de código que valga la pena. Pensando y viendo las cosas desde otro punto de vista, es bueno decir que todas las tareas que se realicen a favor de mejorar un algoritmo requieren un estudio y análisis muy grande por parte del programador y aunque el usuario no note o no se percate de los cambios, la actividad realizada nunca será inútil. No se puede ver la confección de un algoritmo solamente desde la perspectiva de que va a ser útil solo a aquellos que harán uso de él como usuarios finales, hay que ver también la importancia que representa esto para los programadores como una vía de capacitación y superación. Ante cada nuevo programa al que se enfrenta un programador se presenta la oportunidad de adquirir nuevos conocimientos, de mejorar su estilo de diseñar y programar algoritmos, de ir pudiendo optimizar fragmentos de códigos anteriormente confeccionados. Recordemos que la tarea de optimización de los algoritmos ha sido siempre obra de personal con experiencia pues es más difícil que la programación convencional ya que consiste en teniendo la solución a un problema determinado buscar otra más rápida o más corta (a veces ambas a la vez).
Las optimizaciones aritméticas son muy comunes y a veces resultan ser las más fáciles de lograr ya que para los programadores principiantes basta con tener conocimiento y dominio de algunas reglas elementales, estas son:
1- Las operaciones aritméticas de suma y resta se ejecutan más rápido que las de multiplicación y división.
2- La operación aritmética de división es la más lenta de todas las operaciones.
3- Las operaciones aritméticas donde intervienen números enteros se ejecutan más rápido que aquellas donde intervienen números con lugares decimales (siempre que sean las mismas operaciones), o sea que el tipo de datos influye en la velocidad de los cálculos.
4- La operación aritmética de multiplicación con números decimales se ejecuta más rápido que la operación de división con números enteros.
5- La operación aritmética más lenta de todas es la división con números decimales.
6- En las operaciones aritméticas donde intervengan varias constantes numéricas seguidas se pueden calcular y presentar como una sola.
En muchos casos que usamos operaciones aritméticas y cálculos de diferentes tipos dentro de nuestros algoritmos es posible hacer sencillas optimizaciones solamente haciendo uso de las reglas anteriores. Veamos esto con un ejemplo, supongamos que dentro de un algoritmo tenemos la siguiente operación matemática:
Aplicando las reglas 2 y 4 tratemos de cambiar esta operación de división por otra que se ejecute más rápido pero que no nos altere el resultado. Lo anterior, formulado matemáticamente, nos quedaría de la siguiente forma:
Convirtiendo esto en una multiplicación se obtendría:
Ahora que ya está convertido en una operación aritmética de más rápida ejecución por la máquina lo llevamos nuevamente al algoritmo quedando de la siguiente forma:
Ahora podemos aplicar la regla 6 para resolver la operación de división de constantes numéricas y nos quedaría el resultado final que sustituiríamos en nuestro algoritmo:
Aquí se aplicó la regla de las matemáticas que plantea: dividir un número por otro número entero es lo mismo que multiplicar al primero por la inversa del segundo. El proceso de optimización es posible aplicarlo también en las diferentes instrucciones de nuestro algoritmo.
Anexo
ANEXO A
Simbología de los diagramas de bloques
ANEXO B
Respuestas comentadas a 2 de los ejercicios propuestos del capítulo 3
Soluciones lineales
Ejercicio 1
Este es un ejercicio sumamente fácil donde solamente interviene una operación matemática que es la resta. De esto nos damos cuenta ya que en el ejercicio se menciona la palabra "extraerle". Una posible solución es la siguiente:
Ejercicio 2
Este ejercicio se parece mucho al anterior con la diferencia de que solamente cuenta con un dato primario y la operación matemática que es necesario utilizar es la multiplicación.
Obsérvese que aquí se hace uso de un dato de tipo constante que es el número 5. Para que se tenga una clara comprensión de como se maneja este tipo de dato dentro de los algoritmos, mostramos dos posibles soluciones:
Análisis de los datos para la solución (a)
Autor:
Higinio Bellón Corvo
| Página siguiente |