• Author / Uploaded
• Juan Luis M G

Citation preview

FUNDAMENTOS DE PROGRAMACIÓN I

UDC003

Parte II La presente guía tiene como finalidad continuar con el proceso de inmersión del estudiante en el mundo de la programación. Por tal motivo su contenido se centrará en proporcionar un conjunto de conocimientos básicos complementarios de programación orientados a la solución de problemas mediante su descomposición en problemas más específicos que puedan ser resueltos con un algoritmo, al igual que se le enseñará la forma en la que la información puede ser almacenada dentro de las denominadas estructuras de datos y como posteriormente esta información podrá ser organizada utilizando algoritmos de ordenamiento concretos; para ello se abordarán los siguientes temas: modularización (métodos y parámetros), arreglos y matrices como estructuras de datos, y, búsquedas y ordenamientos en 3 módulos. Página 3

TEMARIO •••

Módulo 1: Modularización Métodos y parámetros…..……………….............................................…………….

06

Introducción ……………………………………………………………………………………………………

07

1.01 Modularización …….……….……………………………………………………………….................

08

1.01.01 Ventajas de la modularización …………………………………………...................

08

1.01.02 Ejemplo de un algoritmo modularizado …………………………………...............

09

1.02 Métodos ……………………....……………………………………………...………………................

10

1.02.01 Métodos y Lenguajes de Programación …..………………………………………..

10

1.02.02 Declaración de un método ………………..……………………………...…………..

10

1.02.03 El cuerpo de un método …………………...……………………………...…………..

12

1.02.04 Invocación de un método ………………...……………………………...…………..

13

1.02.05 Almacenamiento en memoria de los argumentos ...………………...…………..

15

1.03 El ámbito de las variables de un método ...…..…………………………………………………..

15

1.03.01 Variables Locales …………………….…………..……………...……………...............

16

1.03.02 Variables Globales ...…………………………..………………..……………...............

18

Actividad 1 ……………………………………………………………………………………………………..

19

Banco de Ejercicios 1 ……………………..…………………………………………………………………

20

Autoevaluación 1 ……………………………………………………………………………………………..

23

Módulo 2: Arreglos y Matrices Estrucuras de Datos …………………………………………..……………………...… Introducción …………………………………………………………………………………………………...

27 27

2.01 Arreglos ………………………………………………………………….……………………...……......

28

2.01.01 Esquema de un arreglo de datos en memoria RAM …………………................

28

2.01.02 Componentes de un arreglo de datos ….……..…………………..……...............

28

2.01.03 Arreglos en PSeInt …………………………….……..…………………..……...............

29

2.02 Matrices ………………...………………………………………………………...……………………...

29

2.02.01 Componentes de una matriz ..……………………..……………………..................

29

2.02.02 Matrices en PSeInt …..……………………………………….…...……...……………...

30

Actividad 2 ……………………………………………………………………………………………………..

31

Página 4

Fundamentos de Programación I Banco de Ejercicios 2 ………………………………………………………………………………………..

33

Autoevaluación 2 ……………………………………………………………………………………………..

37

Módulo 3: Búsquedasy Ordenamientos En estructuras de datos ………………………………….....………………………….

42

Introducción ……………………………………………………………………………………………………

43

3.01 Búsquedas …….……………...………………………………………………………………………....

44

3.01.01 Porqué son importantes las búsquedas …………………………………................

44

3.01.02 Algoritmos de búsqueda ……....……………………………………………...............

44

3.01.02.01 Búsqueda lineal o búsqueda secuencial …………………………....

45

3.01.02.02 Búsqueda binaria ………………………………………………………....

46

3.01.03 Análisis de los algoritmos de búsqueda ………………….………………...............

48

3.01.03.01 Complejidad de la búsqueda secuencial .….……………………....

49

3.01.03.02 Complejidad de la búsqueda binaria …….….……………………....

49

3.01.03.03 Comparación entre los métodos de búsqueda secuencial y

49

búsqueda binaria …....…………………………………………………………….….... 3.02 Ordenamientos …………..……….……......…………………………………………………………..

50

3.02.01 ¿Qué es ordenar? ….…………………………………………………………...............

50

3.02.02 Algoritmos de ordenamiento ....……………………………………………...............

50

3.02.02.01 Algoritmo de ordenamiento por inserción .….……………………....

50

3.02.02.02 Algoritmo de ordenamiento por el método de la burbuja ……....

52

3.02.02.03 Algoritmo de ordenamiento por el método de selección …….....

54

3.02.03 Análisis de los métodos de ordenamiento …...…………………………................

57

Actividad 3 ……………………………………………………………………………………………………..

58

Banco de Ejercicios 3 ………………………………………………………………………………………..

59

Autoevaluación 3 …………………………………………………………………………………………….

61

Referencias ……………………………………………………………………………….

64

Página 5

1

MODULARIZACIÓN: MÉTODOS Y PARÁMETROS

OBJETIVOS ESPECÍFICOS DEL MÓDULO 1. Analizar un problema que puede ser resuelto con un algoritmo y descomponerlo en problemas más específicos. 2. Formular algoritmos usando métodos para resolver los sub-problemas específicos resultantes de la descomposición de un problema general. 3. Explicar las técnicas necesarias para declarar e invocar métodos. 4. Introducir nociones básicas acerca del ámbito de una variable en un método.

CONTENIDO Introducción 1.1

1.2

Modularización 1.01.1

Ventajas de la modularización

1.01.2

Ejemplo de un algoritmo modularizado

Métodos 1.02.1

Métodos y Lenguajes de Programación

1.02.2

Declaración de un método

1.02.3

El cuerpo de un método

1.02.04 Invocación de un método 1.02.5 1.3

Almacenamiento en memoria de los argumentos

El ámbito de las variables de un método 1.03.1

Variables Locales

1.03.02 Variables Globales

Página 6

Fundamentos de Programación I

I NT RODUCC IÓ N La experiencia ha demostrado que la mejor manera de desarrollar y mantener (brindar soporte y garantizar el acceso a actualizaciones específicas) un sistema informático extenso (programa), es construirlo mediante la integración de componentes simples y pequeños. El término genérico utilizado dentro del contexto de PROGRAMACIÓN para designar a cada una de estas partes o componentes es módulo y el proceso de dividir un programa en diferentes módulos se denomina modularización. Por lo que, el proceso de modularización es una parte trascendental dentro del diseño de la solución a un problema mediante un programa de computadora, debido a que ésta permite al desarrollador generar un programa con una estructura apropiada, que sea fácil de adaptar y mantener, además de entendible y eficiente en cuanto a su ejecución (Deitel y Deitel, 2012). Considerando que, el proceso de modularizar un programa corresponde a la estructuración y separación de las tareas que realiza en métodos, el término método será usado dentro de este contexto para referirse a un fragmento de código auto-contenido que ejecuta una tarea específica (Leiva, 2012), por lo tanto es factible de mencionar que, el método no es más que la utilización de una herramienta que ayuda a modularizar un programa, en donde, el término utilizado para representar a éste concepto en específico varía según el lenguaje de programación que se esté utilizando. Por ejemplo, la palabra método es generalmente utilizada en JAVA, mientras que en C++ el mismo concepto es referido como función y en BASIC se emplea la expresión subrutina o procedimiento, por lo que, en lo que resta de éste documento se dará preferencia al término MÉTODO en forma consistente, sin que esto implique que la utilización de la terminología función, subrutina o procedimiento descontextualicen el concepto analizado en el presente módulo.

Página 7

Fundamentos de Programación I

1.01 MODULARIZACIÓN.

1.01.01 Ventajas de la Modularización. La correcta modularización de un programa en métodos, no solo facilita su proceso de diseño, implementación y operación, sino que, adicionalmente facilita tareas posteriores a su culminación, como es el caso del mantenimiento, una labor crítica y sumamente complicada de efectuar sobretodo en programas que tienen una gran extensión (en términos de la cantidad de funcionalidades que se espera que preste dicho programa y, en definitiva, del número de líneas de código que lo componen) (Leiva, 2012).

La utilización de métodos ayuda a la modularización de un programa mediante la segmentación de sus tareas en unidades auto-contenidas, y considerando que, las instrucciones que componen un método se escriben una sola vez y pueden ser reutilizadas en varias partes del programa o incluso en otros programas que requieran realizar tareas similares (Deitel y Deitel, 2012), es posible emplear métodos existentes como bloques constructivos para crear programas, dejando en cierto sentido a éstas instrucciones ocultas para otros métodos, a esta técnica se la conoce como reutilización de código. De hecho, es habitual que gran porcentaje de un programa esté compuesto por métodos predefinidos, en lugar de código personalizado. Por lo que, modularizar un programa hace que el desarrollo de dicho programa sea más manejable, mediante la construcción del mismo usando segmentos mucho más pequeños y simples (Fig. 1), un hecho que a la vez facilita la corrección de errores y el mantenimiento del mismo.

Fig. 1 Modularización.

Un principio básico que debe aplicarse y que facilita la modularización de un programa y por ende la reutilización de código, es que todo método debe limitarse a ejecutar una sola tarea claramente definida2, debido a que un método que ejecuta una sola tarea es más fácil de probar y depurar que uno que ejecuta muchas tareas. 2 Este es uno de los principios básicos de la filosofía de desarrollo del sistema operativo U NIX (do one thing and do it well).

Página 8

Fundamentos de Programación I

Pero ésta idea de utilizar métodos para resolver problemas no debería resultarnos para nada compleja, debido a que muy probablemente nos encontremos altamente familiarizados de forma inconsciente con el uso de métodos en nuestra vida cotidiana y mientras desarrollamos determinadas tareas para nosotros habituales sin siquiera habernos percatado de ello. Por ejemplo, cuando escribimos un texto en la pantalla del computador o cuando calculamos la raíz cuadrada de un número, de hecho, estamos empleando métodos predefinidos en una librería específica del lenguaje de programación con el cual la aplicación que estamos utilizando fue desarrollada. En el siguiente enlace se encuentra disponible un video que presenta una explicación básica de un ejemplo de modularización aplicado a la vida real que esperamos le sea de gran utilidad.

1.01.02 Ejemplo de un algoritmo modularizado. En la Fig. 2 se puede apreciar el ejemplo de la modularización de un algoritmo que permite encontrar el mayor de tres números ingresados por el usuario, para lo cual recurre a la ayuda de un método (max), que es el encargado de determinar el mayor de los números ingresados. Algoritmo Algoritmo numero_mayor Escribir(“Ingrese 3 números: “) Leer(a, b, c) mayor = max(a, b, c) Escribir(“El número mayor es “, mayor) Fin Algoritmo

Método Numero max (Numero num1, Numero num2, Numero num3) num_max = num1 Si num2 > num_max Entonces

Fin Si

num_max = num2

Si num3 > num_max Entonces

Fin Si

num_max = num3

Retornar num_max Fin Metodo

Fig. 2 Ejemplo – Algoritmo para encontrar el mayor de tres números.

Página 9

Fundamentos de Programación I

1.02 MÉTODOS.

1.02.01 Métodos y Lenguajes de Programación. La mayoría de los lenguajes de programación proveen al desarrollador de una extensa colección de métodos predefinidos para las tareas más comunes, esta colección se almacena dentro de una estructura a la que se denomina librería de métodos. Generalmente, la librería de métodos suministrada por un lenguaje de programación está conformada por un conjunto de procedimientos que permiten llevar a cabo cálculos matemáticos comunes,

manipulación de texto y caracteres, operaciones de entrada/salida, operaciones con bases de datos, operaciones de redes de computadoras, procesamiento de archivos, entre otras tareas. Sin embargo, un desarrollador puede escribir sus propios métodos según lo requiera el procedimiento diseñado para la solución del problema. Por lo tanto y desde ésta perspectiva, un programa de computadora se convierte en una combinación coherente de métodos tanto predefinidos en una librería como desarrollados por el programador (Gómez y Fernández, 2013).

1.02.02 Declaración de un método. La oportuna y adecuada declaración de un método, no solo permite a futuro su rápida localización, sino que además una veloz identificación de la función específica que éste realiza dentro de un programa, ofreciendo de ésta forma al desarrollador, una visión mucho más clara de sus posibles escenarios de usabilidad, facilitando una reutilización coherente y sobretodo eficiente de código, pues podrían existir funciones declaradas de manera análoga que cumplen labores completamente diferentes o funciones incorrectamente declaradas cumpliendo tareas similares. En la Fig. 3 se muestran los diferentes elementos que componen la declaración de un método.

Fig. 3 Declaración de un método.

A continuación, se detalla cada uno de los componentes que intervienen en la declaración de un método. •

Tipo de dato de retorno: Indica el tipo de dato que retorna o da como resultado el método y que será utilizado por el código en el que fue invocado. Por ejemplo, el tipo de retorno puede indicar que el resultado del método es un número entero, un número decimal, una cadena de texto, etc. Cabe aclarar que, un método puede retornar sólo un o ningún valor. El no retornar ningún valor, implica que el método se limita a cumplir con una tarea específica sin que haya necesidad de que retorne un valor en específico, por lo que en éste caso, obviamente, no es necesario especificar el tipo de valor

Página 10

Fundamentos de Programación I

de retorno. Por ejemplo, tomando como referencia al algoritmo planteado anteriormente en la Fig. 2, el tipo de retorno del método max indica que devolverá un valor numérico, posiblemente incluyendo una parte decimal. Algoritmo Algoritmo numero_mayor Escribir(“Ingrese 3 números: “) Leer(a, b, c) mayor = max(a, b, c) Escribir(“El número mayor es “, mayor) Fin Algoritmo

Método Numero max

(Numero num1, Numero num2, Numero num3)

num_max = num1 Si num2 > num_max Entonces

Fin Si

num_max = num2

Si num3 > num_max Entonces

Fin Si

num_max = num3

Retornar num_max Fin Metodo

Fig. 2 Ejemplo – Algoritmo para encontrar el mayor de tres números.

•

Nombre del método: Especifica el nombre que se utilizará para llamar o invocar al método que se está declarando, motivo por el que, es extremadamente importante que el nombre escogido sea significativo, es decir, que exprese claramente la tarea que cumple. Este principio se aplica también a los nombres de variables y, en general, a todos los nombres que defina el programador dentro de su código. Si es difícil encontrar un nombre conciso que exprese claramente la funcionalidad de un método, muy probablemente esto podría significar que dicho método intenta ejecutar demasiadas tareas y que, por lo tanto, se debe pensar en fragmentar el método en partes más pequeñas que cumplan funciones específicas y fáciles de definir. Para definir el nombre de un método es factible utilizar letras minúsculas y/o MAYÚSCULAS, números y el guion bajo (_). Por otra parte, no se permite utilizar caracteres especiales como vocales tildadas, la ñ, el guion medio (-), llaves, corchetes, entre otros, así como no es permitido empezar el nombre de un método con un número.

•

Lista de parámetros: A continuación del nombre del método se incluye la lista de parámetros delimitada por paréntesis. Esta lista puede contener uno o más parámetros separados por comas o simplemente puede no contener parámetros, según lo requiera el diseño del método. La lista de parámetros consiste en información adicional que se le proporciona al método en el momento de su Página 11

Fundamentos de Programación I

invocación, en donde, cada parámetro con su tipo de dato correspondiente es suministrado como una variable que puede ser referenciada y utilizada en el cuerpo del método. Si la lista de parámetros está vacía, significa que el método declarado no requiere ninguna información adicional para ejecutar su tarea. En el caso específico del algoritmo presentado en la Fig. 2 la lista de parámetros del método max está conformada por tres variables numéricas (que posiblemente incluirán una parte decimal) llamadas num1, num2 y num3. Algoritmo Algoritmo numero_mayor Escribir(“Ingrese 3 números: “) Leer(a, b, c) mayor = max(a, b, c) Escribir(“El número mayor es “, mayor) Fin Algoritmo

Método Numero max

(Numero num1, Numero num2, Numero num3)

num_max = num1 Si num2 > num_max Entonces

Fin Si

num_max = num2

Si num3 > num_max Entonces

Fin Si

num_max = num3

Retornar num_max Fin Metodo

Fig. 2 Ejemplo – Algoritmo para encontrar el mayor de tres números.

1.02.03 El cuerpo de un método. A la sentencia de declaración conformada por: tipo de dato de retorno, nombre del método y lista de parámetros (Fig. 3) se la denomina encabezado, mientras que el cuerpo del método, se encuentra definido por un conjunto de (una o más) instrucciones que se escriben y ejecutan dentro del método para cumplir con una tarea específica. La combinación de la declaración y el cuerpo del método conforman una entidad auto-contenida en el sentido de que la información que se utiliza

y las operaciones que se ejecutan dentro del método son sólo conocidas y relevantes para el método en cuestión, debido a que, ninguna otra parte del programa puede acceder a ellas de forma directa.

Página 12

Fundamentos de Programación I

A fin de aclarar este concepto, retomamos la Fig. 2, en donde claramente podemos observar la tarea específica que cumple el método max dentro del algoritmo (encontrar el mayor de tres números) y como las operaciones que se ejecutan dentro del mismo son únicamente conocidas por el método. Algoritmo Algoritmo numero_mayor Escribir(“Ingrese 3 números: “) Leer(a, b, c) mayor = max(a, b, c) Escribir(“El número mayor es “, mayor) Fin Algoritmo

Método Numero

max (Numero num1, Numero num2, Numero num3)

Encabezado

num_max = num1 Si num2 > num_max Entonces

Fin Si

num_max = num2 Si num3 > num_max Entonces

Cuerpo

Fin Si

num_max = num3 Retornar num_max Fin Metodo

Fig. 2 Ejemplo – Algoritmo para encontrar el mayor de tres números.

Ejemplo de la vida real: Para ilustrar el concepto de método tomaremos como ejemplo una práctica cotidiana de la vida real, como es el proceso de aceleración de un vehículo. La forma de invocar este método sería ejerciendo presión sobre el pedal de aceleración. Un ejemplo de parámetro en este caso, sería la cantidad de aceleración que se requiere, información adicional que es proporcionada por la persona que presiona el acelerador, dependiendo de si lo presiona sólo ligeramente o con fuerza.

1.02.04 Invocación de un método. Si bien es necesario declarar un método, esto solo es parte de un proceso, pues es necesario invocarlo para poder acceder a su funcionalidad. Por lo que, el concepto de invocar un método hace referencia a la acción de llamar a un método para que éste se ejecute. Este llamado o invocado generalmente es realizado desde el interior de otro método y cuando el método invocado termina su ejecución, puede devolver o retornar un resultado o simplemente restituir el control de ejecución al método desde

el cual fue invocado. Cuando un método es invocado es necesario proporcionarle un valor para cada uno de los parámetros del método, a estos valores proporcionados en la invocación se los conoce como argumentos.

Página 13

Fundamentos de Programación I

Un claro ejemplo de invocación de un método lo podemos encontrar en la Fig. 2, en donde, en la línea mayor = max(a, b, c),

podemos apreciar cómo se está llamando al método max. Los argumentos en

esta invocación corresponden a los valores almacenados en las variables a, b y c, que fueron ingresados anteriormente por el usuario. El valor proporcionado para cada argumento será asignado a cada parámetro definido para el método max, por lo que, el valor del argumento a en la invocación del método será asignado al parámetro num1, el valor del argumento b será asignado al parámetro num2, y el valor del argumento c será asignado al parámetro num3. Algoritmo Algoritmo numero_mayor Escribir(“Ingrese 3 números: “) Leer(a, b, c) Invocación del método

mayor = max(a, b, c)

Escribir(“El número mayor es “, mayor) Fin Algoritmo

Método Numero

max (Numero num1, Numero num2, Numero num3)

num_max = num1 Si num2 > num_max Entonces

Fin Si

num_max = num2 Si num3 > num_max Entonces

Fin Si

num_max = num3 Retornar num_max Fin Metodo

Fig. 2 Ejemplo – Algoritmo para encontrar el mayor de tres números.

Ejemplo de la vida real: Una analogía tomada de la vida real para esta situación sería por ejemplo, la gestión jerárquica del trabajo dentro de una empresa manufacturera. En éste contexto, el jefe departamental (en programación representaría el método que invoca) solicita a un obrero (el método que es invocado) realizar una tarea e informar su resultado luego de que la haya terminado (retorno). El jefe no necesita saber la forma en que el obrero ejecutó la tarea asignada, ya que el obrero pudo haber llamado por ejemplo a otros obreros (invocar otros métodos) sin que el jefe se haya enterado. Igualmente, dentro del contexto de PROGRAMACIÓN, existe una relación jerárquica entre los diferentes métodos que componen un programa, de tal forma que el programa divide sus tareas entre varios métodos, en donde, cada método se encarga de realizar subtareas y de sus detalles de implementación propios.

Página 14

Fundamentos de Programación I

Ejemplo de la vida real: Asumiendo la existencia de un método para el registro de un depósito de dinero en una cuenta bancaria, es probable que cuando se invoque a este método se le deba proporcionar el número de cuenta y el monto del depósito como argumentos.

1.02.05 Almacenamiento en memoria de los argumentos. Es importante tener en cuenta que un argumento puede consistir ya sea en un valor concreto o en una variable. En caso de usar una variable como argumento, el nombre de dicha variable puede ser el mismo o puede ser diferente al nombre del parámetro, como se pudo observar en el ejemplo anteriormente citado. Esto se debe a que tanto el argumento como el correspondiente parámetro se almacenan como variables separadas en la memoria de la computadora, tal como se muestra en la Fig. 4.

Fig. 4 Almacenamiento en memoria de los argumentos y parámetros luego de invocar al método max().

Es sumamente transcendental que el orden, el número y el tipo de dato de los valores o variables proporcionados como argumentos en la invocación de un método, deban corresponder exactamente a la lista de parámetros en la declaración del método. Para ver un resumen de lo hasta ahora analizado, le recomendamos visitar el siguiente enlace.

1.03 EL ÁMBITO DE LAS VARIABLES EN UN MÉTODO. Las variables que corresponden a los parámetros de un método pueden ser referenciadas exclusivamente dentro del mismo, ya que son creadas en una sección específica de la memoria inmediatamente después de haber sido invocado y coexistirán únicamente durante su ejecución, lo que significa que, luego de que la última instrucción es ejecutada, sus parámetros ya no podrán ser referenciados y serán borrados de la memoria.

Página 15

Fundamentos de Programación I

Por ejemplo, las variables parámetro del método max

max

(Fig. 2) se crean en memoria en el momento en que

es invocado, y se borrarán luego de que la última instrucción del método (Retornar num_max) se haya

ejecutado. Lo mismo ocurrirá con las variables declaradas en el cuerpo del método (p.e., num_max).

Algoritmo Algoritmo numero_mayor Escribir(“Ingrese 3 números: “) Leer(a, b, c) Creación en memoria de las mayor = max(a, b, c) variables Escribir(“El número mayor es “, mayor) Fin Algoritmo

Método Numero max

(Numero num1, Numero num2, Numero num3)

num_max = num1 Si num2 > num_max Entonces

Fin Si

num_max = num2

Si num3 > num_max Entonces

Fin Si

num_max = num3

Retornar num_max Fin Metodo

Paso previo antes de borrar las variables num1, num2 y num3

Fig. 2 Ejemplo – Algoritmo para encontrar el mayor de tres números.

Una vez que la ejecución del método max haya terminado, el valor almacenado en la variable num_max se retorna y se almacena en la variable mayor del algoritmo principal. La ejecución del algoritmo principal continúa en la instrucción subsiguiente a la invocación del método max, la cual se encarga de mostrar el valor de la variable mayor.

1.03.01. Variables Locales En la Fig. 2, la variable num_max se utiliza únicamente dentro del método max, esto significa que la variable empieza a existir en memoria justo antes de que se ejecute la primera instrucción del método, y es borrada de la memoria inmediatamente después de la ejecución de la última instrucción. Exactamente lo mismo sucede con las variables que actúan como parámetros del método max: num1, num2 y num3. Es por esto que se dice que éstas variables y los parámetros tienen un ámbito local dentro del método. Ningún otro método del algoritmo “conoce” de la existencia de estas variables locales, lo que significa que, ningún otro método puede acceder o cambiar el valor almacenado en esas variables. La única forma en que un método puede comunicar a otro el valor almacenado en una variable local es invocando al otro método y pasando el valor indicado como parámetro (Deitel y Deitel, 2012).

Página 16

Fundamentos de Programación I

Algoritmo Algoritmo numero_mayor Escribir(“Ingrese 3 números: “) Leer(a, b, c) Creación en memoria de las mayor = max(a, b, c) variables. Escribir(“El número mayor es “, mayor) Fin Algoritmo

Método Numero max

(Numero num1, Numero num2, Numero num3)

num_max = num1 Si num2 > num_max Entonces

Fin Si

Creación en memoria de la variable num_max

num_max = num2

Si num3 > num_max Entonces

Fin Si

num_max = num3

Retornar num_max Fin Metodo

Paso previo antes de borrar las variables num1, num2 y num3

Fig. 2 Ejemplo – Algoritmo para encontrar el mayor de tres números.

La Fig. 4 ilustra claramente que las variables locales del algoritmo principal (a, b y c) de la Fig. 2 corresponden a espacios en memoria distintos con respecto a las variables locales del método

max (num1,

num2 y num3).

Fig. 4 Almacenamiento en memoria de los argumentos y parámetros luego de invocar al método max().

Página 17

Fundamentos de Programación I

1.03.02. Variables Globales A diferencia de una variable local, que existe únicamente durante la ejecución de un método, las variables globales existen en memoria desde su declaración hasta que termina la ejecución del programa. Es decir, una variable global es creada en memoria en el momento de su declaración y es borrada después de la ejecución de la última instrucción del programa. Debido a que todos los métodos que conforman el programa pueden acceder y cambiar el valor almacenado en una variable global, ésta se declara fuera del cuerpo de cualquier método. Por lo tanto, una forma simple de comunicación entre métodos consiste en utilizar variables globales, de tal forma que cuando un método quiere comunicar un valor a otro u otros métodos, simplemente asigna un valor específico a la variable global correspondiente, de tal forma que cuando un método acceda a la variable global, le es factible leer el valor asignado por el otro método. A pesar de esta simplicidad, se recomienda evitar el uso de variables globales siempre que sea posible, debido a que su inapropiada utilización suelen conducir a errores sutiles de lógica, los cuales son muy complicados de detectar y posteriormente corregir.

Página 18

Fundamentos de Programación I

ACTIVIDAD1

Siguiendo con este proceso de enseñanza, lo invitamos a revisar el siguiente recurso bibliográfico acompañado de un banco de ejercicios y una actividad lúdica como parte de las actividades programadas en ésta sección. Sección que busca profundizar tanto en temas como en conceptos que podrían ser de su interés y que le serán de gran utilidad mientras se divierte y aprende, dentro de éste proceso de transferencia del conocimiento. El recurso bibliográfico (lectura 1), al igual que el banco de ejercicios 1, los puede encontrar claramente identificados en la sección de lecturas y en la sección de banco de ejercicios respectivamente. 1. Lectura 1: Colombia, U. N. (s.f.). Libros Electrónicos: Departamento de Ingeniería de Sistemas e Industrial.

Obtenido

de

Departamento

de

Ingeniería

de

Sistemas

e

Industrial:

http://dis.unal.edu.co/~programacion/book/modulo4.pdf. – Funciones y Procedimientos. 2. Banco de Ejercicios 1: Para todos los ejercicios propuestos, desarrollar un algoritmo para la solución y expresarlo en pseudocódigo y diagrama de flujo. Además realizar la respectiva prueba de escritorio. 3. Actividad Lúdica 1: Nuevamente lo invitamos a jugar Lightbot, un divertido y emocionante juego de puzzles cuya finalidad es ayudarlo a continuar con la introducción a algunos principios de programación que podrían resultarle bastante complejos mientras cultiva una verdadera comprensión de los conceptos tratados hasta el momento; conceptos esenciales dentro de la informática. Lightbot basa su estrategia de juego en utilizar lógica de programación para resolver los diferentes niveles que lo conforman, en donde, el objetivo a alcanzar en cada nivel es simplemente guiar a un robot e iluminar el azulejo indicado. Dentro de ésta actividad el objetivo a cumplir es, completar todo el NIVEL 2 (PROCEDURES) y los correspondientes 6 subniveles que lo conforman. Página 19

FUNDAMENTOS DE PROGRAMACIÓN I Parte II

BANCO DE EJERCICIOS 1 Para todos los ejercicios propuestos, desarrollar un algoritmo para la solución y expresarlo en pseudocódigo y diagrama de flujo. Además realizar la respectiva prueba de escritorio.

1. Suma de números primos Desarrollar una función que permita ingresar una cadena. Dicha función recibirá como parámetro una cadena que se encontrará conformada por una lista de números separados por comas y retornará como resultado la suma de los números primos de la misma. Se deberá hacer una función adicional para determinar si un número es primo o no. Ejemplo: Entrada: "3, 4, 11, 15, 7, 6" Salida: La suma de los números primos es 3 + 11 + 7 = 2

2. Frase Capitalizada Escribir una función que permita ingresar una cadena. Dicha función recibirá como parámetro una frase cualquiera y retornará la misma frase "Capitalizada", es decir, la misma frase en donde cada palabra comenzará con una letra mayúscula. Para hacer la capitalización de las palabras deberá escribir una función adicional que reciba una palabra como entrada y devuelva la palabra capitalizada.

Página 20

Fundamentos de Programación I

Ejemplo: Entrada: "Este es un ejemplo ejercicio de capitalización de frases" Salida: "Este Es Un Ejercicio De Capitalización De Frases".

3. Transformar número a decimal Escribir una función que permita ingresar una cadena. Dicha función recibirá como parámetro un número hexadecimal (e.g., E7A9) y lo transformará en su equivalente decimal sin importar si la cadena ingresada se encuentra en mayúsculas o en minúsculas. Ejemplo: Entrada: “E7A9” Salida: 59305. Proceso: E7A9 en base 10 es igual a la suma de cada dígito multiplicado por su correspondiente 16n, es decir: E7A916 = 14×(16)3 + 7×(16)2 + 10x(16)1 + 9×(16) 0

= 57344 + 1792 + 160 + 9 = 59305

4. Número perfecto Escriba un programa que lea un número entero positivo n y muestre en pantalla si dicho número es o no perfecto. Utilice 2 funciones para resolver el presente ejercicio, la primera denominada numeroPerfecto, para visualizar en pantalla si el número es o no perfecto y la segunda, denominada esDivisor para indicar si el número es o no divisor de otro número. Esta última deberá ser usada dentro de la primera. Mostrar la salida tal y como se ve en el ejemplo. Ejemplo 1 Entrada: 6 Salida: El número 6 es un número perfecto debido a que la suma de sus divisores (1, 2, 3) es igual a 6. Ejemplo 2 Entrada: 8 Salida: El número 8 no es un número perfecto. Recuerde que, un número perfecto es un entero positivo que es igual a la suma de todos los enteros positivos (excluido él mismo número) que son divisores del número. El primer número perfecto es 6, ya que los divisores de 6 son 1, 2, 3 y 1 + 2 + 3 = 6.

Página 21

Fundamentos de Programación I

5. Serie de Fibonacci Escribir una función que permita al usuario ingresar un número n. Para dicho número elabore un algoritmo que muestre los términos de la serie de Fibonacci que sean menores al número ingresado. Ejemplo: Entrada: 35 Salida: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34.

6. Contar vocales y consonantes Escribir una función que permita ingresar una cadena. Dicha función recibirá como parámetro una frase cualquiera y mostrará en pantalla una a una las pablas que componen la frase, indicando cuantas vocales y cuantas consonantes conforman a la vez cada palabra. Para esto deberá desarrollar las funciones contarVocales y contarConsonantes que reciben una palabra como entrada y devuelven el número de vocales y el número de consonantes de la palabra respectivamente.

Ejemplo Entrada: “Hola Mundo” Salida: Hola: 2 vocales y 2 consonantes Mundo: 2 vocales y 3 consonantes

Escribiendo únicamente el nombre del método.

Página 22

AUT O E V A L U A C I ÓF N 1 u n d a m e n t o s d e P r o g r a m Debes leer y comprender el Módulo 4 ubicado en la Unidad 4a para poder responder a la c Autoevaluación 4 del curso donde encontrarás un cuestionario conformado por 10 Preguntas i cerradas de elección única (Dicotómicas) o de elección múltiple. óCada pregunta consta de un n

enunciado y de 2 o más alternativas de respuesta, así que lea cuidadosamente el enunciado y I seleccione la o las alternativas que corresponden a la respuesta correcta.

A U

2

ARREGLOS Y

MATRICES: ESTRUCTURAS DE DATOS OBJETIVOS ESPECÍFICOS DEL MÓDULO

1. Entender el uso de arreglos. 2. Entender el uso de matrices. 3. Estudiar operaciones de acceso a elementos.

CONTENIDO Introducción 2.1

2.2

Arreglos 2.01.1

Esquema de un arreglo de datos en memoria RAM

2.01.2

Componentes de un arreglo de datos

2.01.3

Arreglos en PSeInt

Matrices 2.02.1

Componentes de una matriz

2.02.2

Matrices en PSeInt

INTRODUCCIÓN En el presente módulo nos centraremos a estudiar las denominadas Estructuras de Datos, las cuales hacen referencia a un conjunto de datos que son del mismo tipo y poseen el mismo nombre, además que pueden ser caracterizados por su organización y por las operaciones que sobre ellas se definen.

Página 27

Fundamentos de Programación I

2.01 ARREGLOS.

2.01.01. Esquema de un arreglo de datos en memoria RAM Un arreglo de datos es un espacio en memoria que permite almacenar una colección de elementos, todos del mismo tipo. Para ilustrar éste concepto, imagine un arreglo como una secuencia contigua de espacios de memoria o casillas (Fig. 5), en donde, en cada una de las casillas se puede almacenar un elemento perteneciente a un conjunto que hace referencia a un mismo tema.

Fig. 5 Esquema de un arreglo de datos en la memoria RAM.

2.01.02. Componentes de un arreglo de datos Como se mencionó anteriormente, la utilidad de un arreglo radica en la posibilidad de en qué en cada casilla que conforma el arreglo se puede almacenar un dato, sin embargo, es necesaria una manera de localizar e identificar al dato dentro del arreglo. Esta localización e identificación es factible gracias al manejo de dos conceptos básicos pero esenciales, el primero denominado elemento, que no es más que cada una de casillas que se pueden utilizar para almacenar un dato, en donde, al número total de elementos que tiene un arreglo se lo conoce como la dimensión del arreglo El segundo concepto involucrado es el llamado índice, el cual permite identificar de manera única a un elemento dentro el arreglo, es decir, cada elemento del arreglo tiene asociado un índice. Se debe tener muy en cuenta que el índice de un arreglo podría comenzar en cero o en uno, dependiendo del lenguaje de programación que se esté utilizando para la codificación (por ejemplo, en C++ y Java comienza en cero).

Fig. 6 Arreglo de dimensión 8 cuyo primer elemento tiene el índice cero.

Página 28

Fundamentos de Programación I

La Fig. 6 muestra un arreglo de dimensión 8 cuyo primer elemento tiene el índice cero y la flecha apunta al elemento de índice 3. Si el lenguaje de programación utilizado para codificar hace referencia al primer elemento con el índice cero y la dimensión del arreglo es N, el último elemento es el elemento N1. Tenga en cuenta que independientemente del lenguaje de programación la dimensión no varía (es decir, siempre es igual al número total de elementos).

2.01.03. Arreglos en PSeInt Para crear un arreglo en PSeInt se utiliza la palabra clave DIMENSION, seguida del nombre del arreglo y su dimensión entre corchetes [ ], tal como se detalla a continuación: Sintaxis: DIMENSION nombre_arreglo[indice]; A pesar de que los arreglos en PSeInt pueden comenzar desde cero o uno, (todo depende de cómo se configure el programa) se recomienda sea desde 0, debido a que muchos de los lenguajes de programación trabajan con arreglos en base 0, cuyos elementos válidos van desde 0 hasta N-1 para un tamaño de arreglo igual a N, lo que permitiría a futuro, una rápida familiarización con respecto al uso de arreglos en múltiples leguajes de programación. Con el objetivo de profundizar lo hasta ahora analizado, en el siguiente

enlace

podrá encontrar un video en

donde se realiza la declaración de un arreglo que permite almacenar un conjunto de datos utilizando PSeInt, mismo que esperamos le sea de gran utilidad y le permita aclarar cualquiera de sus dudas.

2.02 MATRICES.

2.02.01. Componentes de una matriz Una matriz es un conjunto de datos que se disponen en filas y columnas y que contienen elementos de un mismo tipo de datos. También se les conoce como arreglos bidimensionales puesto que en los lenguajes de programación no se hace distinción entre arreglos y matrices sino que se extiende una dimensión más a un arreglo (en realidad es la única diferencia). Por lo que podemos comparar una matriz con una hoja de papel cuadriculado en la que cada celda corresponde a un elemento. Si una matriz tiene m filas y n columnas, decimos que la matriz es de orden o tamaño m x n. Por ejemplo, en la Fig. 7 se muestra una matriz de 3 filas x 4 columnas. Columna 0

Columna 1

Columna 2

Columna 3

Fila 0 Fila 1 Fila 2 Fig. 7 Ejemplo de matriz de tres filas y cuatro columnas.

Página 29

Fundamentos de Programación I

De manera similar que con los arreglos, para referenciar o identificar un elemento de la matriz, se deben de especificar dos subíndices: el primero indica la fila y el segundo la columna. Por ejemplo, en la Fig. 8 se identifican los elementos de la siguiente manera: Columna 0

Columna 1

Fila 0

10

40

Fila 1

20

50

Fila 2

30

60

Identificación de los elementos: En la fila 0 columna 0 el dato es: 10 En la fila 0 columna 1 el dato es: 40 En la fila 1 columna 0 el dato es: 20 En la fila 1 columna 1 el dato es: 50 En la fila 2 columna 0 el dato es: 30 En la fila 2 columna 1 el dato es: 60

Fig. 8 Matriz - Ejemplo de ilustración

2.02.02. Matrices en PSeInt Para crear una matriz en PSeInt se utiliza la palabra clave DIMENSION, seguida del nombre con el que se identificará a la matriz y su dimensión entre corchetes [filas, columnas], tal como se detalla a continuación:

Sintaxis: DIMENSION nombre_matriz [filas, columnas]; Con el objetivo de profundizar lo hasta ahora analizado, en el siguiente enlace podrá encontrar un video en donde se retoma y razona acerca del uso de matrices utilizando la herramienta PSeInt, mismo que esperamos le sea de gran utilidad y le permita aclarar cualquiera de sus posibles dudas.

Página 30

Fundamentos de Programación I

ACTIVIDAD2

Siguiendo con este proceso de enseñanza, lo invitamos a revisar el siguiente recurso bibliográfico acompañado de un banco de ejercicios y el subsecuente material audiovisual, como parte de las actividades programadas en éste punto. Actividades que le permitirán profundizar tanto en temas como en conceptos que podrían ser de su interés y que le serán de gran utilidad dentro de este proceso de aprendizaje. El material audiovisual está conformado por un conjunto de 3 video ejemplos, en donde, cada video aborda una temática diferente y específica. Durante la reproducción de los mismos, está en total libertad de pausar, retroceder o simplemente proseguir con la reproducción del material audiovisual, lo importante es que cada video le ayude a despejar cualquier inquietud en cuanto a la temática analizada hasta el momento. 1. Lectura 2: Colombia, U. N. (s.f.). Libros Electrónicos: Departamento de Ingeniería de Sistemas e Industrial.

Obtenido

de

Departamento

de

Ingeniería

de

Sistemas

e

Industrial:

http://dis.unal.edu.co/~programacion/book/modulo3.pdf. – Arreglos y Matrices. 2. Banco de Ejercicios 2: Para todos los ejercicios propuestos, desarrollar un algoritmo para la solución y expresarlo en pseudocódigo y diagrama de flujo. Además realizar la respectiva prueba de escritorio. 3. Video Ejemplo 1 - Creación de dos arreglos utilizando PSeInt, el primero permitirá almacenar dos nombres

y

el

segundo

permitirá

almacenar

3

números:

https://www.youtube.com/embed/lvcZ2pDR_Yg

Página 31

Fundamentos de Programación I

4. Video Ejemplo 2 - Creación de dos arreglos utilizando PSeInt, el primero permitirá almacenará n nombres

de

personas

y

el

segundo

permitirá

almacenar

n

números:

https://www.youtube.com/embed/j5GRFTjq2O4 5. Video Ejemplo 3 - Creación de una matriz de n filas x n columnas con números que el usuario desee, utilizando PSeint y posteriormente sumar todos los números de la primera columna: https://www.youtube.com/embed/CCKwAEl82eU

Página 32

FUNDAMENTOS DE PROGRAMACIÓN I Parte II

BANCO DE EJERCICIOS 2 Para todos los ejercicios propuestos, desarrollar un algoritmo para la solución y expresarlo en pseudocódigo y diagrama de flujo. Además realizar la respectiva prueba de escritorio.

1. Operaciones con vectores Un vector en un espacio tridimensional es una tripleta de valores reales (x, y, z). Deseamos desarrollar un programa que permita operar con dos vectores, para lo cual el usuario visualizará en pantalla un menú con las siguientes opciones: 1.

Introducir el primer vector

2.

Introducir el segundo vector

3.

Calcular la suma

4.

Calcular la diferencia

5.

Calcular el producto escalar

6.

Calcular el producto vectorial

7.

Calcular el ángulo (en grados) entre ellos

8.

Calcular la longitud

9.

Finalizar

Consideraciones: •

Tras la ejecución de cada una de las acciones del menú, éste deberá de reaparecer en pantalla, a menos que la opción seleccionada sea la número 9.

Página 33

Fundamentos de Programación I

•

Si el usuario selecciona una opción diferente a las alternativas mostradas, el programa advertirá al usuario de su error y el menú reaparecerá.

•

Las opciones 4, 6 y 8 del menú pueden proporcionar resultados distintos en función del orden de los operandos, por lo que, si se selecciona cualquiera de éstas opciones, deberá mostrarse un nuevo menú que permita seleccionar el orden de los operandos. Por ejemplo, la opción 4 mostrará el siguiente menú: 1.

Primer vector menos segundo vector

2.

Segundo vector menos primer vector

Nuevamente, si el usuario se equivoca, se le advertirá del error y se le permitirá corregirlo. •

La opción 8 del menú principal conducirá también a un submenú para que el usuario decida sobre cuál de los dos vectores se aplica el cálculo de longitud.

Tenga en cuenta que el programa deberá de contemplar y controlar toda posible situación excepcional: divisiones para cero, raíces con argumento negativo, etcétera. En caso de que necesite recordar algunos conceptos referentes a los cálculos a realizar, lo invitamos a revisar la siguiente tabla: Operación

Cálculo

Suma: (x1, y1, z1) + (x2, y2, z2)

(x1+x2, y1+y2, z1+z2)

Diferencia: (x1, y1, z1) - (x2, y2, z2)

(x1-x2, y1-y2, z1-z2)

Producto escalar: (x1, y1, z1) . (x2, y2, z2)

x1x2 + y1y2 + z1z2

Producto vectorial: (x1, y1, z1) x (x2, y2, z2)

y1z2 - z1y2, z1x2-x1z2, x1y2-y1x2

Angulo entre (x1, y1, z1) , (x2, y2, z2) Longitud de (x, y, z) Tabla 1: Recordatorio de operaciones básicas con vectores

Nota: La función arco coseno se encuentra disponible en el módulo math y su identificador es acos.

Página 34

Fundamentos de Programación I

2. Operaciones con Matrices Se tiene una matriz de 5 filas por 5 columnas (matriz cuadrada), rellenarla de la siguiente manera: a.

b.

c.

Diagonal 1 1 2 3 4 5

1 2 3 4 0

1 2 3 0 0

1 2 0 0 0

1 0 0 0 0

0 0 0 0 5

0 0 0 4 5

0 0 3 4 5

0 2 3 4 5

1 2 3 4 5

Diagonal 2

Diagonal 3 1

1 2

2 3

4 5 d.

4 5

Dada una matriz cuadrada, mostrar su matriz transpuesta:

3. Ejercicios Prácticos Con la ayuda de la herramienta PSeInt desarrollar el siguiente conjunto de ejercicios planteados: a.

Crear un arreglo llamado num que almacene los siguientes datos: 20, 14, 8, 0, 5, 19 y 24.

b.

Crear un arreglo llamado num que almacene los siguientes datos: 20, 14, 8, 0, 5, 19 y 24, posteriormente mostrar todos los datos con un sólo mensaje utilizando la estructura de repetición PARA.

c.

Crear un arreglo de 5 posiciones y llenarlo con los números que el usuario desee.

d.

Crear un arreglo de n posiciones y llenarlo con nombres de personas.

e.

Crear un arreglo de n posiciones y llenarlo con los números que el usuario desee.

f.

Crear dos arreglos uno que almacene 2 nombres y otro que almacene 3 números.

Página 35

Fundamentos de Programación I

g.

Sumar todos los elementos de un arreglo de tamaño n (utilizar un acumulador).

h.

Sumar los elementos de dos vectores y guardar el resultado en otro vector.

i.

Llenar un vector de 10 posiciones con números aleatorios entre 1 y 100 (utilizar la función Azar).

j.

Llenar un vector con números enteros (números positivos y negativos) y posteriormente mostrar la cantidad de números positivos que hay en dicho arreglo.

k.

Almacenar en un arreglo de n posiciones nombres de países, a continuación implementar una opción que al digitar una posición muestre el dato que contiene.

l. m.

Crear una matriz 2x2 que almacene los siguientes valores: 10, 20, 30, 40. Crear una matriz de n filas y n columnas, en donde le es permitido al usuario llenar la matriz con los números que desee.

n.

Crear una matriz n x n y llenarla con los números que el usuario desee. Sumar todos los números que conformen la columna 1.

o.

Llenar una matriz de 3 x 3 completamente de números aleatorios entre 0 y 9 (utilizar la función Azar).

4. Ejercicios Complementarios Deitel, P. J., & Deitel, H. M. (2012). Java: How to Program (9a ed.). Upper Saddle River, N.J: Prentice

Hall. – Ejercicios del Capítulo 7: Arrays and ArrayLists.

Página 36 Fundamentos de Programación I

AUTOEVALUACIÓN2

Debes leer y comprender el Módulo 4 ubicado en la Unidad 4 para poder responder a la Autoevaluación 4 del curso donde encontrarás un cuestionario conformado por 10 Preguntas cerradas de elección única (Dicotómicas) o de elección múltiple. Cada pregunta consta de un enunciado y de 2 o más alternativas de respuesta, así que lea cuidadosamente el enunciado y seleccione la o las alternativas que corresponden a la respuesta correcta.

3

BÚSQUEDAS Y

ORDENAMIENTOS: EN ESTRUCTURAS DE DATOS

OBJETIVOS ESPECÍFICOS DEL MÓDULO 1. Introducir los conceptos más importantes relacionados con el ordenamiento y las búsquedas básicas dentro de una estructura de datos. 2. Conocer los algoritmos de ordenamiento y búsquedas básicas basados en el intercambio de elementos. 3. Analizar la eficiencia de los métodos de ordenamiento y búsqueda.

CONTENIDO Introducción 3.1

3.2

Búsquedas 3.01.1

Porqué son importantes las búsquedas

3.01.2

Algoritmos de búsqueda

3.01.3

Análisis de los algoritmos de búsqueda

Ordenamientos 3.02.1

¿Qué es ordenar?

3.02.02 Algoritmos de ordenamiento 3.02.03 Análisis de los métodos de ordenamiento

Página 42

Fundamentos de Programación I

INTRODUCCIÓN Muchas actividades humanas requieren que en ellas, las diferentes colecciones de elementos utilizados se ubiquen en un orden determinado, por ejemplo, las oficinas de correo y las empresas de mensajería proceden a disponer en un orden en específico las cartas y los paquetes recibidos, este ordenamiento suele estar definido de acuerdo a una serie de códigos postales, lo que permite un almacenamiento y una posterior entrega eficiente tanto de sobres como de paquetes. De igual manera, los estudiantes en una clase se ordenan por sus apellidos y nombres, permitiendo al docente buscar e identificar rápidamente a un alumno en específico dentro de dicha lista, un criterio que de manera similar es utilizado al momento de ordenar a los abonados del servicio telefónico dentro de un directorio; así como este ejemplo, podemos encontrar incontables ejemplos más dentro de nuestra vida cotidiana, en donde, sin siquiera habernos percatado, es inevitable que la información se encuentre ordenada en base a un criterio. Por tal motivo, una de las tareas que más frecuentemente realizan las computadoras en el procesamiento de datos es el ordenamiento y la búsqueda. El estudio de diferentes métodos de ordenamiento y búsqueda es una tarea intrínsecamente interesante desde un punto de vista teórico y, naturalmente, práctico, por lo que en el presente módulo presentaremos los conceptos más importantes relacionados con los ordenamientos y las búsquedas básicas en estructuras de datos, sus algoritmos y su eficiencia a través de una serie de videos, actividades y una autoevaluación.

Considerando a los métodos de ordenamiento como la distribución de una serie de elementos en base a una regla específica y a la búsqueda, como la localización de un elemento en específico dentro de un conjunto, siendo en ambos casos, métodos o algoritmos desarrollados para ser ejecutados únicamente en la memoria principal del computador.

Página 43

Fundamentos de Programación I

3.01 BÚSQUEDAS.

3.01.01. Porqué son importantes las búsquedas Uno de los usos más frecuentes de los computadores es la búsqueda de información dentro de estructuras de datos (i.e., arreglos), en donde, la eficiencia de la búsqueda está directamente relacionada con respecto a si la estructura sobre la que se realiza la exploración de un elemento está o no ordenada. Por ejemplo, al tomar un diccionario y realizar la búsqueda de la palabra MUNDO, lo más probable es que inicialmente se deba comenzar por buscar la sección que contiene el conjunto de palabras que comienzan con la letra M, posteriormente, se deberá proceder a

buscar la siguiente letra de la palabra (U en este caso), luego la letra N, y así sucesivamente hasta encontrar la palabra completa. Esto es factible debido a que el diccionario se encuentra alfabéticamente ordenado, caso contrario, habría que examinar cada una de las hojas, recorriendo cada una de las palabras que se hallarían en cada hoja, hasta encontrar la palabra buscada. Esto sin duda conllevaría muchísimo más tiempo y resultaría en una labor sumamente extenuante y casi interminable, tan solo por el hecho de que el diccionario no está ordenado. Tomando como referencia el par de ejemplos expuestos anteriormente y en base a la lógica aplicada individualmente en cada caso, podemos mencionar que dentro del presente módulo se estudiarán dos tipos de búsquedas. El primer caso (búsqueda en un diccionario ordenado) corresponde a una búsqueda binaria y en el segundo caso (búsqueda en un diccionario desordenado) corresponde a una búsqueda secuencial.

3.01.02. Algoritmos de búsqueda: búsqueda lineal y búsqueda binaria Con mucha frecuencia los desarrolladores de software trabajan con grandes cantidades de datos almacenados en arreglos localizados en memoria y suelen necesitar conocer si dicho arreglo contiene un elemento específico que coincida con un valor buscado (valor clave). A éste proceso de encontrar un elemento específico dentro de un arreglo se denomina búsqueda. En esta sección se examinarán dos técnicas ampliamente utilizadas que permitirán realizar la búsqueda de elementos almacenados en una estructura de datos localizada en la memoria principal del computador: la primera, llamada búsqueda lineal o secuencial, que es la técnica más sencilla, y la segunda, denominada búsqueda binaria o dicotómica, que en cambio corresponde a la técnica más eficiente.

Página 44

Fundamentos de Programación I

3.01.02.01. Búsqueda lineal o búsqueda secuencial En una búsqueda secuencial los elementos de un arreglo se exploran de forma lineal o secuencial como su nombre lo indica, para lo cual, se analiza un elemento a continuación de otro dentro de una lista, en busca de un elemento específico que coincida con un valor buscado denominado clave. Es decir, un algoritmo básico de búsqueda secuencial consiste en empezar desde el inicio de la estructura e ir a través de cada elemento hasta encontrar el valor buscado, o hasta llegar al final del arreglo.

Este algoritmo de búsqueda secuencial compara cada elemento del arreglo con la clave de búsqueda, pero debido a que el arreglo no está en un orden determinado, es probable que el elemento a buscar pueda ser el primero, el último, cualquier otro elemento o simplemente no encontrarse presente dentro de la estructura. A continuación (Fig. 9) se describe el uso del algoritmo de búsqueda secuencial, dentro de un contexto en el que se tiene un arreglo de 5 elementos, los cuales no disponen un orden específico y el valor buscado es el elemento con valor igual a 10. Pseudocódigo Algoritmo busqueda_lineal Dimension arreglo[10] arreglo[0]=2 arreglo[1]=5 arreglo[2]=4 arreglo[3]=10 arreglo[4]=1 buscado=10

i=0 encontrado=Falso Mientras encontrado == Falso y i Sn Descendente Los datos ordenados ofrecen la ventaja de que son mucho más fáciles de encontrar, lo que conlleva menos operaciones y por lo tanto menos tiempo de búsqueda. Para ordenar los datos, existen una serie de algoritmos que, dependiendo de la estrategia a utilizar, servirán en mayor o menor grado al momento de organizar los datos, a estas estrategias de ordenamiento se las denomina algoritmos de ordenamiento. Entre las principales estrategias o algoritmos de ordenamiento tenemos: burbuja, inserción y selección, en donde, dentro de este contexto, el que un algoritmo sea ingenioso significa que va a intentar ordenar un conjunto desorganizado de datos haciendo uso del menor número de comparaciones posible.

3.02.02. Algoritmos de ordenamiento: Inserción, selección y burbuja 3.02.02.01 Algoritmo de ordenamiento por inserción El método de ordenamiento por inserción es similar al proceso típico de organizar en orden alfabético dentro de un tarjetero un conjunto de tarjetas de presentación u organizar un juego de naipes por color del palo y valor del naipe, es decir, el ordenamiento por inserción consiste en insertar en una lista o archivo previamente ordenado, un dato en una posición específica dependiendo de su valor y de un criterio de ordenamiento. La estrategia utilizada por el algoritmo de ordenamiento por inserción es: 1. Se toma el primer elemento del arreglo, como el primer elemento de lo que llamaremos el arreglo ordenado. 2. Se toma el próximo número del arreglo y se compara con los elementos del arreglo ordenado, hasta encontrar su posición. 3. Se repite el proceso para todos los elementos del arreglo. A continuación (Fig. 11), se describe el uso del algoritmo de ordenamiento por inserción.

Página 50

Fundamentos de Programación I

Pseudocódigo Proceso Ordenamiento_Insercion n