Programación Lógica M.3 Resumen

Módulo III
Programación Lógica
1.Arreglos Unidimensionales
Una estructura de datos es una colección de datos organizados para usarse eficientemente,
son muy importantes. Pueden ser simples y estructurados
Los datos estructurados se clasifican en estáticos y dinámicos, los estáticos la memoria se
gestiona en tiempo de compilación y las estructuras dinámicas se gestionan en tiempo de
ejecución. Ambos tipos existen en los lenguajes reales.
Una estructura de datos estática es un arreglo y representa un conjunto finito, ordenado y
homogéneo de elementos. Estos pueden ser unidimensionales (vectores), bidimensionales
(matrices) o multidimensionales. Cada arreglo tiene su identificador y cada elemento del
arreglo se identifica por la posición que ocupa, a través de índices. Los arreglos se utilizan
cuando es necesario manipular varios valores como parte de un conjunto. Estos vectores se
pueden representar gráficamente, abajo un ejemplo dónde el arreglo se llama datos con 4
elementos.
El número de elementos se llama rango del vector, este vector llamado datos es de rango 4.
Los arreglos pueden contener datos numéricos y no numéricos. El rango se debe indicar
previamente a su uso dentro de un programa y en pseudocódigo se declara así:
Algoritmo declaración_arreglo
tipo
array [límite inferior…límite superior] de <tipo de dato>:<nombre estructura arrelgo>
var
<nombre estructura arreglo>:<nombre variable de tipo de arreglo>
inicio
…
Hay una sección llamada tipo en dónde se declaran las estructuras de datos de arreglos y
otros tipos de datos definidos por el usuario. Se usa la palabra array seguido de un par de
corchetes con el rango del arreglo donde se pone el límite inferior y superior (el primer y
último número), seguido de esto se coloca el tipo de datos de los elementos del arreglo y el
nombre. Luego hay que declarar la variable que contendrá el arreglo.
Ejemplo de un arreglo
Algoritmo declaración_arreglo
tipo
array [1…4] de entero: arreglo_enteros
var
arreglo_enteros:datos
inicio…
Cada elemento del vector se puede procesar como si fuera una variable simple. Por ejemplo
datos[4] ← 8 almacena el valor entero 8 en el vector datos, en la posición 4.
Se pueden crear dos vectores distintos pero con la misma estructura, ejemplo
…
tipo
array [1…10] de entero: lista
var
lista: origen, destino
inicio
…
Ahí se declararon dos arreglos distintos llamados origen y destino, de tipo de dato lista (el
arreglo es un tipo de dato que creamos, dónde las variables pueden ser de ese tipo). El
límite inferior no siempre tiene que iniciar en 1, puede ser de 0 a 3 (y serán 4 los elementos
para ingresar valores, el rango seguirá siendo de 4).
Las operaciones que pueden realizarse con vectores son:

● Asignación
● lectura/escritura
● recorrido
● ordenamiento
● búsqueda
Las operaciones de lectura y escritura de los elementos de un arreglo lineal se realizan con
estructuras repetitivas. Si se desea mostrar por pantalla el contenido de todo un arreglo se
usará desde/hasta (un índice hasta el rango del arreglo) y hacer un leer los datos y luego
escribirlos.
2.Arreglos Bidimensionales
Existen escenarios en los que la información es mejor organizarla en forma de matriz con
dos subíndices: uno para las filas y otro para las columnas. Un arreglo bidimensional es un
vector de vectores.
Cada elemento de un arreglo bidimensional se utiliza

con un mismo nombre y dos subíndices. En notación estándar el primer subíndice hacer
regerencia a las filas y el segundo a las columnas. si el arreglo de la figura 2 se llama tabla
entonces tabla[2,3] = 1. Estos arreglos bidimensionales se declaran de la siguiente forma
Algoritmo declaración_arreglo_bidimensional
tipo
array [límite inferior filas… límite superior filas] [límite inferior columnas… límite
superior columnas] de <tipo de dato>: <nombre estructura arreglo>
var
<nombre estructura arreglo>: <nombre variable de tipo arreglo>
inicio
….
Ejemplo
Para recorrer arreglos
bidimensionales, es necesario tener
dos estructuras repetitivas
anidadas, generalmente se utiliza la
estructura desde/fin-desde. Si se
quiere leer datos desde el teclado y
luego recorrerlo para mostrar los
elementos en pantalla se puede
utilizar el siguiente pseudocódigo.
Algoritmo recorrer_arreglo_bidimensional
tipo
array [1…5][1…3] de entero:lista
var
lista:notas
entero: i, j
inicio
//cargamos el arreglo
desde i ← hasta 5 hacer
desde j ← 1 hasta 3 hacer
leer (notas[i,j])
fin-desde
fin-desde
// recorremos y mostramos cada elemento

desde i ← hasta 5 hacer
desde j ← 1 hasta 3 hacer
mostrar(notas[i,j])
fin-desde
fin-desde
fin
La estructura repetitiva externa recorre las filas y para cada una de ellas la estructura
interna recorre cada una de las columnas.
3.Algoritmos de ordenamiento
Ordenamiento por algoritmo de burbuja

La estrategia del método de ordenamiento por burbuja tiene su base en la comparación de
pares de elementos adyacentes e intercambiarlos entre sí. Suponiendo que se desea
ordenar un arreglo unidimensional por este método, entonces se deben recorrer sus
elementos, se comparan de a pares en forma adyacente y se intercambian hasta llegar al
final del arreglo. Esto se repite hasta que esté todo ordenado.
Suponiendo un arreglo unidimensional X de N, el pseudocódigo sería así.
para i← 1 hasta N-1 hacer

para j ← 1 hasta N-1 hacer
si X[j] > X[j+1] entonces
//intercambiamos
AUX ← X[j]
X[j] ← X[j+1]
X[j+1] ← AUX
fin-si
fin-para
fin-para
3.2 Ordenamiento por algoritmo de burbuja mejorada
La cantidad de comparaciones que se realizan utilizando el algoritmo burbuja se puede

reducir si modificamos algo. Si se ordena crecientemente un arreglo unidimensional
utilizando el método de burbuja, cuando se termina el recorrido el elemento más grande se
posiciona al final del arreglo y no hace falta compararlo otra vez, para solo comparar los
elementos desordenados se utiliza este método.
para i ← 1 hasta N-1 hacer

para j←1 hasta N-i hacer
si X[j] > x[j+1] entonces
//intercambiar
AUX ← X[j]
X[j] ← X[j+1]
X[j+1] ← AUX
fin-si
fin-para
fin-para
3.3 Ordenamiento por algoritmo de inserción
Este método de ordenamiento consiste en tomar un elemento del conjunto e insertarlo en

una parte ya ordenada. Se debe repetir este procedimiento para el resto de elementos
desordenados.
para i ← 2 hasta N hacer

AUX ← X[i]
k←i-1
sw ← falso
mientras NO(sw) y (K>=1) hacer
si AUX < X[k] entonces
X[k+1] ← X[k]
k ← k-1
sino
sw ← verdadero
fin-si
fin-mientras
X[k+1] ← AUX
fin-para
3.4 Ordenamiento por algoritmo de selección
Suponiendo que se desea ordenar un arreglo unidimensional en forma creciente, el método

de ordenamiento por selección consiste en recorrer el arreglo para buscar el menor
elemento e intercambiarlo con el primero. A continuación se debe recorrer nuevamente el
arreglo para buscar el segundo menor elemento e intercambiarlo con el elemento de
segunda posición y así hasta que el algoritmo se encuentre ordenado.
para i ← hasta N-1 hacer

AUX ← X[i]
k←i
para j ← i + 1 hasta N hacer
si X[j] < AUX entonces
AUX ← X[j]
k←j
fin-si
fin-para
X[k] ← X[i]
X[i] ← AUX
fin-para
4. Búsqueda secuencial
Existen distintos algoritmos que pueden ser utilizados para buscar un elemento y su
elección dependerá de cómo estén organizados los elementos.
El algoritmo de búsqueda secuencial es utilizado cuando los elementos del conjunto no se

encuentran ordenados. Este algoritmo consiste en recorrer la estructura de datos para
comparar cada uno de los elementos con el valor que se desea buscar.
leer(k)
para i ← 1 hasta N hacer
si A[i] == k entonces
escribir(“Elemento encontrado en la posición”, i)
fin-si
fin-para
Cada vez que se encuentre el valor K en el arreglo A se mostrará un mensaje indicando la
posición.
4.2 Búsqueda binaria
La búsqueda secuencial puede resultar muy lenta si el número de elementos del conjunto
es grande. La búsqueda binaria es mucho más rápida pero se necesita que los elementos
estén ordenados. Se compara el elemento central del arreglo, si es ese, se finaliza la
búsqueda; y si no lo es se debe verificar si el valor que se busca es más chico que el
central, si lo es se busca en la primera o segunda parte del arreglo dependiendo cómo esté
ordenado. Se debe repetir el proceso de comparación con el resto de la sublista de
elementos, hasta determinar la existencia del valor.
leer (k)
BAJO ← 1
ALTO ← N
CENTRAL ← (BAJO + ALTO) div 2
mientras (BAJO<=ALTO) Y ( X[CENTRAL] <> K) hacer
si K < X [CENTRAL] entonces
ALTO ← CENTRAL - 1
si-no
BAJO ← CENTRAL + 1
fin-si
CENTRAL ← (BAJO + ALTO) div 2
fin-mientras
si K == X [CENTRAL] entonces
escribir (“Valor encontrado en la posición”, CENTRAL)
fin-si
En el peor de los casos se necesitarán log2(N+1) comparaciones y en el mejor de los casos

se realizará 1 comparación. Por lo tanto el método de búsqueda binaria necesita en
promedio la siguiente cantidad de comparaciones para encontrar un elemento:
1+log2(N +
1)

Programación Lógica M.3 Resumen

Cargado por

Copyright:

Formatos disponibles

Programación Lógica M.3 Resumen

Cargado por

Información del documento

Descripción original:

Derechos de autor

Formatos disponibles

Compartir este documento

Compartir o incrustar documentos

Opciones para compartir

¿Le pareció útil este documento?

¿Este contenido es inapropiado?

Copyright:

Formatos disponibles

Programación Lógica M.3 Resumen

Cargado por

Copyright:

Formatos disponibles

Módulo III

Las operaciones que pueden realizarse con vectores son:

Cada elemento de un arreglo bidimensional se utiliza

// recorremos y mostramos cada elemento

Ordenamiento por algoritmo de burbuja

Suponiendo un arreglo unidimensional X de N, el pseudocódigo sería así.

para i← 1 hasta N-1 hacer

3.2 Ordenamiento por algoritmo de burbuja mejorada

La cantidad de comparaciones que se realizan utilizando el algoritmo burbuja se puede

para i ← 1 hasta N-1 hacer

3.3 Ordenamiento por algoritmo de inserción

Este método de ordenamiento consiste en tomar un elemento del conjunto e insertarlo en

para i ← 2 hasta N hacer

3.4 Ordenamiento por algoritmo de selección

Suponiendo que se desea ordenar un arreglo unidimensional en forma creciente, el método

para i ← hasta N-1 hacer

El algoritmo de búsqueda secuencial es utilizado cuando los elementos del conjunto no se

4.2 Búsqueda binaria

En el peor de los casos se necesitarán log2(N+1) comparaciones y en el mejor de los casos

También podría gustarte