Algoritmia II

Curso: Lógica y Representación II
ANÁLISIS DE ALGORITMOS
Cuando se dice que un problema tiene solución, significa que existe un algoritmo
susceptible de implantarse en una computadora, capaz de producir la respuesta correcta
para cualquier instancia del problema en cuestión. Para ciertos problemas es posible
encontrar más de un algoritmo para resolverlos, lo que conlleva a tener que seleccionar
el mejor de ellos, de acuerdo a ciertos criterios.
Entre los principales criterios que se deben de tener en cuenta cuando se evalúa una
solución algorítmica, se encuentran los siguientes:
1. Que sea fácil de entender, implementar, depurar y mantener
2. Que se encuentre bien documentado
3. Que pueda ser usado por otros algoritmos
4. Que sea eficiente con respecto a los recursos que utiliza. La eficiencia
computacional de un algoritmo está relacionada principalmente con el tiempo
que demora su ejecución y el espacio que gasta en memoria, siendo el primero,
por lo general, el más importante.
Cuando se diseña una solución algorítmica para un programa que se va a usar con poca
frecuencia, no se justifica escoger entre varias soluciones, la más eficiente con respecto
a los recursos, sólo se tendrían en cuenta los primeros tres criterios. En caso contrario,
si el programa se va a utilizar con periodicidad, se justifica escoger entre varias
soluciones encontradas la que sea más eficiente con respecto al uso de los recursos. De
todos modos, ninguno de los criterios de evaluación debe eliminarse por completo. Por
ejemplo, si se selecciona una solución muy eficiente pero muy difícil de entender, puede
suceder que después no sea posible darle el mantenimiento adecuado.
Se han definido tres enfoques para seleccionar la mejor solución algorítmica para un
mismo problema:
- El enfoque empírico (a posteriori): consiste en implementar cada una de las
soluciones algorítmicas y medir los tiempos reales obtenidos de cada una de
ellas.
- El enfoque teórico (a priori): consiste en encontrar en forma matemática la
cantidad de recursos necesarios para cada una de las soluciones algorítmicas
como una función del tamaño de los casos considerados.
- El enfoque híbrido: consiste en determinar en forma teórica las funciones que
describen la eficiencia de las diferentes soluciones algorítmicas para luego
encontrar en forma empírica aquellos parámetros numéricos que sean
específicos a cada una soluciones.
Medición del tiempo de ejecución de un Programa:

La eficiencia, o lo que se denomina la complejidad de una solución algorítmica se
define como el número de operaciones básicas requeridas por el algoritmo para procesar
una entrada de cierto tamaño. La complejidad de una solución algorítmica, se determina
a partir de los recursos que dicha solución necesita para su ejecución, y se denota por
T(n).
Se han definido dos tipos de complejidad:
- Complejidad temporal: Indica la cantidad de tiempo que requiere un algoritmo

para resolver un problema de tamaño n; ya que un algoritmo no se puede
ejecutar para medir la cantidad de tiempo que consume, la complejidad
temporal no se expresará en unidades de tiempo, sino en términos de la
cantidad de operaciones que realiza.
- Complejidad espacial: Indica la cantidad de espacio que requiere un algoritmo
para resolver un problema de tamaño n.
El tiempo de ejecución de un programa en función de n, no sólo depende de los datos

de entrada, sino del tamaño del problema, independientemente de la calidad del código
generado, de la máquina, etc. en que se vaya a implementar la solución algorítmica.
Para cada problema se determina una medida n de su tamaño. El concepto exacto de lo
que mide n depende de la naturaleza del problema. Por ejemplo, en un método de
ordenamiento se tiene como entrada una lista de elementos para ordenar con el fin de
retornar la lista de elementos ordenados. El tamaño de entrada para este problema es el
número de elementos a ordenar. En algunos casos se indica que el tiempo de ejecución
de un programa es T(n) = cn, en donde c se define como una constante de
proporcionalidad que depende del compilador, la máquina y otros factores.
En general, la cantidad de recursos que consume un algoritmo para resolver un

problema se incrementa conforme crece el tamaño del problema. Dependiendo del
problema en particular, uno o varios de sus parámetros serán elegidos como tamaño del
problema.
Por ejemplo, el tamaño de cada uno de los siguientes problemas es:

- Buscar un elemento en una lista, es el número de elementos de la lista.
- Sumar dos matrices de orden N * M, es 2*(N*M).
- Ordenar un conjunto de valores, es el número de elementos en el conjunto.
Tipos de Medición de T(N):

El tiempo de ejecución de una solución algorítmica se puede obtener de acuerdo a los
siguientes tres enfoques:
- El Peor caso: Se define como el tiempo máximo necesario para resolver un
problema de tamaño n.
- Caso medio: se define como el tiempo medio de todos los casos posibles para un
problema de tamaño n. Se requiere establecer una distribución estadística de la
ocurrencia de cada uno de los casos.
- El Mejor caso: Tiempo mínimo necesario para resolver un problema de tamaño n.
Notación Asintótica (O grande)

Sea f(n) = T(n) el tiempo de ejecución de un algoritmo y f(n) definida en el dominio de
los enteros no negativos. Se dice que f(n) es O(g(n)) si f(n) es una constante de tiempo
g(n), excepto posiblemente para valores pequeños de n. Es decir, f(n) es O(g(n)), si
existe un no y una constante c > 0 tal que para todos los enteres n >= no, se cumple que
f(n) <= c.g(n). Sean g(n) diferentes funciones que identifican la cantidad de recursos
que utiliza un algoritmo, se pretende entonces, encontrar a qué función o "familia"
pertenece un algoritmo, usando como criterio el comportamiento del algoritmo a medida
de N crece. A este comportamiento se le denomina crecimiento asintótico o el Orden de
Magnitud(O grande). Por ejemplo, si se determina que el T(n) de un algoritmo es O(n2)
significa que existen constantes enteras positivas c y no tales que para n mayor o igual a
no se tiene que T(n) <= cn2. En la práctica, se ignoran las constantes y los términos de
menor peso. Por ejemplo, f(n)= 7n3 + 5n2 – 60 = O(n3).
Tipos de Ordenes de Magnitud:

Dado el tiempo de ejecución de un algoritmo en términos de la función f(n), es posible
asignar uno de los siguientes Órdenes de Magnitud a dicho algoritmo:
O(1): Complejidad constante. Es la más eficiente. Resulta de algoritmos que no

contienen ciclos, es decir, si f(n) = constante. Por ejemplo, f(n) = 8
O(logbn): Complejidad logarítmica. Se presentan en algoritmos en donde la función f(n)
es una ecuación logarítmica. Por ejemplo, f(n) = 4log2n – 6.
O(n): Complejidad lineal. Cuando f(n) es una ecuación lineal. Por ejemplo,
f(n)= 5n -12
O(n * logbn): Se presenta en algoritmos en donde la función es una ecuación de la forma
n*logbn. Por ejemplo, f(n) = 3nlog3n– 5.
O(n2): Complejidad cuadrática. Cuando f(n) es una ecuación cuadrática. Por ejemplo,
f(n) = 4n2 + 6n - 2.
O(n3): Complejidad cúbica. Cuando f(n) es una ecuación cúbica. Por ejemplo,
f(n)= 7n3+ 8n2 – 3n- 1.
O(cn), c>1: Complejidad exponencial. Se presenta en algoritmos recursivos.
O(n!): Complejidad factorial.
Para cuando n es lo suficientemente grande, los órdenes de magnitud se pueden ordenar

de acuerdo a la eficiencia, de la siguiente manera:
O(1) > O(logbn) > O(n) > O(n logbn) > O(n2) > O(n3) > O(cn) > O(n!)
Siendo los algoritmos O(1) los más eficientes y los O(n!) los menos eficientes.
La siguiente tabla muestra el comportamiento de las diferentes funciones para diferentes

valores de n.
N O(logbN) O(N) O(N logbN) O(N2) O(N3) O(2N) O(n!)
2 1 2 2 4 8 4 2
4 2 4 8 16 64 16 24
8 3 8 24 64 512 256 40320
16 4 16 64 256 4096 65536 16!
32 5 32 160 1024 32768 232 32!
64 6 64 384 4096 262144 264 64!
Propiedades de la notación O:
- c O(f(n)) = O(f(n))
- O(f(n) + g(n)) = max{ O(f(n)), O(g(n)) } regla de la suma
- O(f(n)) * O(g(n)) = O(f(n) * g(n)) regla del producto
- O(O(f(n))) = O(f(n))
Ejemplos:
Si f(n)=4N2 + 6log2N + 8
Debido a que parte de la ecuación es cuadrática y parte es logarítmica, al aplicar la
regla de la suma, el mayor orden entre O(N2) y O(log2N) es O(N2). Por lo tanto, el orden
de magnitud que se asigna a f(n) es O(N2).
f(n) = 6N3 + 4N + 5Nlog3N +12

Parte de la ecuación es cúbica y parte es Nlog3N, al aplicar la regla de la suma, el
mayor orden entre O(N3) y O(Nog2N) es O(N3). Por lo tanto, el orden de magnitud que
se asigna a f(n) es O(N3).
f(n)= N*(N+1) +5N

Al aplicar la regla del producto, el orden de magnitud asignado es O(N2)
Asignación del f(n) para cada tipo de instrucción:

- Estructuras de Secuencia (asignación, entrada y salida): el f(n) es igual a 1.
Ejemplos:
x = x+1 f(n) = 1 por lo tanto, O(1)
Leer y f(n) = 1
Muestre z f(n) = 1
- Estructuras de decisión lógica: el f(n) será igual a 1 de evaluar la condición, más

el máximo f(n) obtenido de evaluar el SI y el NO.
Ejemplos:
Es (A > D) Si:{ A=A+2

D=D+1
Muestre A, D
}
No: A=D
El f(n) asignado a la decisión lógica será igual a: 1 de evaluar la condición (A > D)

más el máximo f(n) obtenido entre evaluar el Si y el No. El f(n) del Si es igual a 3 y
el f(n) del No es igual a 1. Luego el máximo f(n) entre el Si y el No, es 3. Para la
decisión lógica el f(n) es igual a 1+3 = 4.
Es (A > D) Si: Es (A > C) Si: { A=A+C

C= C-1
Muestre A, C
}
No:{ A=D
D= D+5
}
No: A=A+ 3
Para encontrar el f(n) de la decisión (A>D) se debe encontrar primero el f(n) del Si,
que en este caso es otra decisión lógica. El f(n) de la decisión lógica (A>C) es igual
a 4. Por lo tanto, el f(n) de la decisión lógica (A>D) es igual a 1 más el máximo de
evaluar el f(n) del Si, que es 4 y el f(n) del No, que es 1. Luego el f(n) asignado a la
decisión lógica (A>D), es 5.
- Estructuras de Selección Múltiple: el f(n) será igual a 1 más el máximo f(n)

obtenido entre las opciones de la selección.
- Estructuras de Ciclos predefinidos: El f(n) será igual al número de veces que se

ejecuta el ciclo más 1. Si no se conoce con exactitud el número de iteraciones, se
estima el número para el peor de los casos.
Ejemplo 1
f(n)
I=2 -------------------------------------------- 1
J=1 -------------------------------------------- 1
Para K = 1 hasta N -------------------------- N+1
{
I = I + 3 -------------------------------------- N
J= J + 4 -------------------------------------- N
Muestre I, J, K ------------------------------- N
}
-----------------
f(n)= 4N + 3 = O(N)
Ejemplo 2
f(n)
A=2 -------------------------------------------- 1
B=1 -------------------------------------------- 1
Para I = 1 hasta N ---------------------------- N+1
{
Para J = 1 hasta N -------------------------- (N + 1)*N=N2 + N
{
A = A + 3 -------------------------------------- N2
B = B * 4 -------------------------------------- N2
Muestre A, B, K ------------------------------- N2
}
} -----------------
f(n)= 4N2 + 2N + 3 = O(N2)
Ejemplo 3
f(n)
A=2 -------------------------------------------- 1
B=1 -------------------------------------------- 1
Para I = 1 hasta N { ---------------------------- N+1
Para J = 1 hasta I -------------------------- N*(N+1)/2 + N
{
A = A + 3 -------------------------------------- N*(N+1)/2
B = B * 4 -------------------------------------- N*(N+1)/2
Muestre A, B, K ------------------------------- N*(N+1)/2
} ----------------------
} f(n)= 2N2 + 4N + 3 = O(N2)
El número de veces que se ejecuta el ciclo interno J, depende de los valores que
tome la variable I en cada iteración. Para cuando:
I =1, la instrucción del ciclo interno se ejecuta 1 vez, más chequeo fin ciclo
I =2, la instrucción del ciclo interno se ejecuta 2 veces, más chequeo fin ciclo
I=3, la instrucción del ciclo interno se ejecuta 3 veces, más chequeo fin ciclo
Cuando,
I = N, la instrucción del ciclo interno se ejecuta N veces.
Luego el total de veces que se ejecuta el ciclo J es igual a:

∑ = 1+ 2 + 3 + 4 +...….+ N = N*(N+1)/2,
más N veces que resulta del fin de chequeo del ciclo J.
Ejemplo 4
f(n)
A=2 -------------------------------------------- 1
B=1 -------------------------------------------- 1
Para I = 1 hasta N { ---------------------------- N+1
Para J = 1 hasta I{ -------------------------- N*(N+1)/2 + N

Para K = 1 hasta J{---------------------------
6 5

A = A + 3 -------------------------------------- (1)
B = B * 4 -------------------------------------- (1)
Muestre A, B, K ------------------------------- (1)
} -------------------------------

} f(n)=
3 13 3=O(N3)
El número de veces que se ejecuta el ciclo interno K se puede expresar como,

1
1
2
1 1

2 2

!

" " 1 # $!

%
" " 1 # $! &" " 12" 4( (1)

Al resultado de la ecuación (1) se le debe sumar los fines de ciclo K. En este caso,
))
1 + 2 + 3 +…+N = (2)
Siendo (1) + (2) igual a:

&"" 12" 10( = "
6" 5"

Ejemplo 5
f(n)
C=0 -------------------------------------------- 1
i=1 -------------------------------------------- 1
j=1 -------------------------------------------- 1
Entre N -------------------------------------------- 1
Mientras (i ≤ N) ∧ (j ≤ N) haga ---------------------- N2 + N
{ i = i + 1 ------------------------------------------------- N2
C = C + 1------------------------------------------------ N2
Es ((i > N) ∧ (j < N)) Si:{ i = 1 ------------------- 3N2
j= j+1
}
}
Muestre C --------------------------------------------- 1
-----------------
f(n)= 6N2 + N + 5 = O(N2)
En el ciclo Mientras, para cada uno de los valores de J igual desde 1 hasta N, la I se ejecuta
desde 1 hasta N. Luego el número de veces que se ejecuta el ciclo Mientras, es igual a N2 +
N.
Ejemplo 6:
f(n)
A=1 ------------------------------------------------- 1
C=1 -------------------------------------------------- 1
Mientras (C < N) haga ---------------------------------- log2N +1
{
A= A + 1 ----------------------------------------------- log2N
C = C * 2 ----------------------------------------------- log2N
Muestre A, C ------------------------------------------ log2N
} ----------------------
f(n)= 4log2N + 3 = O(log2N)
El número de veces que se ejecuta la instrucción del ciclo va a depender de

los valores de C. Si por ejemplo, N=128 (27), el ciclo se ejecuta para C = 1,
2, 4, 8, 16, 32, 64 y 128, es decir, 8 veces. Si N=256 (28), el ciclo se ejecuta
9, veces. Luego, el número de veces que se ejecuta el ciclo es igual a log2N
+1 (el entero inmediato superior).
Ejemplo 7:
f(n)
A=1 ------------------------------------------------- 1
C=N -------------------------------------------------- 1
Mientras (C > 1) haga ---------------------------------- log2N +1
{
A= A + 1 ----------------------------------------------- log2N
C = C / 2 ----------------------------------------------- log2N
Muestre A, C ------------------------------------------ log2N
} ----------------------
f(n)= 4log2N + 3 = O(log2N)
Como en el ejemplo 4, el número de veces que se ejecuta la instrucción del
ciclo va a depender de los valores de C. Si por ejemplo, N=128 (27), el ciclo
se ejecuta para C = 128, 64, 32, 16, 8, 4, 2 y 1, es decir, 8 veces. Si N=256
(28), el ciclo se ejecuta 9, veces. Luego, el número de veces que se ejecuta el
ciclo es igual a log2N +1 (el entero inmediato superior).
En general, si la instrucción que altera la condición del ciclo es multiplicada,

o dividida por una constante k, el número de veces que se ejecuta el ciclo es
aproximadamente igual a logk N.
Ejemplo 8:
f(n)
j=1 ------------------------------------------------ 1
z=0 ------------------------------------------------ 1
Haga{
A = 1 ------------------------------------------------- N
Mientras (A≤ N) haga ---------------------------------- N*(log2N +1) = Nlog2N + N
{
A= A * 2 ----------------------------------------------- N* log2N
z = z + 1 ----------------------------------------------- N*log2N
Muestre A, z ------------------------------------------ N* log2N
}
j=j+1 ------------------------------------------N
} Mientras (j ≤ N) N+1
---------------------
f(n)= 4N + 4Nlog2N + 3 = O(Nlog2N)
- Llamadas a Procedimientos: Cuando se tiene la llamada a un procedimiento, el

f(n) asignado a éste, será el f(n) obtenido en dicho procedimiento.
Ejercicio 1:
Determinar el f(n) y el Orden de Magnitud de un algoritmo que encuentre la suma de los
N primeros números naturales.
Análisis del Problema:

Una solución al problema de encontrar la suma de los N primeros números naturales
consiste en utilizar un ciclo desde 1 hasta N, en donde a medida que se itere, se acumule
la suma.
Valores de entrada:
N: Variable numérica entera. Número de valores a sumar
Resultado:
Suma: Variable numérica entera que contiene la suma de los N primeros números
naturales.
Solución 1:
Programa Suma1 f(n)
{
entero N, Suma = 0 ----------- 1
Entre N ----------------- 1
Para I= 1 hasta N ---------- N+1
{
Suma = Suma + I -------- N
}
Muestre Suma ------------ 1
} ------------
f(n) = 2N + 4 = O(N)
Solución 2:
Dado que la suma de 1+ 2 + 3 + …...+ (N - 1) + N = N*(N+1) / 2, es posible diseñar otra
solución utilizando la fórmula anterior.
Programa Suma2 f(n)

{
entero N, Suma
Entre N ----------------- 1
Suma = N*(N+1)/2 --------- 1
Muestre Suma ------------ 1
-----------
f(n) = 3 = O(1)
Comparando el orden de magnitud de la solución 1 O(N), con el orden de magnitud de

la solución 2 O(1), se concluye que el algoritmo 2 es más eficiente porque siempre esta
solución se ejecutará en un tiempo constante, es decir, independiente del valor que se le
asigne a N.
Ejercicio 2:
Determinar el f(n) y el Orden de Magnitud de un método que encuentre la suma de los
N primeros números de una serie aritmética con valor inicial a1 y una diferencia
(distancia) d.
Análisis del Problema:

En una serie aritmética:
a1 = a1
a2 = a1 + d
a3 = a2 + d
.
.
an = an-1 + d
Valores de entrada:
a1: Variable numérico que contiene el valor inicial de la serie
d: Variable numérica. Diferencia entre los términos de la serie
N: Variable numérica entera. Número de valores a sumar
Salida:
Suma: Variable numérica que contiene la suma de los N primeros números de la serie
aritmética
Solución 1:
real Serie_Aritmetica(real a1, real d, entero N) f(n)

{
real ai, suma = a1 ---------------------------------------------- 1
ai= a1-------------------------------------------------------------- 1
Para I= 2 hasta N ---------------------------------------------- N
{ ai = ai + d ------------------------------------------ N - 1
suma = suma + ai ----------------------------------------- N - 1
}
retorne( suma) ----------------------------------------------- 1
} ------------
f(n) = 3N + 1 = O(N)
Solución 2:
En una serie aritmética el término N-ésimo de la serie es igual a:
an = a1 + (N – 1)*d
y la suma de los N términos es:

N* (a1 + an)/2
Utilizando estas 2 fórmulas, otra solución algorítmica es la siguiente:
real Serie_Aritmetica(real a1, real d, entero N) f(n)

{
real an = a1 + (N – 1)*d ------------------------------- 1
retorne( N*(a1 + an)/2.0) ------------------------------- 1
} ------------
f(n) = 2 = O(1)
Lo que indica que la segunda solución es más eficiente que la primera, ya que en ésta el tiempo
de ejecución es constante, es decir es independiente del valor de N.
Ejercicio 3:
Elaborar dos métodos uno con orden de magnitud O(N) y el otro O(1), que encuentre la
suma de los N primeros números de una serie geométrica con valor inicial a1 y una
razón r.
En una serie geométrica:

a1 = a1
a2 = a1 * r
a3 = a2 * r
.
.
an = an-1 * r
El N-ésimo término es igual a:
an = a1*rN – 1
y la suma de los N términos es:

- . /
,
-/
Referencias
- Estructuras de Datos y Algoritmos. Alfred V.Aho, John E. Hopcroft, Jeffrey D.
Ullman. Addison-Wesley, Iberoamericana 1988.
- Fundamentos de Algoritmia. Brassard, Gilles, Bratley, Paul. Prentice-Hall. 1997.
- Estructura de Datos. Libro de Problemas. Luis Joyanes Aguilar, Ignacio Zahonero

Martínez, Matilde Fernández A y Lucas Sánchez G. Ed. Mc. Graw Hill. 1999
TALLER ANÁLISIS DE ALGORITMOS
1. a) Elaborar un método que tiene como entrada dos matrices A y B de orden N*M y
que retorne la matriz C con el resultado de la suma de A + B
b) Encontrar el contador de frecuencia y el orden de magnitud del método anterior
2. a) Elaborar un método que tiene como entrada dos matrices A y B de orden N*M y
que retorne la matriz C con el resultado de la multiplicación de A * B
3. a) Elaborar un método que tiene como entrada un arreglo unidimensional A y que

retorne el menor elemento del arreglo.
4. Encontrar el contador de frecuencia y el orden de magnitud para cada uno de los

métodos siguientes:
a) entero p1 (entero n)
{
entero i, j, numero
entero suma = 0
Para i=1 hasta n-1
{
Para j= i+1 hasta n
{
Entre numero
suma = suma + numero
}
}
retorne( suma )
}
b) entero p2 (entero n)
{
entero i = 1, x= 0
Mientras i ≤ n haga
{
x =x+1
i=i+3
}
retorne( x )
}
c) entero p3 (entero n)
{
entero i = 1, x= 0
Mientras i < n haga
{
x =x+1
i=i*3
}
retorne( x )
}
d) entero p4 (entero n)
{
entero i = 1, x= 0, j
Haga
{
j=1
Mientras j ≤ n haga
{
x =x+2
j = j*2
}
i = i +1
} Mientras ( i ≤ n)
retorne( x )
}
e) entero p5(entero n)
{
entero i, j, k , x = 0
Para i=1 hasta n
{
Para j=1 hasta n
{
Para k =1 hasta j
{
x=x+2
} //fin ciclo k
} // fin ciclo j
}// fin ciclo i
retorne( x )
}
f ) entero P6(entero n, entero m)
{
entero i, j, k , tmp = 0
Para i=1 hasta n
{
Para j=1 hasta n
{
Es (j = = m) Si: {
Para k= 1 hasta n inc 2
tmp= tmp + (i+j+k)
}
No: {
Para k= 1 hasta n
tmp= tmp + (i+j+k)
}
tmp= tmp div 2

}// fin ciclo j
}// fin ciclo i
tmp=tmp + 1
retorne (tmp)
}
g) entero p7 (entero n1, entero n2, entero m1, entero m2)

{
entero tmp
Es (n1 > n2) Si: {
Para i=1 hasta 10 {
tmp=tmp * n2 }
}
No: Es (m1>m2) Si: tmp=10
No: tmp =12
retorne (tmp)
}
h) entero p8 (entero n, entero m)
{
entero resultado = 1
Es(n > m) Si:
Para i=1 hasta n {
resultado = resultado + 1}
No:
resultado = resultado * 2
Para j = 1 hasta n, inc 2 {

resultado = resultado + j }
retorne(resultado)
}
i) hilera NumBin( entero n)

{ hilera binario = “ ”
entero x = n
Mientras (x!= 0) haga
{ Es ( par(x)) Si: binario = binario + “0”
No:{ binario = binario + “1”
x=x–1
}
x = x/2
}
retorne(binario)
}
j) entero p9 (entero n)
{
entero j= 0, L= 0
Para i=1 hasta n {
j = j + i*i
Para k=1 hasta j {
L=L+1
}// fin ciclo k
}// fin ciclo i
Muestre L
}
BÚSQUEDA Y ORDENAMIENTO
BÚSQUEDA
La búsqueda es una de las operaciones que se realiza con mayor frecuencia sobre un
conjunto de elementos.
El proceso consiste en revisar el conjunto de elementos con el fin de localizar un

determinado elemento.
Los métodos de búsqueda más utilizados son:

- Búsqueda Lineal
- Búsqueda Binaria
Búsqueda Lineal: El método de la búsqueda lineal compara cada uno de los elementos
del conjunto con el valor a buscar y termina cuando: encuentra el valor, en este caso el
método retornará el mensaje “existe el valor”, o la posición en donde se encuentra dicho
valor. Cuando después de comparar todos los elementos del conjunto, con el valor a
buscar, ninguno coincide, el método retornará el mensaje “no existe el valor” o la
posición -1.
Entrada:
A: Arreglo unidimensional de N valores numéricos enteros
N: Tamaño del arreglo A. Variable numérica entera.
V: Valor a buscar en el arreglo A. Variable numérica entera.
Resultado:
S: Variable tipo hilera en donde se retorna el resultado de la búsqueda: “existe el valor”
o, “no existe el valor”.
hilera BÚSQUEDA_LINEAL( entero V) f(n)

{
hilera S = ”no existe el valor” --------------------------------- 1
entero L = 1 --------------------------------- 1
Mientras (L< = N) ^ (S = = ”no existe el valor”) ------------ N+1
{
Es (V = = A[L]) Si: S = ”existe el valor” ---------------- 2N
No: L = L +1
}
Retorne S
} ------------
f(n) =3N + 3 = O(N)
La instrucción del ciclo Mientras, se ejecuta N+1 veces porque en el peor de los casos (cuando
no existe V), la primera condición (L < = N) es falsa cuando L > N.
Búsqueda Binaria: este método se utiliza sobre un arreglo unidimensional ordenado. El

procedimiento se describe de la siguiente manera:
Sea por ejemplo, el arreglo A con N = 12 elementos
A
9 15 28 35 42 57 76 125 224 275 360 612
1 2 3 4 5 6 7 8 9 10 11 12
Se definen dos variables:

LI: Límite inferior. Inicialmente LI = 1
LS: Límite superior. Inicialmente LS = N
Se ubica el elemento que se encuentra en la posición del medio en el arreglo:

Medio = (LI + LS) / 2 = (1 + 12) / 2 = 6 (división entera)
Se compara A[Medio] con el valor a buscar (V):

- Si V < A[Medio], se asigna a LS = Medio – 1 y se calcula nuevamente Medio. Es
decir, que se descartan para la búsqueda, los elementos que se encuentran después
del elemento del Medio, ya que si el arreglo está ordenado y el elemento a buscar V,
es menor que A[Medio], no se va a encontrar después de A[Medio].
- Si V > A[Medio], se asigna a LI = Medio + 1 y se calcula nuevamente Medio. Es
decir, se descartan de la búsqueda, los elementos que se encuentran antes del
elemento del Medio, debido a que si el arreglo está ordenado y el elemento a buscar
V, es mayor que A[Medio], no se va a encontrar antes de A[Medio].
- Si V = A[Medio], significa que existe V en el arreglo y termina la búsqueda.
En el caso de que no exista V en el arreglo, el algoritmo termina cuando LI > LS.
Para el ejemplo, si el valor a buscar V es igual a 15:

- Se compara 15 con el elemento del medio que es 57. Dado que V < A[Medio], se
asigna a LS = 5.
- Se calcula Medio = (1 + 5) / 2 = 3.
- Se compara 15 con A[3], ya que V < 28, se asigna a LS = 2.
- Se calcula Medio = ( 1+ 2 ) / 2 = 1
- Se compara 15 con A[1], ya que V > 9, se asigna a LI = 2.
- Se calcula Medio = (2+ 2 ) / 2 = 2
- Se compara 15 con A[2], como son iguales, termina el método retornando que si
existe el valor.
A: Arreglo unidimensional ordenado de N valores numéricos enteros

N: Tamaño del arreglo A. Variable numérica entera.
V: Valor a buscar en el arreglo A. Variable numérica entera.
Resultado:
S: Variable tipo hilera en donde se retorna el resultado de la búsqueda: “ existe el valor”
o, “no existe el valor”.
hilera BÚSQUEDA_BINARIA(entero V) f(n)
{
hilera S = ”no existe el valor” ----------------------------------------------- 1
entero LI = 1, LS = N, Medio ----------------------------------------------- 2
Mientras (LI < = LS) ^ (S = = ”no existe el valor”) ----------------------- log2 N + 2
{
Medio = (LI + LS) / 2 --------------------------------------------------- log2 N + 1
Es (V < A[ Medio ] ) Si: LS = Medio - 1 -------------------------------- 3 *(log2 N + 1)
No: Es (V > A[Medio] ) Si: LI = Medio +1
No: S = ”existe el valor”
}
Retorne S
} ---------------------
f(n) = 5log2 N + 9 = O( log2 N )
La instrucción del ciclo Mientras se ejecuta log2 N + 2, ya que para el peor de los casos,
que se presenta cuando no existe V en el arreglo, el ciclo termina cuando LI >LS. Por
ejemplo, si N = 64, la segunda vez que ingresa al ciclo, se han descartado de la
búsqueda la mitad de los valores, es decir 32, luego se descartan 16, después 8, 4, 2, 1 y
termina porque LI > LS. Es decir, que para N = 64 el número de veces que se ejecuta el
ciclo es log264 + 2 = 6 + 2 = 8. Si N = 128, el número de veces que se ejecuta el ciclo
es: log2128 + 2= 7 + 2 = 9 veces.
Comparando el orden de magnitud del método de la Búsqueda Lineal, que es O(N), con
el orden de magnitud del método de la Búsqueda Binaria O(log2N), significa que la
Búsqueda Binaria es más eficiente.
Dependiendo entonces de la periodicidad con que se deban realizar búsquedas sobre un

arreglo no ordenado, se decide entonces si se justifica ordenarlo para seguir utilizando el
método de la búsqueda binaria.
ORDENAMIENTO
El ordenamiento se define como el proceso de organizar un conjunto de elementos de

acuerdo a un criterio definido. El propósito principal de un ordenamiento es el de
facilitar las búsquedas de los elementos del conjunto.
Ejemplos de ordenamientos:
El directorio telefónico, una lista de estudiantes, bibliotecas y diccionarios, etc.
El ordenar un grupo de datos significa mover los datos o sus referencias, para que
queden en una secuencia tal que represente un orden, el cual puede ser numérico,
alfabético o incluso alfanumérico, en forma ascendente o descendente.
¿Cuándo conviene usar un método de ordenamiento?

Cuando se requiere hacer una cantidad considerable de búsquedas y es importante el
factor tiempo.
Tipos de Ordenamientos:
Los 2 tipos de ordenamiento que se pueden realizar son:
Internos: Son aquellos en los que los valores a ordenar están en memoria principal, por
lo que se asume que el tiempo que se requiere para acceder a cualquier elemento sea el
mismo. Son usados cuando el número de valores a ordenar no es muy grande.
Externos: Son aquellos en los que los valores a ordenar están en memoria secundaria,
por lo que se asume que el tiempo que se requiere para acceder a cualquier elemento
depende de la última posición accesada (posición 1, posición 500, etc).
Métodos de Ordenamiento Internos

- Burbuja (o Intercambio): Consiste en comparar pares de elementos adyacentes e
intercambiarlos entre sí, hasta que queden ordenados.
V: arreglo unidimensional de valores numéricos enteros

N: tamaño del arreglo V.
Resultado:
El método retorna el arreglo ordenado
Procedimiento:
En este método se realizan N - 1 pasadas.
En la primera pasada, se compara V[1] con V[2] y si V[1] > V[2], se intercambian,
luego se compara V[2] con V[3] y si V[2] > V[3], se intercambian, y así se
continua hasta comparar V[N-1] con V[N]. Al finalizar la primera pasada, el mayor
de todos los elementos del arreglo queda ubicado en la última posición del arreglo.
En la segunda pasada, se compara V[1] con V[2] y si V[1] > V[2], se intercambian,
luego se compara V[2] con V[3] y si V[2] > V[3], se intercambian, y así se
continua hasta comparar V[N-2] con V[N-1]. Al finalizar la segunda pasada, el
siguiente mayor de todos los elementos del arreglo queda ubicado en la penúltima
posición del arreglo
En la N-1 pasada se compara V[1] con V[2] y si V[1] > V[2], se intercambian.
BURBUJA( ) f(n)
{
entero aux
Para I = 1 hasta N - 1 haga --------------------------------- N

Para J = 1 hasta N - I haga ----------------------------- ------ + (N - 1)

Es ( V[ J ] > V[ J + 1]) Si: { aux =V[ J ] --------------------------- 4

V[ J ] = V[J +1]
V[ J +1] = aux
}
Fin ciclo J
Fin ciclo I
Retorne
} ---------------------------------

- 1

Para encontrar el f(n) del ciclo J se hace el siguiente análisis:
Cuando en el primer ciclo,

I = 1, el ciclo J se ejecuta N - 1 veces, más chequeo fin ciclo
I = 2, el ciclo J se ejecuta N - 2 veces, más chequeo fin ciclo
I = 3, el ciclo J se ejecuta N- 3 veces, más chequeo fin ciclo
Para el último valor que toma I que es N – 1, el ciclo J se ejecuta 1 vez, más chequeo
fin ciclo, por lo tanto el número de veces que se ejecuta el ciclo J es igual a:

(N – 1) + (N – 2) + … + 2 + 1= 1

ya que el f(n) resultante del método de la Burbuja es una ecuación cuadrática,

entonces el método tiene un orden de magnitud igual a O(N2).
Ejemplo:
Sea el arreglo a ordenar V = [40, 12, 78, 65, 8]
Dado que N=5, se realizan 4 pasadas.
En la primera pasada:
Se compara V[1]:V[2], como V[1] > V[2] se intercambian y queda V igual a:
V = [12, 40, 78, 8, 65]
Se compara V[2]:V[3], V[2] < V[3] , el arreglo permanece igual
V = [12, 40,78, 8, 65]
V = [12, 40, 8, 78, 65]
V = [12, 40, 8, 65, 78 ]
Al finalizar la primera pasada queda ubicado en la última posición del arreglo, el
mayor valor del arreglo V.
En la segunda pasada:
Se compara V[1]:V[2], como V[1] < V[2], el arreglo permanece igual
V = [12, 40, 8, 65, 78 ]
Se compara V[2]:V[3], V[2] > V[3] se intercambian y queda V igual a:
V = [12, 8, 40, 65, 78 ]
Se compara V[3]:V[4], V[3] < V[2] el arreglo permanece igual

V = [8, 12, 40, 65, 78]
Al finalizar la segunda pasada queda ubicado en la penúltima posición del arreglo, el

siguiente mayor valor del arreglo V.
En la tercera pasada:
Se compara V[1]:V[2], como V[1] < V[2] no se realiza intercambio.
Se compara V[2]:V[3], V[2] < V[3] no se realiza intercambio.
Al finalizar la tercera pasada queda ubicado en la tercera posición del arreglo, el
siguiente mayor de V
En la cuarta y última pasada, no se realiza ningún intercambio y retorna el arreglo

ordenado:
V = [8, 12, 40, 65, 78]
- Burbuja Mejorado: Para el método de la Burbuja se ha propuesto una versión

mejorada, la cual consiste en adicionar una bandera que se utiliza para detectar, en
una determinada pasada, si se realizan cambios. Es decir, que si en una pasada no se
realizan cambios, el arreglo ya se encuentra ordenado y en este caso no es necesario
continuar con las siguientes. En el ejemplo anterior, cuando se realizó la tercera
pasada, no se hizo ningún intercambio porque el arreglo ya estaba ordenado. Si se
usa la bandera, al finalizar la tercera pasada se retorna el arreglo ordenado.
BURBUJA_MEJORADO( ) f(n)
{
entero aux, I = 1 ----------------------------------------------------------- 1
booleano Bandera = falso -------------------------------------------------------- 1
Mientras (Bandera = = falso) ∧ (I < N) ---------------------------------------- N

{ Bandera = Verdadero ------------------------------------------------------- N-1

Para J = 1 HASTA N - 1 haga-------------------------------- N 1

{ Es ( V[ J ] > V[ J + 1] ) Si: { aux =V[ J ]----------------5

V[ J ] = V[J + 1]
V[ J + 1] = aux
Bandera = falso
}
} Fin ciclo J
I = I +1 ---------------------------------------------------------------------------------- N-1
} Fin ciclo I
Retorne
}
---------------------------------

3 - 1
el f(n) resultante del método de la Burbuja Mejorado es una ecuación cuadrática,
entonces el método tiene un orden de magnitud igual a O(N2).
- Selección: Sea V un arreglo de tamaño N. En este método también se realizan N - 1

pasadas. En la primera pasada se busca el menor valor del arreglo y se intercambia
con el primero, en la segunda pasada se ubica el siguiente menor y se intercambia
con el de la segunda posición, y así sucesivamente hasta ordenar todo el arreglo.

Resultado
SELECCION( ) f(n)
{
entero aux, menor
Para I = 1 hasta N - 1 haga ---------------------------------------- N

{ menor = I --------------------------------------------- N-1

Para J = I +1 hasta N haga --------------------------------------- N-1)

{ Es(V[ J ] < V[menor]) Si: menor = J -------------------------- 2

} Fin ciclo J
aux = V[ I ] ----------------------------------------------------------- N-1
V[ I ] = V[menor] ----------------------------------------------------------- N - 1
V[menor] = aux ----------------------------------------------------------- N - 1
}Fin ciclo I
}
---------------------------------

5

el f(n) resultante del método de Selección es una ecuación cuadrática, entonces el

método tiene un orden de magnitud igual a O(N2).
Ejemplo:
En el mismo arreglo del ejemplo del método de la burbuja
V = [40, 12, 78, 65, 8]
Se realizan 4 pasadas.
En la primera pasada, se busca el menor de los elementos del arreglo y se
intercambia con el de la primera posición, quedando el arreglo:
V = [8, 12, 78, 65, 40]
En la segunda pasada como no existe en el arreglo un elemento a partir del tercero,

que sea menor a 12, el arreglo permanece igual.
En la tercera pasada, se intercambia el 78 con el 40:

V = [8, 12, 40, 65, 78]
En la cuarta y última pasada, no se realiza intercambio y retorna el arreglo ordenado.

- Inserción Directa (o Baraja): El método consiste en insertar cada uno de los
elementos del arreglo, en una parte ya ordenada del mismo.

Resultado
INSERCION( ) f(n)
{
booleano Bandera
entero J, aux
Para I = 2 hasta N haga -------------------------------------------------- N
{ Bandera = falso -------------------------------------------------------- N-1
J= I -------------------------------------------------------------- N-1

Mientras (J > 1) ∧ (Bandera = = falso) -------------------------- N 1

{ Es ( V[ J ] < V[J – 1]) Si:{ aux = V[ J ] -------------------------- 5

V[ J ] = V[J – 1]
V[ J – 1] = aux
J= J - 1
}
No: Bandera = verdadero
}Fin ciclo J
} Fin ciclo I
} ------------------------------

3 3
el f(n) resultante del método de Inserción es una ecuación cuadrática, entonces el

método tiene un orden de magnitud igual a O(N2).
Ejemplo:
En el arreglo del ejemplo
V = [40, 12, 78, 65, 8]
Cuando I = 2, se compara V[2]:V[1], como V[2] < V[1] se intercambian y queda V

igual a:
V = [12, 40, 78, 8, 65]
I = 3, se compara V[3]:V[2], como V[3] > V[2] hace bandera = verdadero
I = 4, se compara V[4]:V[3], como V[4] < V[3] se intercambian y queda V igual a:
V = [12, 40, 8,78, 65]
se compara V[3]:V[2], como V[3] < V[2] se intercambian y queda V igual a:
V = [12, 8, 40, 78, 65]
se compara V[2]:V[1], como V[2] < V[1] se intercambian y queda V igual a:
V = [8, 12, 40, 78, 65]
I = 5, se compara V[5]:V[4], como V[5] < V[4] se intercambian y queda V igual a:
V = [8, 12, 40, 65, 78]
se compara V[4]:V[3], como V[4] > V[3] hace bandera = verdadero y termina.
Inserción Binaria: Es una mejora del método de inserción directa. Para lograr esta
mejora se utiliza a una búsqueda binaria en lugar de una búsqueda secuencial para
insertar un elemento en la parte izquierda del arreglo, que ya se encuentra ordenado.
INSERCION_BINARIA( ) f(n)
{
entero J, aux, izq, der, medio
Para I = 2 hasta N haga -------------------------------------------------- N
{
aux = V[I] -------------------------------------------------- N-1
izq= 1 -------------------------------------------------- N-1
der= I -1 -------------------------------------------------- N-1
Mientras (izq < = der) haga --------------------------------- (N – 1)(log2N +2)
{
medio =((izq + der)/2 --------------------------------- (N – 1)(log2N + 1)
Es (aux < V[medio])Si: der = medio - 1 -------------- 2(N – 1)(log2N +1)
No: izq = medio + 1
}
J=I–1 -------------------------------------------------- N-1
Mientras (J > = izq) haga ----------------------------------------- N*( N + 1)/2 + N - 2
{
V[J + 1] = V[J] ----------------------------------------- N*( N + 1)/2 - 1
J=J–1 -------------------------------------- N*( N + 1)/2 - 1
}
V[izq] = aux -------------------------------------------------- N-1
} //fin ciclo I
}
Encontrar el f(n) y el Orden de Magnitud del método de Inserción Binaria.

Solución Taller Análisis Algoritmos
4. Encontrar el contador de frecuencia y el orden de magnitud para cada uno de los

métodos siguientes:
a) O(N2)
b) O(N)
c) O(log 3N)
d) O(Nlog 2N)
e) O(N3)
f) O(N3)
g) O(1)
h) O(N)
i) O(log 2N)
j) O(N4)
Listas Simples Enlazadas
La lista simple enlazada es una estructura de datos que permite almacenar datos de una
forma organizada, al igual que los arreglos pero, a diferencia de éstos, una lista enlazada
es una estructura dinámica, por lo que no se tiene que conocer de antemano el número
de elementos que se van a almacenar
Una lista enlazada se compone de un conjunto de elementos. Cada elemento de la lista

simple enlazada contiene un conjunto de campos de información y un enlace al
siguiente elemento de la lista. Los elementos de una lista enlazada, reciben también el
nombre de Nodos.
En una lista simple enlazada, cada uno de los elementos de la lista, almacena la
referencia del siguiente elemento de la lista, excepto el último que no tiene sucesor y
contiene null que significa fin de la lista.
La principal ventaja de las listas enlazadas con respecto a los arreglos, es que no se
necesita conocer de antemano el número de elementos que se van a almacenar, ya que a
medida que se necesite almacenar un nuevo elemento, se solicita el espacio para él. Otra
ventaja de las listas enlazadas es que para realizar operaciones de inserción y/o borrado
no hay que mover todos los elementos, sólo se actualizan los enlaces de los nodos
afectados por dichas operaciones, mientras que en un arreglo si se va a insertar un nuevo
elemento se deben mover hacia la derecha de él todos los elementos que se encuentren a
partir de la posición de la cual se va a realizar la inserción. De igual manera si se va a
realizar una operación de eliminación de un elemento sobre el arreglo.
Una desventaja de las listas enlazadas es que no se puede acceder directamente sobre un
elemento si no se conoce la referencia en donde se encuentra ubicado. En un arreglo se
puede ir directamente a la posición en donde se encuentra cualquier elemento.
Representación de una Lista Simple Enlazada:
5 9 3 12 null
dato sig
Primero Ultimo
Los datos a almacenar en cada nodo pueden ser de cualquier tipo. En este ejemplo la
lista se compone de un conjunto de números enteros.
Definición de la Clase Nodo:

Clase Nodo{
int dato; //campo de información
Nodo sig; //campo de enlace
Nodo(int d){ // método constructor de un nodo
dato = d;
sig = null;
}
Nodo( ){ // método constructor de un nodo

dato =0;
sig = null;
}
Asigna_Dato(int d){ //método para modificar campo de dato

dato = d;
}
Asigna_Sig(Nodo x){ //método para modificar campo de enlace
sig = x;
}
entero Retorne_Dato( ){ //método para retornar la información del campo de dato

retorne(dato);
}
Nodo Retorne_Sig( ){ //método para retornar la información del campo de enlace

retorne(sig);
}
Las operaciones básicas que se definen sobre una lista simple enlazada son las
siguientes:
- Construir la lista
- Encontrar si la lista es vacía, o no.
- Encontrar primer elemento de la lista
- Encontrar último elemento de la lista
- Insertar: inserta un nuevo nodo en la lista, La inserción en una lista enlazada
puede ser al principio, al final de la lista o en orden.
- Eliminar: elimina un nodo de la lista
- Buscar: busca la referencia del nodo en donde se encuentra un determinado dato
- Anterior: retorna la referencia del nodo anterior a otro nodo dado
Definición de la Clase Lista Simple Enlazada
Clase Lista_Simple{
Nodo primero, ultimo;
Lista_Simple(){ // Constructor de la Lista

primero=ultimo= null;
}
Nodo primero(){ // Ubica el primer elemento de la lista
retorne(primero);
}
Nodo ultimo(){ // Ubica el último de la lista

retorne(ultimo);
}
booleano EsVacia( ){ // Determina el estado de la lista

retorne (primero = = null):
}
Nodo Anterior(Nodo x){ //Buscar Nodo Anterior a un nodo dado X
Nodo ant;
ant=primero( );
Mientras (ant.Retorne_Sig() != x)
ant = ant.Retorne_Sig();
retorne(ant);
}
Insertar_principio(entero nuevoDato){ //Inserta al principio de la Lista

//petición de espacio de memoria para el nuevo nodo
Nodo nuevoNodo = new Nodo(nuevoDato);
Es (EsVacia()) Si:{ primero = nuevoNodo;
ultimo = nuevoNodo;
}
No: { nuevoNodo.Asigna_Sig(primero);
primero = nuevoNodo;
}
}
Insertar_fin(entero nuevoDato){ //Inserta al final de la Lista

//petición de espacio de memoria para el nuevo nodo
Nodo nuevoNodo = new Nodo(nuevoDato);
Es (EsVacia()) Si:{ primero = nuevoNodo;
ultimo = nuevoNodo;
}
No: { ultimo.Asigna_Sig(nuevoNodo);
ultimo = nuevoNodo;
}
}
Insertar_Ordenada(entero nuevoDato){ //Insertar en Lista Ordenada

Nodo x, ant, nuevoNodo
Es (EsVacia( ))Si:{Insertar_principio(nuevoDato);
retorne;
}
x = primero( );
Mientras (x!=null) ∧ ( x.Retorne_Dato() < nuevoDato)
x=x.Retorne_Sig();
Es(x = =null) Si{Insertar_fin(nuevoDato);
retorne;
}
Es(x = =primero())Si: Insertar_principio(nuevoDato);
No:{
nuevoNodo = new Nodo(nuevoDato);
ant=Anterior(x);
ant.Asigna_Sig(nuevoNodo);
nuevoNodo.Asigna_Sig(x);
}
}
Nodo Buscar_Nodo(entero d){ // Buscar nodo de un determinado dato

Nodo x;
x=primero();
Mientras(x!= null ∧ x.Retorne_Dato()!=d)
x=x.Retorne_Sig();
retorne(x); //si no existe dato retorna x =null
}
Eliminar(entero d){ // Elimina un elemento de la Lista

Nodo x, ant;
Es(EsVacia()){Si:{Muestre “Lista Vacia"
retorne;
}
x =Buscar_Nodo(d);
Es(x= =null)Si:{ Muestre "No existe "+d+" En Lista"
retorne;
}
Es(x = = primero())Si{primero=primero.Retorne_Sig();
Es(primero= =null) ultimo=null;
}
No:{ant=Anterior(x);
ant.Asigna_Sig(x.Retorne_Sig());
Es(x= =ultimo())Si: ultimo=ant;
}
}
Mostrar( ){ //Mostrar la Lista

Nodo x;
x = primero();
Mientras(x!=null) {
Muestre x.Retorne_Dato();
x =x.Retorne_Sig();
}
}
} // Fin Clase Lista Simple

Ejemplo:
Elaborar un algoritmo que cree una lista simple enlazada que contenga un conjunto de
números enteros.
Programa Crear_Lista{
entero dato
Lista_Simple miLista= new Lista_Simple()
Entre dato
Mientras (dato != 0){
miLista.insertar_Ordenada(d)
Entre dato
}
miLista.Mostrar()
}
Listas Doblemente Enlazadas
Una lista doblemente enlazada se compone de un conjunto de elementos. Cada elemento
de la lista doblemente enlazada contiene un conjunto de campos de información y dos
enlaces, en donde un enlace contiene la referencia al anterior elemento a él en la lista y
el otro enlace contiene la referencia al siguiente elemento de la lista.
La ventaja de lista doble enlazada, con respecto a la lista simple enlazada, es que se
puede recorrer la lista en ambos sentidos, ya que partiendo del primer elemento se
puede recorrer la lista hasta el último de ella, o viceversa, partiendo del último elemento
se puede llegar al primero.
Representación de una Lista Doblemente Enlazada:
null 5 9 3 12 null
ant dato sig
Primero Ultimo
Definición de la Clase Nodo Doble:

Clase Nodo_D{
Nodo_D ant //campo de enlace al anterior
entero dato //campo de información
Nodo_D sig //campo de enlace al siguiente
Nodo_D(entero d){ // método constructor de un nodo doble

ant = null
dato = d
sig = null
}
Nodo_D( ){ // método constructor de un nodo doble

ant = null
dato =0
sig = null
}
AsignaAnt(Nodo_D x){ //método para modificar campo de enlace anterior

ant = x
}
AsignaDato(entero d){ //método para modificar campo de dato

dato = d
}
AsignaSig(Nodo_D x){ //método para modificar campo de enlace al siguiente
sig = x
}
Nodo_D RetorneAnt( ){ //método para retornar la información del campo de

retorne(ant) enlace al anterior
}
entero RetorneDato( ){ //método para retornar la información del campo de dato

retorne(dato)
}
Nodo_D RetorneSig( ){ //método para retornar la información del campo de enlace

retorne(sig) al siguiente
}
Las operaciones básicas que se definen sobre una lista doblemente enlazada son las
siguientes:
- Construir la lista
- Encontrar si la lista es vacía, o no.
- Encontrar primer elemento de la lista doble
- Encontrar último elemento de la lista doble
- Insertar: inserta un nuevo nodo en la lista, La inserción en una lista doble
enlazada puede ser al principio, al final de la lista o en orden.
- Eliminar: elimina un nodo de la lista doble enlazada
- Buscar: busca la referencia del nodo en donde se encuentra un determinado dato
- Mostrar lista doble de izquierda a derecha
- Mostrar lista doble de derecha a izquierda
Definición de la Clase Lista Doblemente Enlazada
Clase Lista_Doble{
Nodo_D primero, ultimo
Lista_Doble( ){ // Constructor de la Lista Doble

primero = ultimo= null
}
Nodo_D primero( ){ // Ubica el primer elemento de la lista

retorne(primero)
}
Nodo_D ultimo( ){ // Ubica el último de la lista

retorne(ultimo)
}
retorne(primero = = null)
}
insertarPrincipioD(entero nuevoDato){ //Inserta al principio de la Lista

Nodo_D nuevoNodo = new Nodo_D(nuevoDato)
Es (EsVacia( )) Si:{ primero = nuevoNodo
ultimo = nuevoNodo
}
No: { nuevo.AsignaSig(primero)
primero.AsignaAnt(nuevo)
primero = nuevo }
}
insertarFinD(entero nuevoDato){ //Inserta al final de la Lista

Es (EsVacia()) Si:{ primero = nuevoNodo
ultimo = nuevoNodo
}
No: { nuevo.AsignaAnt(ultimo)
ultimo.AsignaSig(nuevo)
ultimo = nuevo }
}
insertarOrdenadaD(entero nuevoDato){ //Insertar en Lista Doble Ordenada

Nodo-D x, ant, nuevo
Es (EsVacia( ))Si:{insertarPrincipioD(nuevoDato)
retorne
}
x = primero( )
Mientras (x!=null && x.RetorneDato() < nuevoDato)
x= x.Retorne_Sig()
Es(x = = null)Si:{insertarFinD(nuevoDato)
retorne; }
Es(x = = primero( ))Si: insertarPrincipioD(nuevoDato)
No:{
nuevoNodo = new Nodo_D(nuevoDato)
nuevoNodo.AsignaSig(x)
nuevoNodo.AsignaAnt(x.Retorne_Ant( ))
x.RetorneAnt().AsignaSig(nuevoNodo)
x.AsignaAnt(nuevoNodo)
}
}
Nodo_D Buscar_Nodo(entero d){ // Buscar nodo de un determinado dato
Nodo_D x
x=primero( )
Mientras(x!= null ∧ x.RetorneDato( )!=d)
x = x.RetorneSig()
retorne(x) //si no existe dato retorna x =null
}
eliminar(entero d){ // Elimina un elemento de la Lista Doble

Nodo-D x
Es(EsVacia( )){Si:{Muestre “Lista Vacia"
retorne
}
x =Buscar_Nodo(d)
Es(x= = null)Si:{ Muestre "No existe "+d+" En Lista"
retorne
}
Es(x = = primero( ))Si{primero=primero.RetorneSig( )
Es(primero= =null)Si: ultimo=null
No: primero.AsignaAnt(null)
}
No: { x.RetorneAnt().AsignaSig(x.RetorneSig( ))
Es(x= = ultimo( )) Si: ultimo = x.RetorneAnt( )
No: x.RetorneSig().AsignaAnt(x.RetorneAnt( ))
}
}
mostrarID( ){ //Mostrar Lista Doble de izquierda a derecha

Nodo-D x
retorne
}
x = primero( )
Mientras(x!=null) {
Muestre x.RetorneDato( )
x = x.RetorneSig( )
}
}
mostrarDI( ){ //Mostrar Lista Doble de derecha a izquierda

Nodo-D x
retorne }
x = ultimo( );
Mientras(x!=null) {
x = x.RetorneAnt( )
}
}
} // Fin Clase Lista Doble Enlazada
Listas Simples Enlazadas Circulares
La lista simple enlazada circular es una Lista Simple en donde el último elemento en su
campo de enlace al siguiente, almacena la referencia del primero de la lista
Representación de una Lista Simple Enlazada:
5 9 3 12
dato sig
Primero Ultimo
La ventaja de la lista simple circular enlazada, es que partiendo de cualquier nodo de la

lista se puede recorrer completamente dicha lista.
La Clase Lista Simple Enlazada Circular hereda de la clase Lista Simple Enlazada.
Definición de la Clase Lista Simple Enlazada Circular

Clase ListaCircular hereda de ListaEnlazada{
//Inserta al principio de Lista Simple Circular

insertar_principio(entero nuevoDato){
Nodo nuevoNodo = new Nodo(nuevoDato)
Es(EsVacia())Si:{ primero = nuevoNodo
ultimo = nuevoNodo
primero.Asigna_Sig(nuevoNodo)
}
No:{ nuevoNodo.Asigna_Sig(primero())
ultimo.Asigna_Sig(nuevoNodo)
primero = nuevoNodo
}
}
//Inserta al final de Lista Simple Circular

insertar_fin(entero nuevoDato){
Es(EsVacia())Si:{ primero = nuevoNodo
ultimo = nuevoNodo
}
No:{ ultimo.Asigna_Sig(nuevoNodo)
ultimo = nuevoNodo
ultimo.Asigna_Sig(primero())
}
}
//Insertar en Lista Simple Circular Ordenada
insertar_ordenada(entero nuevoDato){
Nodo x, ant, nuevoNodo
entero sw=0
Es(EsVacia( ))Si:{insertar_principio(nuevoDato)
retorne
}
x = primero( )
Haga {
Es(nuevoDato > x.Retorne_Dato()) Si: x = x.Retorne_Sig()
No: sw=1
Mientras ((x!=primero()) && (sw= =0))
Es(x = = primero())Si: Es(sw= =0)Si: insertar_fin(nuevoDato)
No: insertar_principio(nuevoDato)
No{ nuevoNodo = new Nodo(nuevoDato)

ant=Anterior(x)
ant.Asigna_Sig(nuevoNodo)
nuevoNodo.Asigna_Sig(x)
}
}
// Buscar nodo de un determinado dato

Nodo Buscar_Nodo(entero d){
Nodo x
entero sw=0
x=primero()
Haga{
Es(x.Retorne_Dato()= =d)Si: sw=1
No: x = x.Retorne_Sig()
Mientras((x!=primero()) && (sw= =0))
Es(sw= =1)Si: retorne(x)
No: retorne(null)
}
// Elimina un elemento de Lista Simple Circular

eliminar(entero d){
Nodo x, ant
Es(EsVacia())Si: {muestre "Lista Vacia"
retorne
}
x=Buscar_Nodo(d)
Es(x= =null) Si:{ Muestre No existe "+d+" en Lista" retorne
}
Es (x = = primero()) Si: Es(x = = ultimo())Si: primero= ultimo=null
No:{ primero=primero.Retorne_Sig()
ultimo.Asigna_Sig(primero())
}
No:{ant=Anterior(x)
ant.Asigna_Sig(x.Retorne_Sig())
Es(x= =ultimo()) Si: ultimo=ant
}
}
//Mostrar la Lista
mostrar( ){
Nodo x
x=primero()
Haga{
Muestre x.Retorne_Dato()
x= x.Retorne_Sig();
} Mientras (x!=primero())
}
} // fin clase lista circular
Listas Doblemente Enlazadas y Circulares
Una lista doblemente enlazada y Circular es una lista doblemente enlazada en donde el
primer elemento en su campo de anterior almacena la referencia del último elemento de
la lista y el último elemento en su campo de siguiente almacena la referencia del primer
elemento de la lista
Representación de una Lista Doblemente Enlazada Cicular:
5 9 3 12
Primero Ultimo
Definición de la Clase Lista Doblemente Enlazada Cicular

Clase Lista_Doble_Circular{
Nodo_D primero, ultimo
Lista_Doble_Circular( ){ // Constructor de la Lista Doble

primero = ultimo= null
}
Nodo_D primero( ){ // Ubica el primer elemento de la lista

retorne(primero)
}
Nodo_D ultimo( ){ // Ubica el último de la lista

retorne(ultimo)
}

retorne(primero = = null)
}
insertarPrincipioDCir(entero nuevoDato){ //Inserta al principio de la Lista

ultimo = nuevoNodo
nuevo.AsignaSig(primero)
nuevo.AsignaAnt(primero)
}
nuevo.AsignaAnt(ultimo)
primero = nuevo }
}
insertarFinDCir(entero nuevoDato){ //Inserta al final de la Lista

ultimo = nuevoNodo
nuevo.AsignaSig(primero)
nuevo.AsignaAnt(primero)
}
nuevo.AsignaAnt(ultimo)
ultimo = nuevo }
}
insertar_ordenadaDCir(entero nuevoDato){
Nodo-D x, , nuevoNodo
entero sw=0
Es(EsVacia( ))Si:{insertar_principioDCir(nuevoDato)
retorne
}
x = primero( )
Haga {
Es(nuevoDato > x.Retorne_Dato()) Si: x = x.Retorne_Sig()
No: sw=1
} Mientras ((x!=primero()) && (sw= =0))
Es(x = = primero( ))Si: Es(sw= =0)Si: insertar_finDCir(nuevoDato)

No: insertar_principioDCir(nuevoDato)
No{ nuevoNodo = new Nodo(nuevoDato)

nuevoNodo.Asigna_Sig(x)
nuevoNodo.Asigna_Ant(x,Retorne_Ant( ))
x.RetorneAnt( ).Asigna_Sig(nuevoNodo)
x.AsignaAnt(NuevoNodo)
}
}

Nodo-D Buscar_Nodo(entero d)
{
Nodo_D x
entero sw = 0
x = primero()
Haga{
Es(x.Retorne_Dato( ) = =d)Si: sw=1
No: x = x.Retorne_Sig()
} Mientras((x!=primero()) && (sw= =0))
Es(sw= =1)Si: retorne(x)
No: retorne(null)
}
eliminar(entero d){ // Elimina un elemento de la Lista Doble

Nodo-D x
retorne
}
x =Buscar_Nodo(d)
Es(x= = null)Si:{ Muestre "No existe "+d+" En Lista"
retorne
}
Es(x = = primero( ))Si:
Es(primero.Retorne_Sig( ) = = primero)Si:ultimo=primero = null
No:{primero= primero.Retorne_Sigt()
primero.AsignaAnt(ultimo)
ultimo.AsignaSig(primero)
}
No: { x.RetorneAnt().AsignaSig(x.RetorneSig( ))
Es(x= = ultimo( )) Si: ultimo = x.RetorneAnt( )
x.RetorneSig().AsignaAnt(x.RetorneAnt( ))
}
}
mostrarID( ){ //Mostrar Lista Doble de izquierda a derecha

Nodo-D x
retorne
}
x = primero( )
haga{
x = x.RetorneSig( )
} Mientras(x!= primero)
}
mostrarDI( ){ //Mostrar Lista Doble de derecha a izquierda

Nodo-D x
retorne }
x = ultimo( );
Haga{
x = x.RetorneAnt( )
} Mientras(x!=ultimo)
}
} // Fin Clase Lista Doble Enlazada Circular
Listas Simples Enlazadas con Nodo Cabeza
Es una lista enlazada que contiene un nodo especial denominado Nodo Cabeza que se
encuentra al principio de ella. El nodo Cabeza contiene en su campo de información un
dato no válido con respecto a los demás elementos de la lista. También se puede utilizar
para almacenar información global de la lista, como por ejemplo, el número de
elementos de la lista, el promedio de los valores, etc.
Representación de una Lista Simple Enlazada con Nodo Cabeza:
9 3 12 null
dato sig
primero Ultimo
Lista Simple Enlazada Con Cabeza (LSC) Vacía se representa de la siguiente manera:
null
primero ultimo
La clase LSC hereda de la clase lista SimpleEnlazada.
A continuación se muestran los métodos que se modifican en la Clase LSC
Clase LSC{
Nodo primero, ultimo
LSC( ){ // Constructor de LSC

primero = new Nodo(-1) //se asume que los datos son enteros positivos
ultimo = primero
}
Nodo Cabeza( ){ // Retorna la referencia del Nodo Cabeza

retorne(primero)
}
Nodo primero( ){ // Ubica el primer elemento con información de la lista

retorne(Cabeza( ). Retorne_Sig( ))
}
Nodo ultimo( ){ // Ubica el último elemento de la lista
retorne(ultimo);
}

retorne (primero( ) = = null):
}
//Inserta al principio de LSC (inserta después del Nodo Cabeza)

insertar_principio(entero nuevoDato){
Es(EsVacia() )Si:{ primero.Asigna_Sig(nuevoNodo)
ultimo = nuevoNodo
}
No:{ nuevoNodo.Asigna_Sig(primero())
}
}
//Inserta al final de Lista Simple Circular

insertar_fin(entero nuevoDato){
Es(EsVacia())Si: primero.Asigna_Sig(nuevoNodo)
No: ultimo.Asigna_Sig(nuevoNodo)
ultimo = nuevoNodo
}
Insertar en Lista Simple Circular Ordenada

El procedimiento es el mismo que se definió para la clase Lista Simple

Nodo Buscar_Nodo(entero d){
Nodo x
x=primero( ) // primero como método
Mientras(x!= null ∧ x.Retorne_Dato()!=d)
x=x.Retorne_Sig();
retorne(x); //si no existe dato retorna x =null
}
// Elimina un elemento de LSC

eliminar(entero d){
Nodo x, ant
Es(EsVacia())Si: {muestre "Lista Vacia"
retorne
}
x=Buscar_Nodo(d)
Es(x= =null) Si:{ Muestre No existe "+d+" en Lista"
retorne }
ant=Anterior(x)
ant.Asigna_Sig(x.Retorne_Sig())
Es(x= =ultimo())Si: ultimo=ant
//Mostrar la Lista
mostrar( ){
Nodo x
x = primero() //método de LSC
Mientras(x!=null) {
Muestre x.Retorne_Dato()
x = x.Retorne_Sig()
}
}
} // fin clase lista circular
La lista Simple Enlazada Circular con Cabeza (LSCC) Vacía se representa de la

siguiente manera:
primero ultimo
La Lista Doble Enlazada Con Cabeza (LDC) Vacía se representa de la siguiente

manera:
null
null
primero ultimo
La Lista Doble Enlazada Circular con Cabeza (LDCC) Vacía se representa de la

siguiente manera:
primero ultimo
Ejercicios
Implementar las operaciones básicas sobre los diferentes tipos de listas con Cabeza
EJERCICIOS LISTAS ENLAZADAS
Elaborar los siguientes métodos:
1. Dada una Lista Simple Encadenada retornar la lista al revés, es decir que el
primer elemento quede de último, el segundo de penúltimo y así sucesivamente.
Nota: No se puede crear una nueva lista.
2. Dadas dos listas simplemente encadenadas y circulares L1 y L2 ordenadas por
el campo de dato, intercale los elementos de L2 en L1 de tal forma que L1
permanezca ordenada.
3. Dada una Lista Simple Encadenada con registro cabeza L1 y un valor V1, crear
las listas L2 y L3 simplemente encadenadas y circulares, de tal forma que L2
contenga los valores menores o iguales a V1 en L1 y L3 contenga los valores
mayores a V1.
4. Dada una Lista Simple Encadenada y circular, eliminar de la lista un
determinado dato, todas las veces que se presente.
5. Dada una Lista Doblemente Encadenada y circular L1, encontrar los elementos
que poseen el valor mayor de la lista y el valor menor de la lista y luego,
intercambie dichos elementos.
6. Dada una Lista Doblemente Encadenada y circular ordenada con valores
repetidos, eliminar los valores repetidos de la lista.
7. Dada una Lista Simple Encadenada, circular y con cabeza, encontrar el
promedio de los valores contenidos en la lista.
8. Dada una Lista Doblemente Encadenada, circular y con cabeza, encontrar el
menor valor de la lista, y eliminarlo de ella.
9. Dadas las listas L1 y L2 Simplemente Encadenadas circulares y con cabeza,
encontrar si dichas listas son Semejantes, es decir si cada valor de la lista L1 se
presenta al menos una vez en la lista L2.
10. Dadas las listas L1 y L2 Simplemente Encadenadas circulares, encontrar si
dichas listas son Iguales, es decir si cada valor de la lista L1 se presenta
exactamente una vez en la lista L2.
11. Dadas las listas L1 y L2 Simplemente Encadenadas y circulares ordenadas y sin
valores repetidos dentro de cada una de ellas, crear las listas L3 y L4, en donde
L3 contenga los valores que se encuentran tanto en L1 como en L2 y L4
contenga el resto de valores.
12. Dada una Lista Simple Encadenada y circular, elaborar un método que retorne la
suma de los valores contenidos en las posiciones pares de la lista.
13. Dada una Lista Simplemente Encadenada, eliminar I elementos de la lista a
partir del elemento ubicado en la k-ésima posición de la lista.
14. Dada una Lista Simplemente encadenada, insertar I elementos en la lista a partir
de la k-ésima posición de la lista.
TALLER DE LISTAS ENCADENADAS
Elaborar los siguientes métodos:
1. Dada una Lista Simple Encadenada retornar la lista al revés, es decir que el
primer elemento quede de último, el segundo de penúltimo y así sucesivamente.
2. Dadas dos listas simplemente encadenadas y circulares L1 y L2 ordenadas por
el campo de dato, intercale los elementos de L2 en L1 de tal forma que L1
permanezca ordenada.
3. Dada una Lista Simple Encadenada con registro cabeza L1 y un valor V1, crear
las listas L2 y L3 simplemente encadenadas y circulares, de tal forma que L2
contenga los valores menores o iguales a V1 en L1 y L3 contenga los valores
mayores a V1.
4. Dada una Lista Doblemente Encadenada y circular L1, encontrar los elementos
que poseen el valor mayor de la lista y el valor menor de la lista y luego,
intercambie dichos elementos.
5. Dada una Lista Doblemente Encadenada y circular ordenada con valores
repetidos, eliminar los valores repetidos de la lista.
6. Dada una Lista Simple y circular, encontrar el promedio de los valores
contenidos en la lista.
7. Dadas las listas L1 y L2 Simplemente Encadenadas y circulares ordenadas y sin
valores repetidos dentro de cada una de ellas, crear las listas L3 y L4, en donde
L3 contenga los valores que se encuentran tanto en L1 como en L2 y L4
contenga el resto de valores.
8. Dada una Lista Simplemente Encadenada, eliminar I elementos de la lista a
partir del elemento ubicado en la k-ésima posición de la lista.
9. Dada una Lista Simplemente encadenada, insertar I elementos en la lista a partir
de la k-ésima posición de la lista.
Manejo de Caracteres
Los lenguajes de programación utilizan juegos a alfabetos para representar información
de tipo carácter. Se han definido diferentes alfabetos, entre ellos se encuentran:
- ASCII (American Standard Code for Information Interchange): Este alfabeto

utilizaba inicialmente 7 bits para representar un caracter, es decir que se podían
representar 128 caracteres. Luego se definió el ASCII extendido de 8 bits en donde
se representan 256 caracteres diferentes. Este código es empleado principalmente
en los computadores personales.
- EBCDIC (Extended Binary Coded Decimal Interchange Code) : utiliza 8 bits para
representar el conjunto de caracteres.
- UNICODE: Se considera como el alfabeto universal cuya principal aplicación es la
internet. En este alfabeto se emplean 16 bits y consta de caracteres de varios
idiomas.
Un alfabeto consta de los siguientes tipos de caracteres:

. Letras: A, B, …., Z, a, b,…, z
. Dígitos: 0, 1, …, 9
. Especiales: +, *, ., , &, %, $, ¿, >, etc.
. Control: son caracteres que no se muestran pero que realizan operaciones relacionadas
con la escritura de textos. Como por ejemplo, borrar carácter, insertar línea, etc.
Hilera: Conjunto de caracteres definidos bajo un alfabeto. Por ejemplo:

H = “abcgg”
La hilera vacía se representa como:

H = “” (comillas seguidas)
Las principales operaciones que se definen sobre la clase Hilera son las siguientes:
Clase Hilera
{
Hilera( ) //constructor
entero LONG(hilera) // retorna la longitud de una hilera
CONCAT (hilera) //concatena una subhilera en una hilera
hilera SUB(entero, entero) //extrae una subhilera de una hilera
entero POS(hilera) // retorna la posición a partir de la cual se encuentra una subhilera
en una hilera
ELIMINAR(entero, entero) //elimina una subhilera de una hilera
INSERTAR(entero, hilera) //inserta una subhilera en una hilera a partir de una
posición dada
REM(entero, entero, hilera) //reemplaza una subhilera por otra subhilera
}
Implementación de Operaciones en Hileras
- Longitud de una hilera:

Si H es una hilera y J un entero, la operación:
J = H.LONG( )
retorna el número de caracteres contenidos en la hilera H.
Por ejemplo, si H = “abcdijk”

J = H.LONG ( ) = 7
Si H = ”” (la hilera vacía)

J = H.LONG ( ) = 0
- Concatenación de hileras
Sean H, H1dos variables de tipo hileras. La operación:
H.CONCAT( H1)
Concatena los caracteres contenidos en la hilera H1 en la hilera H. La hilera H1 no se
modifica.
Por ejemplo: Si H = “llueve” H1= “hoy”
H.CONCAT( H1)
Luego de la operación la hilera H = “lluevehoy”
El operador “+” puede usarse también como operador de concatenación.
Por ejemplo, si se realiza la operación:
H = “no” + “ “ + H + “ “ + H1
En la hilera H se almacena:
H = “no llueve hoy”
- Extracción de hileras
Sean H, H1dos variables de tipo hileras y las variables I, K de tipo entero. La
operación:
H1 = H.SUB(I, K)
Extrae de la hilera H, a partir del carácter ubicado en la I-ésima posición de la hilera,

K caracteres y los almacena en la hilera H1. Luego de la operación la hilera H no se
modifica.
Por ejemplo, si H = “abcdefghijk”

H1 = H.SUB(1, 3) H1 = “abc”
H1 = H.SUB(3, 4) H1 = “cdef”
H1 = H.SUB(6, 8) H1 = “fgjijk”
Casos Especiales:
. Si se omite el segundo parámetro, se extrae hasta el final de la hilera H.
H1 = H.SUB(3) H1 = “cdefghijk”
. Si la posición I no existe en la hilera, el resultado es la hilera vacía. Por ejemplo,
H1 = H.SUB(14) H1 = “”
H1 = H.SUB(-1) H1 = “”
- Posición
Sean H, H1dos variables de tipo hileras y la variable I de tipo entero. La operación:
I = H.POS(H1)
retorna la posición en donde comienza la primera ocurrencia de la hilera H1 en la
hilera H. Si H1 no existe en H, retorna un valor de 0.
Por ejemplo, si H = “abcxyefxyzijxyz” y H1 = “xyz”
I = H.POS(H1)
retorna un valor de I = 8
Si H1 = “xyw”
I = H.POS(H1)
retorna I = 0.
La operación POS también se define de la siguiente manera:

I = H.POS(H1, K)
Busca a partir de la posición K de la hilera H, la posición en donde se presenta la

ocurrencia de la hilera H1.
Por ejemplo, si H = “abcxyeabyzijxyz” y H1 = “ab”
I = H.POS(H1, 5)
retorna I = 7.
Ejercicio 1:
Elaborar un algoritmo que cuente el número de espacios en blanco que se presentan
en un texto representado en una hilera.
Entrada:
TEXTO: variable hilera que contiene el texto
Resultado:
Cont: variable numérica entera. Número es espacios en blanco en el texto.
Programa Contar_Espacios
{
hilera Texto
entero k, Cont = 0
Entre Texto
k = Texto.POS(“ “) //busca la primera ocurrencia del espacio en blanco
Mientras ( k != 0) haga
{ Cont = Cont + 1
k = Texto.POS(“ “, k+1)
}
Muestre “El espacio en blanco se presenta: “ + Cont + “veces en el texto”
}
Ejercicio 2:
Elaborar un algoritmo que cuente el número de veces que se presentan cada una de
las letras del alfabeto en un texto representado en una hilera.
Entrada:
Resultado:
CONT[26]: arreglo de valores numéricos que contiene el número de veces que se
presenta cada letra.
Análisis del problema:

Si se asume un alfabeto de 26 letras, el procedimiento consiste en recorrer el texto
para buscar y contar las ocurrencias de cada una de las letras.
Si se define una hilera con las letras del alfabeto, como por ejemplo:
ALFA = “abcdefghijklmnopqrstuvwxyz”
Un arreglo de 26 posiciones en donde se va a almacenar las veces que se presenta

cada letra, haciendo una correspondencia entre la posición que ocupa la letra en la
hilera ALFA, y la posición en el arreglo CONT. Así, CONT[ 1] contendrá el número
de veces que se presenta la letra “a”, CONT[2] el número de veces que se presenta
la letra “b”, y así sucesivamente. Se asume también que las letras del texto se
encuentran todas en minúscula.
El algoritmo se puede resolver de dos formas: la primera consiste en buscar y contar

la primera letra de ALFA, que es la “a”, luego la segunda letra y así hasta la letra “z”.
La segunda forma consiste en tomar cada carácter del texto para compararlo con las
letras de la hilera ALFA, si por ejemplo el carácter a comparar es la letra “c”, al
aplicar la operación POS, el resultado es igual a 3, pero si el carácter a comparar es
por ejemplo un “.”, el resultado es cero. O sea que de esta manera, el resultado de
POS nos indicara la posición del arreglo CONT que se debe incrementar.
A continuación se presenta la implementación del algoritmo utilizando la segunda

forma.
Programa Contar_Letras
{
Hilera TEXTO, ALFA = “abcdefghijklmnopqrstuvwxyz”
entero CONT[ 26], j
Para i = 1 hasta 26
CONT[i] = 0
Entre TEXTO
Para i = 1 hasta TEXTO.LONG( ) {
j= ALFA.POS(TEXTO.SUB(i, 1))
Es (j != 0 ) Si: CONT[ j ] = CONT[ j] + 1
}
Para i = 1 hasta 26
Muestre “La letra” + ALFA.SUB(i, 1) + “se presenta: ” + CONT[i] +” veces”
}
Ejercicio 3:
Elaborar un algoritmo que cuente el número de veces que se presenta una
determinada palabra en un texto representado en una hilera.
Entrada:
PAL: variable hilera que contiene la palabra a contar
Resultado:
Cont: variable numérica que contiene el número de veces que se encuentra la
palabra.

Se debe de tener en cuenta que la palabra de entrada no forme parte de otra palabra.
O sea, que a la palabra de entrada se le inserta un blanco al principio y al final. Lo
mismo al texto de entrada.
Programa Contar_Palabra
{
Hilera TEXTO, PAL
entero Cont, k
Entre TEXTO, PAL
TEXTO = “ “ + TEXTO + “ “
PAL = “ “ + PAL + “ “
k = Texto.POS(PAL) //busca la primera ocurrencia de la palabra
{ Cont = Cont + 1
k = Texto.POS(PAL, k + PAL.LONG( ) – 1 )
}
Muestre “La palabra ” + PAL + se presenta: “ + Cont + “veces en el texto”
}
- Eliminación en Hileras
La operación para eliminar un conjunto de caracteres de una hilera H, se define de la
siguiente manera:
H.ELIMINAR(I, K)
Elimina de la hilera H a partir del carácter ubicado en la I-ésima posición de H, K
caracteres.
Por ejemplo, si H = “abcxyefxyzijxyz”
H.ELIMINAR(4,3)
La hilera H se modifica y contendrá luego de la operación:

H = “abcfxyzijxyz”
Utilizando la operación SUB, la operación para eliminar en una hilera se puede

implementar así:
H = H.SUB(1, I -1) + H.SUB( I + K)

En el ejemplo anterior, si H = “abcxyefxyzijxyz”
H.ELIM(4,3)
Es equivalente a:
H = H.SUB(1, 3) + H.SUB(7)
H = “abc” + “fxyzijxyz”
H = “abcfxyzijxyz”
Ejercicio 1:
Elaborar un algoritmo que elimine los espacios en blanco si entre cada una de las
palabras de un texto se presenta más de uno.
Entrada:
Resultado:
TEXTO: texto que contiene un sólo espacio en blanco entre palabras
Programa Eliminar_Espacios
{
hilera Texto
entero k
Entre Texto
k = Texto.POS(“ “) //busca la primera ocurrencia de 2 espacios en blanco
{ Texto.ELIMINAR( k, 1)
k = Texto.POS(“ “, k) //busca las siguientes ocurrencias de 2 espacios en
blanco
}
Muestre Texto
}
Ejercicio 2:
Elaborar un algoritmo que elimine los signos de puntuación en un texto
Entrada:
TEXTO: variable hilera que contiene el texto con signos de puntuación
Resultado:
TEXTO: texto sin signos de puntuación

Se puede definir una hilera que contenga los signos de puntuación a eliminar. En este
caso el algoritmo se puede realizar de dos formas. En la primera forma, se puede
comparar cada uno de los caracteres del texto con los caracteres contenidos en la
hilera de los signos y si existe, se elimina el carácter del texto. La segunda forma
consiste en tomar cada uno de los signos de la hilera, buscarlo en el texto y cada vez
que lo encuentre, se elimina del texto. La implementación del algoritmo utilizando la
segunda forma es la siguiente:
Programa Eliminar_Signos
{
hilera Texto, Signos = “;,:,&%$!¡¿?*+><`{}^[ ]”
entero k
Entre Texto
Para J = 1 hasta signos.LONG( )
{
k = Texto.POS(Signos.SUB(J, 1))
{ Texto.ELIMINAR( k, 1)
k = Texto.POS Signos.SUB(J, 1), k)
}
}// fin ciclo Para
Muestre Texto
}
Ejercicio 3:
Elaborar un algoritmo que elimine en un texto una determinada palabra, todas las
veces que se presente dicha palabra.
Entrada:
PAL: variable hilera que contiene la palabra eliminar del texto
Resultado:
TEXTO: texto sin la palabra que se eliminó

A la palabra de entrada se le inserta un blanco al principio y al final. Lo mismo al
texto de entrada. Se busca la palabra en el texto y cada vez que se encuentre se
elimina.
Programa Eliminar_Palabra
{
hilera Texto, PAL
entero k
Entre Texto, PAL
PAL = “ “ + PAL + “ “
k = Texto.POS(PAL) //busca la primera ocurrencia de la palabra
{ Texto.ELIMINAR(k, PAL.LONG( ) -1)
k = Texto.POS(PAL, k )
}
Muestre Texto
}
- Inserción en Hileras
La operación para insertar un conjunto de caracteres en una hilera H, se define de la
siguiente manera:
H.INSERTAR( I, H1)
Inserta en la hilera H a partir de la I-ésima posición, la hilera H1.
Por ejemplo, si H = “abcdefgh” y H1=”xxxxxxx”
H.INSERTAR(4, H1)

H = “abcxxxxxxxdefgh”
Utilizando la operación SUB, la operación para insertar en una hilera se puede

implementar así:
H = H.SUB(1, I - 1) + H1 + H.SUB( I)
Ejercicio 1:
Elaborar un algoritmo que dado un texto y dos palabras, PAL1 Y PAL2, inserte en el
texto la palabra PAL2 a continuación de la palabra PAL1, todas las veces que PAL1
se presente en el texto.
Entrada:
PAL1, PAL2: variables hileras
Salida:
TEXTO: texto con la palabra PAL2

El algoritmo consiste en buscar en el texto las ocurrencias de PAL1, y cada vez que
se encuentre se inserta la palabra PAL2.
Programa Insertar_Palabra
{
hilera Texto, PAL1, PAL2
entero l
Entre Texto, PAL1, PAL2
PAL1 = “ “ + PAL1 + “ “
PAL2 = PAL2 + “ “
l = Texto.POS(PAL1) //busca la primera ocurrencia de PAL1
Mientras ( l != 0) haga
{ Texto.INSERTAR(l + PAL1.LONG( ), PAL2)
l = Texto.POS(PAL1, l + PAL1.LONG( ) + PAL2.LONG( ) - 1)
}
Muestre Texto
}
- Reemplazo en Hileras
La operación para reemplazar un conjunto de caracteres en una hilera H, por otro
conjunto de caracteres, se define de la siguiente manera:
H.REEMPLAZAR( I, J, H1)
reemplaza en la hilera H a partir del carácter ubicado en la I-ésima posición, J

caracteres, por la hilera H1.
Por ejemplo, si H = “abcdefgh” y H1=”xxxxxxx”
H.REEMPLAZAR(3, 2, H1)

H = “abxxxxxxxefgh”
La operación de reemplazar consta de dos operaciones:

1. H.ELIMINAR( I, J)
2. H.INSERTAR(I, H1)
En el ejemplo anterior, H.REEMPLAZAR(3, 2, H1)
1. H.ELIMINAR(3, 2)
Luego de la operación H= “abefgh”
2. H.INSERTAR(3, H1)
H = “abxxxxxxefgh”
Ejercicio 1:
Elaborar un algoritmo que dado un texto y dos palabras, PAL1 Y PAL2, reemplace
en el texto la palabra PAL1 por la palabra PAL2, todas las veces que PAL1 se
presente en el texto.
Entrada:
PAL1, PAL2: variables hileras
Salida:
TEXTO: texto con la palabra reemplazada

El algoritmo consiste en buscar en el texto las ocurrencias de PAL1, y cada vez que
se encuentre se reemplaza por la palabra PAL2.
Programa Reemplazar_Palabra
{
hilera Texto, PAL1, PAL2
entero l
Entre Texto, PAL1, PAL2
PAL1 = “ “ + PAL1 + “ “
PAL2 = “ “ + PAL2 + “ “
l = Texto.POS(PAL1) //busca la primera ocurrencia de PAL1
Mientras ( l != 0) haga
{ Texto.REEMPLAZAR(l, PAL1.LONG( ), PAL2)
l = Texto.POS(PAL1, l + PAL2.LONG( ) - 1)
}
Muestre Texto
}
TALLER SOBRE MANEJO DE CARACTERES
1. Dado un texto y una palabra, elaborar un método que reemplace la palabra por
un ‘*’, todas las veces que se presente dicha palabra en el texto.
2. Elaborar un método que reciba como entrada un caracter y que retorne un valor
booleano, en donde un valor de verdadero indica que el carácter de entrada es
una letra.
3. Dado un texto, mostrar las palabras que contienen una sola vocal.
4. Elaborar un método que dado un texto y una palabra, retorne la posición en que
se encuentra la palabra en el texto. Si la palabra no existe, retorna 0.
Nota: No utilizar la operación POS.
5. Elaborar un método que reciba como entrada un texto y retorne la palabra del
texto que tenga la mayor longitud.
6. Elaborar un método que dado un texto, retorne el texto al revés.
7. Elaborar un método que reciba como entrada un caracter y que retorne un valor
booleano, en donde un valor de verdadero indica que el carácter de entrada es un
signo de puntuación.
8. Dado un texto, contar las veces que se presentan cada una de las vocales.
9. Dado un texto, encontrar las veces que se presentan cada una de las palabras del
texto. Se debe mostrar cada una palabras ordenadas alfabéticamente y las veces
que se presentan.
10. Un palíndromo es una palabra, número o frase que se lee igual hacia adelante
que hacia atrás. Si se trata de un número, se llama capicúa. Como por ejemplo,
oso, radar, anilina, etc. O las frases, “Dábale arroz a la zorra el abad”, “La ruta
nos aportó otro paso natural”. Cuando se trata de una frase, se ignoran los
espacios en blanco. Elaborar un método que retorne verdadero, si una hilera H,
dada es un palíndromo, de lo contrario retorna falso.
11. Un anagrama es una palabra o frase que resulta de la transposición de letras de
otra palabra o frase. Por ejemplo,
amor - roma
miedo - medio
salta - atlas
monja - jamon
lamina - animal
Cuando se trata de una frase, se ignoran los espacios en blanco. Elaborar un

método que dadas dos hileras H1 y H2, retorne verdadero si H2 es anagrama de
H1, de lo contrario retorna falso.
12. Elaborar un método que reciba un texto y retorne el número de palabras que
contengan al menos 4 vocales diferentes.
13. Dadas dos hileras caracteres H1 y H2, en donde cada una ellas contiene una lista
de nombres separados por espacios en blanco. Crear una nueva hilera que
contenga los nombres que son comunes a H1 y a H2.
Por ejemplo:
H1= “juan pedro carlos gloria lina mario marta”
H2= “mario andres alberto carlos monica lucia pedro”
La hilera resultante será:

R= “carlos mario pedro”
14. Dadas dos hileras caracteres H1 y H2, en donde cada una ellas contiene una
lista de nombres separados por espacios en blanco. Crear una nueva hilera que
contenga los nombres que no son comunes a H1 y a H2.
Por ejemplo:
H1= “juan pedro carlos gloria lina mario marta”
H2= “mario andres alberto carlos monica lucia pedro”
La hilera resultante será:

R= “juan gloria lina marta andres alberto monica lucia”
15. Elaborar un método que reciba como entrada una hilera H1 y retorne una nueva
hilera H2 codificada de la siguiente manera: Si un carácter de la hilera H1 es una
letra o un dígito, éste será reemplazado por el siguiente carácter correspondiente
de la tabla ASCII, excepto la letra ´Z’ que será reemplazada por la ‘A’ y el
dígito ‘9’ por el ‘0’. O sea que el dígito ‘1’ se reemplaza por el ‘2’ y la letra ‘P’
por la letra ‘Q’. Cualquier carácter que no sea letra o dígito se reemplaza por un
punto (‘.’)
16. Dada una lista encadenada H1 que contiene un caracter por elemento, elaborar
un método que inserte a partir de la posición I-ésima de la lista, los caracteres
contenidos en una lista simple enlazada H2.
17. Dada una lista encadenada H1 que contiene un carácter por elemento, elaborar
un método que elimine a partir del elemento ubicado en la posición I-ésima de la
lista, LONG caracteres.
18. Dada una lista encadenada H1 que contiene un caracter por elemento y una
hilera H2, elaborar un método que elimine de la lista H1, los caracteres
contenidos en H2.
Nota: Un caracter de H2 se puede presentar varias veces en H1.
19. Dada una lista encadenada H1 que contiene una palabra por elemento, y una
palabra PAL1, elaborar un método que elimine los elementos de la lista que
contienen la palabra PAL1.
20. Dada una lista encadenada H1 que contiene una palabra por elemento, y dos
palabras PAL1 y PAL2, elaborar un método que inserte en la lista, la palabra
PAL2, a continuación del elemento que contiene la palabra PAL1.
Colas
Una cola es una lista ordenada de elementos en donde las operaciones de inserción se
realizan por un extremo denominado ultimo (final) y las operaciones de borrado por el
otro extremo denominado principio(frente). Una cola se considera una estructura FIFO
(primero en entrar primero en salir).
Una de las aplicaciones de la estructura colas consiste en el manejo de recursos

compartidos por parte de un procesador central. Como por ejemplo, impresoras, discos,
etc,
Las operaciones básicas que se definen sobre una Cola son las siguientes:
- Construir la cola
- Determinar si la cola es vacía, o no.
- Encolar: inserta un elemento al final de la cola
- Desencolar: retira el primer elemento de la cola
- Primero: retorna el valor del primer elemento de la cola
Representación de una Cola

Una cola se puede representar en un arreglo o en una Lista Simple Enlazada.
- Representación en arreglos:
Se define el arreglo en donde se van a almacenar los elementos de la cola.
Por ejemplo,
Entero COLA[N]
1 2 3 4 5 6 7 8 9 10
35 20 15 8
primero = 0 ultimo = 4
Si N = 10 , significa que el arreglo almacenará 10 valores enteros
Se definen las variables que van a manejar las posiciones de Primero y Ultimo
de la cola. La variable primero contiene la posición anterior al primer elemento
de la cola. La variable ultimo contiene la posición del ultimo elemento que
ingresó a la cola.
entero primero, ultimo

Inicialmente primero= 0 y ultimo = 0
Condición de Cola Vacía:

Si primero = ultimo, indica que la cola está vacía
Método Cola Vacía:

Retorna verdadero si la cola se encuentra vacía
Es(primero = = ultimo) Si: retorne(verdadero);
No: retorne(falso);
}
Condición de Cola llena:

Cuando primero = 0 y ultimo = N
Método Cola LLena

Retorna verdadero si la cola se encuentra llena
booleano EsLlena( ){ // Determina el estado de la lista

Es(primero = = 0 && ultimo= =N) Si: retorne(verdadero);
No: retorne(falso);
}
Encolar: Inserta un elemento al final de la cola. Tiene como entrada el dato a

encolar
Encolar(entero nuevoDato){ //Inserta al final de la cola

Es (EsLlena()) Si: Muestre “Cola llena”
retorne
Es (ultimo = = N) Si: {
Para J = primero +1 hasta N
{ Cola[J – primero] = Cola[ J ]}
ultimo = ultimo – primero
primero = 0
}
ultimo = ultimo + 1
Cola[ultimo] = dato
retorne
}
Desencolar: Elimina el elemento que se encuentra en la posición siguiente de

primero de la cola. Retorna el dato que se encuentra de primero en la cola. Si cola
vacía, retorna -1
entero Desencolar( ){ //elimina primer elemento de la cola

Es (EsVacia()) Si: Muestre “Cola Vacia”
retorne (-1)
primero = primero + 1
retorne Cola[primero]
}
Primero: Retorna el dato que se encuentra de primero en la cola. Si cola vacía,

retorna -1
entero Primero( ){ //retorna el dato del primer elemento de la cola
Es (EsVacia()) Si: Muestre “Cola Vacia”
Retorne (-1)
retorne Cola[primero + 1]
}
Colas Circulares
Cuando se está utilizando la representación en arreglos y se va a encolar un

elemento, se puede presentar que se llega a la última posición del arreglo, es decir
ultimo = N, pero primero diferente de cero, y en este caso, se desplazan los
elementos del arreglo hasta la primera posición. Con el fin de evitar el
desplazamiento de los elementos, se propone utilizar un manejo diferente de las
operaciones para encolar y desencolar.
En las colas circulares se define un arreglo de tamaño N que contiene elementos

desde la posición 0 a la posición N – 1.
0 1 2 3 4 5
20 15 8
Inicialmente primero = ultimo = 0
Condición cola Vacia:

primero = ultimo
Procedimiento para Encolar:
0 1 2 3 4 5
8 6 30
Para manejar la cola en forma circular se utiliza la operación módulo, para que
cuando se presente el caso de que se llegue a la última posición del arreglo y la
cola no se encuentre llena, se comience a utilizar la posición 0 del arreglo, sin
tener que desplazar los elementos hacia la parte izquierda de él.
Los incrementos de las variables primero y ultimo utilizando la operación módulo

se realizan de la siguiente manera:
ultimo = (ultimo + 1) % N
primero = (primero + 1) % N
En el ejemplo, ultimo = 5 y si se desea encolar, como la cola no se encuentra

llena, la operación es:
ultimo = (5 + 1) % 6 = 6 % 6 = 0
y el nuevo elemento se almacena en la posición 0 del arreglo.
Condición de Cola Llena: En una cola circular, la cola se encuentra llena cuando
(ultimo +1)% N = primero
0 1 2 3 4 5
15 20 8 6 30
ultimo = 1 primero = 2
Como se puede observar en el ejemplo, permanece una posición sin utilizar.
El método para encolar es el siguiente:
Encolar (entero dato)

{
Es (Esllena()) Si: Muestre “Cola Llena”
Retorne
ultimo = (ultimo + 1) % N
Cola[ ultimo] = dato
}
El método para desencolar en la cola circular se define de la siguiente manera:
Entero Desencolar( )
{
Es (Esvacia()) Si; Muestre “Cola Vacia”
retorne (-1)
primero = (primero + 1)% N
retorne( Cola[primero]
}
El siguiente ejemplo, muestra el caso cuando se tiene un sólo elemento en el

arreglo y se va a desencolar
0 1 2 3 4 5
15
ultimo = 0 primero = 5
Para desencolar, se verifica si la cola se encuentra vacía. Como primero es decir,

5 es diferente de ultimo, hace (primero + 1)% N, que es igual a: (5 +1)% 6 = 0 y la
variable primero se ubica en la posición 0 del arreglo y desencola el 15. Si desea
desencolar de nuevo, las variables primero y ultimo se encuentran en la posición
0, lo que indica que la cola se encuentra vacía.
El método para retornar el valor del primer elemento de la cola circular se define
de la siguiente manera:
Entero Primero( )
{
Es (Esvacia()) Si: Muestre “Cola Vacia”
retorne (-1)
retorne( Cola[primero + 1)% N])
}
Manejo de 2 colas circulares en arreglos

Se define un sólo arreglo de tamaño N en donde se van a almacenar los valores de
las dos colas.
Inicialmente cada una de las colas contiene igual número de elementos, es decir,
M=N/2.
Si el arreglo se denomina Cola, los valores de la cola 1 se almacenarán en el

arreglo desde la posición 0 hasta la posición M-1 y los valores de la cola 2 desde
la posición M hasta la posición N-1
Si N = 10, M =10/2=5
M-1 M N-1
0 1 2 3 4 5 6 7 8 9
15 8 56 35 40
p1 u1 p2 u2
Se definen las variables que contienen el primero y el último de cada una de las 2
colas, en donde inicialmente contendrán los valores:
Para la cola 1: Para la cola 2:

p1 = u1= 0 p2 = u2= M
Condición cola1 vacía: p1 = u1

Condición cola 2 vacía: p2 = u2
Los incrementos de las variables utilizando la operación módulo se realizan de la

siguiente manera:
Para la cola 1: Para la cola 2:

u1 = (u1 + 1) % M u2 = (u2 – M + 1) % (N - M ) + M
p1 = (p1 + 1) % M p2 = (p2 – M + 1) % (N - M ) + M
En el ejemplo, u1 = 4 y si se desea encolar, como la cola 1 no se encuentra llena,

la operación es:
u1= (4 + 1) % 5 = 5 % 5 = 0
y el nuevo elemento de la cola 1 se almacenará en la posición 0 del arreglo
Para la cola 2, u2 = 7 y si se desea encolar,

u2= (7 - 5 + 1) % (10 - 5) + 5 = 3 % 5 + 5 = 8
y el nuevo elemento de la cola 2 se almacenará en la posición 8 del arreglo
Condición de Colas Llenas:

La cola 1 se encuentra llena cuando
(u1 +1)% M = p1
La cola 2 se encuentra llena cuando
(u2 – M +1)% (N – M) = p2
Encolar:
El método para encolar tiene como parámetros de entrada la cola en la que se va a
encolar (1 o 2) y el valor a encolar.
encolar(entero c, entero dato)

{
Es (c = = 1)Si:{ Es(EsLlenaCola1( )) Si: Cola_Llena(c) //Metodo de cola llena
u1=(u1+1)%M;
cola[u1] = dato
}
No:{Es (EsLlenaCola2( )) Si: Cola_Llena( c);
u2 = (u2 - M + 1) % (N - M) + M
cola[u2] = dato;
}
}
Método de Cola LLena:

En este método cuando una de las dos colas se llena y la otra cuenta con espacio
disponible, organiza la cola con espacio disponible de tal forma que se le pueda
asignar una posición adicional a la cola que lo necesita. Después, revisa la cola
que se encuentra llena para que cuando sea necesario, reubicar los elementos para
que quede disponible la posición en donde se va encolar el nuevo elemento.
En el método de Cola Llena se pueden presentar los siguientes casos:
La cola 1 está llena y la cola 2 tiene espacio, en este caso, en la cola 2 se pueden
presentar las siguientes situaciones:
- p2 = M: p2 se asigna a la última posición del arreglo, es decir, p2 = N – 1 y

en el caso de que u2 también sea igual a M, u2 = N - 1.
M-1 M N-1
0 1 2 3 4 5 6 7 8 9
20 15 8 56 35 40
p1 u1 p2 u2
Luego de la modificación de p2, la posición M puede ser utilizada por la cola

1, incrementando en uno el valor de M.
En este ejemplo, M que era igual a 5, queda con el valor de 6, lo que indica
que la cola 1 queda con 6 elementos y la cola 2 con 4.
- p2 > u2:
M-1 M N-1
0 1 2 3 4 5 6 7 8 9
20 15 8 56 24 35 40
p1 u1 u2 p2
En este caso, se desplazan una posición hacia la derecha los elementos que se
encuentran desde la posición u2 hasta la posición M y se incrementan las
variables u2 y M.
Después de que se cuenta con la posición disponible para la cola 1, que en

este ejemplo es la posición 5, se analiza cómo se encuentra la cola 1 para
poder encolar el nuevo elemento.
En el caso de que en la cola 1, u1 < p1, como se puede observar a

continuación:
M-1 M N-1
0 1 2 3 4 5 6 7 8 9
30 20 15 56 35 25
u1 p1 u2 p2
se desplazan una posición hacia la derecha los elementos que se encuentran

desde la posición p1 +1 hasta la M – 2 y la variable p1 se incrementa en 1.
En el ejemplo, el 56 que se encuentra en la posición 4 pasa a la posición 5 y

se incrementa p1, pasando a la posición 4. En este momento la posición 3
queda disponible para el nuevo elemento que se va a encolar en la cola 1.
Si la cola 2 está llena y la cola 1 tiene espacio, en la cola 1 se pueden

presentar las siguientes situaciones:
- u1 = M – 1: En este caso el valor que se encuentra en la última
posición de la cola 1 se lleva a la posición 0 del arreglo y se asigna, u2 = 0 y
M = M – 1. En este momento la posición que era antes M -1 queda
disponible para la cola 2.
- u1 < p1:
M-1 M N-1
0 1 2 3 4 5 6 7 8 9
30 32 56 30 35 38 41
u1 p1 u2 p2
se desplazan un lugar hacia la izquierda los elementos que se encuentran
desde la posición p1 +1 hasta la M – 1 y se decrementan en 1, p1 y M.
En el ejemplo, el 32 pasa a la posición 2 y el 56 a la posición 3, y al

decrementar p1 en 1, queda con el valor de 1 y M con el valor de 4. Luego de
este procedimiento, la cola 1 queda con 4 elementos y la cola 2 con 6
elementos.
Después de que se cuenta con la posición disponible para la cola 2, que en

este ejemplo es la posición 4, se analiza cómo se encuentra esta para poder
encolar el nuevo elemento.
En el caso de que en la cola2, u2 < p2, como se puede observar a

continuación:
M -1 M N-1
0 1 2 3 4 5 6 7 8 9
30 32 30 35 38 41
u1 p1 u2 p2
se desplazan un lugar hacia la izquierda los elementos que se encuentran desde

la posición M+1 hasta la u2 y se disminuye en 1 la variable u2.
En el ejemplo, el 30 pasa a la posición 4, el 35 a la posición 5 y u2 queda con el

valor de 5. En este momento queda la posición 6 disponible para encolar el
nuevo elemento en la cola 2.
El método tiene como parámetro de entrada la cola en la que se va a encolar y se

encuentra llena. En el método se valida si las dos colas están llenas y en este
caso, muestra el mensaje y termina.
Cola _Llena(entero c)
{
Es(c= =1)Si:{ Es(EsLlenaCola2( )) Si: Muestre "Las dos colas estan llenas "
Terminar
Es (p2= = M) Si: {p2= N -1
Es (u2 = = M) Si: u2 = N – 1
}
No: Es (p2 > u2) Si:{Para k=u2 hasta M, k- -
cola[k+1] = cola[k]
u2 = u2 + 1
}
M= M + 1
Es(u1 < p1)Si: {Para k=M – 1hasta p1+2, k- -
cola[k] = cola[k-1]
p1 = p1 + 1
}
}// fin si c es cola 1
No: Es (c= = 2)Si:{Es(EsLlenaCola1( ))Si:{Muestre "Las dos colas estan

llenas "
Terminar
}
Es(!(EsVaciaCola1()))Si: Es (u1= =M-1)Si: {cola[0]=cola[M-1]
u1=0
}
No: Es(u1 < p1)Si:{Parat k=p1 hasta M-2
cola[k] = cola[k+1];
p1 = p1 - 1;
}
M=M-1
Es(u2 < p2)Si: {Para k=M hasta u2 – 1
cola[k] = cola[k+1];
u2=u2 - 1;
}
} //fin si c es cola 2
}
Desencolar:
El método para desencolar tiene como parámetro de entrada la cola en la que se va
a encolar (1 o 2) y retorna el primer valor que se encuentra en la cola (-1, si la cola
está vacía).
Entero desencolar(entero c)
{
Es (c = = 1) Si: Es(EsVaciaCola1( )) Si: Muestre "cola 1 vacia"
retorne(-1)
No: p1 = (p1+1)%M
retorne( cola[p1] )
No: Es(EsVaciaCola2( )) Si: Muestre "cola 2 vacia"

return(-1)
No: p2 = (p2 - M + 1) % (N - M) + M
retorne(cola[p2])
}
Representación de una Cola en Lista Simple Enlazada
5 9 3 12 null
Primero Ultimo
La definición de la estructura Cola en una lista enlazada es la siguiente
Clase Cola{
nodo primero, ultimo
Cola( ) // constructor de la cola

Booleano EsVacia( )
Encolar( elemento) //inserta elemento al final de la cola
elemento Desencolar( ) //elimina primer elemento de la cola y retorna su valor
elemento Primero( ) //retorna valor del primer elemento de la cola
}
La implementación de los métodos es la siguiente:
Constructor:
Si la cola se encuentra vacía, las variables primero y ultimo contienen null.
En el constructor se inicializan estas dos variables en null.
Cola( )
{ primer = ultimo = null
}
Booleano EsVacia( ){ //retorna verdadero si la cola está vacia

retorne (primero = = null)
}
Encolar(entero d) //inserta un elemento al final de la cola

{
nodo nuevo = new nodo(d)
Es( EsVacia( )) Si: primero = ultimo = nuevo
No. {ultimo.Asigna_Sig(nuevo)
ultimo = nuevo
}
}
Entero Desencolar( ) //retira el primer elemento de la cola y retorna valor
{
entero d
Es( EsVacia( ))Si: Muestre “Cola Vacia”

retorne (-1)
d = primero. Retorne_Dato( )
primero = primero.Retorne_Sig( )
Es (primero = null) Si: ultimo = null
retorne ( d )
}
Entero Primero( ) // retorna valor del primer elemento de la cola

{
Es( EsVacia( ))Si: Muestre “Cola Vacia”
retorne (-1)
retorne( primero.Retorne_Dato( ) )
}
Manejo de N Colas en Listas Enlazadas

Se definen dos arreglos de tamaño N (número de Colas) de tipo nodo en donde el
primer arreglo denominado Primero almacena la referencia del primer elemento
de la Cola I y el segundo arreglo almacena la referencia del último elemento de la
Cola I. Si por ejemplo se tiene N =4 pilas, la representación es la siguiente:
Primero Ultimo
1 2
2 1 5 7
4 8
Inicialmente, Primero[ I] = Ultimo[I] = null
La Cola[I] es vacía si Primero[ I] o Ultimo[I] = null
Encolar: Tiene como entrada la Cola I en donde se va a encolar y el dato a encolar
Encolar(entero I, entero d) //inserta un elemento después del último de la Cola I

{
Es( EsVacia(I )) Si: Primero[ I] = Ultimo[ I] = nuevo
No. {Ultimo[I]..Asigna_Sig(nuevo])
Ultimo[ I ] = nuevo
}
}
Desencolar: El método para desencolar tiene como parámetro de entrada la cola I

en la que se va a encolar y retorna el primer valor que se encuentra en la cola I,
Retorna -1, si la cola I está vacía.
Entero Desencolar(entero I) //retira el primer elemento de la Cola I y retorna valor

{ entero d
Es( EsVacia( I))Si: Muestre “Cola ”+ I + “Vacia”
retorne (-1)
d = Primero[ I ]. Retorne_Dato( )
Primero [ I] = Primero[ I ].Retorne_Sig( )
retorne ( d )
}
Primero: Retorna el valor del Primer elemento que se encuentra en la Cola I.

Retorna -1 si Cola I se encuentra vacía.
Entero Primero(entero I )
{
Es( EsVacia( I))Si: Muestre “Cola” + I + “ Vacia”
retorne (-1)
retorne( Primero[ I ].Retorne_Dato( ) )

}
Pilas
Una Pila consiste de una lista ordenada de elementos en donde las operaciones de inserción y
borrado se realizan por un sólo extremo denominado Tope o Cima de la Pila. Una Pila se
considera una estructura LIFO (último en entrar primero en salir).
Las pilas tienen varias aplicaciones en las ciencias de la computación, entre ellas se encuentran
el manejo de las llamadas a métodos y la evaluación de expresiones en un compilador.
Las operaciones básicas que se definen sobre una Pila son las siguientes:
- Construir la Pila
- Determinar si la Pila es vacía, o no.
- Determinar si la Pila se encuentra llena, o no.
- Desapilar: inserta un elemento en el tope de la pila
- Desapilar: retira el elemento que se encuentra en el tope de la pila y retorna el valor.
- Tope: retorna el valor del tope de la pila
Representación de una Pila

Una pila se puede representar en un arreglo o en una Lista Simple Enlazada.
- Representación en arreglos:
Se define el arreglo en donde se van a almacenar los elementos de la pila y una variable
que contiene la posición del Tope de la Pila.
Inicialmente Tope = 0
1 2 3 4 5 6 7 8 9 10
45 80 12 30
Tope
Si N = 10, significa que el arreglo almacenará 10 valores enteros
Condición de Pila Vacía:

Si Tope = N, indica que la cola está vacía
Condición de Pila llena:

La pila se encuentra llena cuando Tope = N
La implementación de los métodos de una Pila representada en un arreglo es la siguiente:
Pila (entero N) // Constructor de la Pila

{
Pila = new arreglo[N]
Tope = 0
}
Método Pila Vacía:

Retorna verdadero si la pila se encuentra vacía
booleano EsVacia( ){ // Determina si la pila está vacía
retorne(Tope = = 0)
}
Método Pila LLena

Retorna verdadero si la pila se encuentra llena
booleano EsLlena( ){
retorne(Tope = = N)
}
Apilar: Inserta un elemento a continuación del elemento que se encuentra en el tope de la

pila. Tiene como entrada el dato que se va a apilar
Apilar(entero dato)
{
Es (EsLlena()) Si: Muestre “Pila llena”
Terminar
Tope = Tope + 1
Pila[ Tope] = dato
}
Desapilar: Elimina el elemento que se encuentra en la posición del tope de la pila y

retorna el dato que se encuentra en dicha posición. Retorna -1 si la pila se encuentra vacía
entero Desapilar( )
{ entero d
Es (EsVacia()) Si: Muestre “Pila Vacia”
retorne (-1)
d = Pila[ Tope ]
Tope = Tope - 1
retorne ( d)
}
Tope: Retorna el dato que se encuentra en el tope de la pila. Si la pila está vacía, retorna -
1
entero Tope( ){
Es (EsVacia()) Si: Muestre “Pila Vacia”
Retorne (-1)
retorne Pila[Tope]
}
Manejo de 2 pilas en arreglos
Se utiliza cuando en una aplicación se necesita manejar simultáneamente dos pilas.
Se define un sólo arreglo de tamaño N en donde se van a almacenar los valores de las dos
pilas.
A continuación se presentan dos formas de manejar las dos pilas en un sólo arreglo:
1) Si el arreglo se denomina Pilas, los valores de la pila 1 se almacenarán en el arreglo

desde la posición 1 hasta la posición M=N/2 y los valores de la pila 2 desde la
posición M+1 hasta la posición N.
Se definen las variables que van a contener los topes de las pilas:
Tope1 = tope pila 1
Tope2 = tope pila 2
En esta forma de almacenar los valores, inicialmente:

Tope1 = 0 y Tope2 = M
Pila 1 vacía: Tope1 = 0 Pila 2 vacía: Tope2 = M

Pila 1 llena: Tope1 = M Pila 2 llena Tope2 = N
M N-1
1 2 3 4 5 6 7 8 9 10
4 27 30 42 35
Tope 1 Tope 2
Pila 1 Pila2
En esta forma de almacenar los valores, si la pila 1 está llena, se revisa si la pila 2
tiene espacio disponible y en este caso se mueven los elementos de la pila 2 una
posición a la derecha. Si la pila 2 es la que se encuentra llena, y la pila 1 tiene espacio
disponible, se desplazan los elementos de la pila 2 una posición hacia la izquierda. En
ambos casos se actualizan los valores de las variables Tope2 y M:
Para evitar estos movimientos de los valores en el arreglo, cuando se comiencen a

llenar las pilas, se propone la segunda forma de almacenar dichos valores.
2) Inicialmente:
Tope1 = 0 y Tope2 = N + 1
Pila 1 vacía: Tope1 = 0 Pila 2 vacía: Tope2 = N+1

Las pilas están llenas cuando Tope1 + 1 = Tope2
1 2 3 4 5 6 7 8 9 10
4 27 30 75 15
Tope 1 Tope 2
Representación de una Pila en Lista Simple Enlazada
5 9 3 12 null
Tope
La definición de la estructura Pila en una lista simple enlazada es la siguiente
Clase Pila{
nodo Tope
Cola( ) // constructor de la cola
Booleano EsVacia( )
Apilar( elemento) //inserta elemento en el tope de la pila
elemento Desapilar( ) //elimina elemento del tope de la pila y retorna su valor
elemento Tope( ) //retorna valor del tope de la pila
}
La implementación de los métodos es la siguiente:

Constructor:
En el constructor se inicializa la variable Tope en null.
Cola( ){
Tope = null
}
Booleano EsVacia( ){ //retorna verdadero si la pila está vacia

retorne (Tope = = null)
}
Apilar(entero d) //inserta un elemento en el tope de la pila

{
Es( EsVacia( )) Si: Tope = nuevo
No. {nuevo.Asigna_Sig(Tope)
Tope = nuevo
}
}
Entero Desapilar( ) //retira el elemento que se encuentra en la posición del Tope de
{ la pila y retorna valor
entero d
Es( EsVacia( ))Si: Muestre “Pila Vacia”
retorne (-1)
d = Tope. Retorne_Dato( )
Tope = Tope.Retorne_Sig( )
retorne ( d )
}
Entero Tope( ) // retorna valor del elemento tope de la pila

{
Es( EsVacia( ))Si: Muestre “Pila Vacia”
retorne (-1)
retorne( Tope.Retorne_Dato( ) )
}
Manejo de N pilas en arreglos

Se utiliza cuando en una aplicación se necesita manejar simultáneamente N pilas.
Se define un sólo arreglo, por ejemplo el arreglo PILAS, de tamaño M en donde se van a
almacenar los valores de las N pilas. Inicialmente todas las pilas contienen el mismo
número de elementos T = M/N.
PILAS
M
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
4 8 12 20 30 40 60 70 22 23
Pila 1 Pila 2 Pila3 Pila 4
Si M = 20 y N= 4 (número de pilas). Inicialmente cada una de las 4 pilas contiene

T= 20/4 = 5 elementos.
Se definen también dos arreglos denominados BASES Y TOPES:

El arreglo de BASES de tamaño N+1, contiene en la posición I la posición anterior al
primer elemento de la pila I en el arreglo de PILAS.
El arreglo TOPES de tamaño N, contiene en la posición I, la posición en el arreglo de

PILAS, en donde se encuentra el tope de la pila I.
Inicialmente los arreglos BASES y TOPES, en este ejemplo, contienen los valores:
BASES
1 2 3 4 5
0 5 10 15 20
TOPES
1 2 3 4
0 5 10 15
Después de haber apilado los valores que se encuentran en el arreglo de PILAS los arreglos
BASES y TOPES contienen:
BASES
1 2 3 4 5
0 5 10 15 20
TOPES
1 2 3 4
3 10 10 17
Condición de Pila I Vacía:

La Pila I se encuentra vacía si: BASES[ I ] = TOPES[ I ].
Como se puede observar en el ejemplo, la pila 3 se encuentra vacía.
Condición de Pila I Llena:

La Pila I se encuentra llena si: TOPES[ I ] = BASES[ I + 1].
En el ejemplo, la pila 2 se encuentra llena.
Apilar: Inserta un elemento a continuación del elemento que se encuentra en el tope de la

pila I. Tiene como entrada la pila I en donde se va a apilar y el dato que se va a apilar.
Apilar(entero I, entero dato)

{
Es (EsLlena(I)) Si: Pila llena (I)
Tope[ I ] = Tope[ I ] + 1
Pilas[ Tope[I] ] = dato
}
Si la Pila I se encuentra llena, invoca el método de Pila llena(I) . El procedimiento que se

sigue en este método es el siguiente:
Busca primero cuál de las pilas desde la I + 1 hasta la N, tiene espacio disponible. Si la pila
J es la pila con espacio disponible, mueve un lugar hacia derecha todos los elementos del
arreglo Pilas desde el tope de la pila J hasta la base de la pila [I+1] +1. Luego actualiza las
bases y los topes desde la pila I+1 hasta la pila J. Si todas estas pilas están llenas, busca
desde la pila I - 1 hasta la 1 la pila con espacio disponible. Si la pila J es la pila con
espacio, desplaza los elementos en el arreglo de pilas, desde la base de la pila J +1 hasta el
tope de la pila I, un lugar hacia la izquierda. Luego actualiza las bases y los topes de las
pilas J +1 hasta la pila I. Después de asignar el espacio a la pila I que se encontraba llena,
retorna para apilar el nuevo elemento. Si todas las pilas están llenas, termina el método de
apilar.
Desapilar: Elimina el elemento que se encuentra en la posición del tope de la pila I y
retorna el dato que se encuentra en dicha posición. Retorna -1 si la pila se encuentra vacía
entero Desapilar( entero I )

{ entero d
Es (EsVacia(I)) Si: Muestre “Pila” + I + “ Vacia”
retorne (-1)
d = Pilas[ Tope[ I] ]
Topes[ I ] = Topes[ I ] - 1
retorne ( d)
}
Tope: Retorna el dato que se encuentra en el tope de la pila I. Si la pila está vacía, retorna -
1
entero Tope( I ){
Es (EsVacia(I)) Si: Muestre “Pila” + I +” Vacia”
Retorne (-1)
retorne Pilas[Tope[ I ]]
}
Manejo de N pilas en Listas Enlazadas
Se define un arreglo de tamaño N (número de Pilas) de tipo nodo que contiene el tope de
cada una de las pilas. Si por ejemplo se tiene N =4 pilas, la representación es la siguiente:
Topes
1 2
2 1 5 7
4 8
Inicialmente, Topes[ I] = null, siendo esta la condición de pila I vacía
Apilar: Tiene como entrada la pila I en donde se va a apilar y el dato que se va a apilar.
Apilar(entero I, entero d) //inserta un elemento en el tope de la pila
{
Es( EsVacia(I )) Si: Topes[ I] = nuevo
No. {nuevo.Asigna_Sig(Topes[I])
Topes[ I ] = nuevo
}
}
Entero Desapilar( entero I) //retira el elemento que se encuentra en la posición del Tope de
{ la pila I y retorna valor
entero d
Es( EsVacia( I))Si: Muestre “Pila”+ I + “Vacia”
retorne (-1)
d = Topes[ I ]. Retorne_Dato( )
Topes [ I] = Topes[ I ].Retorne_Sig( )
retorne ( d )
}
Entero Tope(entero I ) // retorna valor del elemento tope de la pila I

{
Es( EsVacia( I))Si: Muestre “Pila” + I + “ Vacia”
retorne (-1)
retorne( Topes[ I ].Retorne_Dato( ) )

}
Taller Pilas y Colas
1. Defina la forma de representar una cola como una lista enlazada en donde sólo se
maneje una variable para el primero y el último elemento de la cola. Elaborar los
métodos para encolar y desencolar de orden O(1).
2. Defina la forma más eficiente de representar dos pilas en un sólo arreglo. Elaborar
los métodos para apilar y desapilar sobre cada una de las pilas.
3. Se tiene una cola circular representada en un arreglo. Elaborar un método que
muestre los elementos de la cola desde el último hasta el primero.
4. Elaborar un método que reciba una palabra y la muestre al revés. Primero, utilizando
una pila y luego una cola.
5. Elaborar un método recursivo que retorne la suma de los valores de una pila
representada en un arreglo.
6. Elaborar el método del numeral 5 en una pila representada en una lista enlazada
7. Elaborar un método recursivo que muestre en orden inverso los valores de una pila
representada en un arreglo.
8. Elaborar el método del numeral 7 en una pila representada en una lista enlazada.
9. Se tienen dos pilas que contienen 12 números. La primera pila ordenada
ascendentemente con los números del 1 al 12 desde el tope hacia el fondo. La
segunda pila ordenada descendentemente con los números del 24 al 13 desde el tope
hacia el fondo. Elaborar un método que fusione los números de las dos pilas en una
tercera pila ordenada descendentemente desde el tope hacia el fondo.
10. Defina la forma de representar una pila y una cola circular en un sólo arreglo.
Para dicha representación, elaborar los métodos para las operaciones que sea realizan
sobre la pila y sobre la cola de acuerdo a la representa utilizada.
11. Dada una cola representada en un arreglo, elaborar un método que copie los
elementos de la cola en una pila, también representada en un arreglo, de tal forma
que el primer elemento de la cola quede de tope de la pila.
12. Realizar el numeral 11 utilizando representación de listas enlazadas para la pila
y para la cola.
13. Dado un arreglo X de tamaño N que contiene en cada posición una palabra, crear
una lista simple enlazada, en donde cada nodo contiene una letra del alfabeto, de la
‘A’ a la ‘Z’ y la referencia al primer elemento de una cola que va a contener las
palabras que comiencen por dicha letra. Es decir, que por cada letra del alfabeto se va
a construir una cola. Tomar cada una de las palabras del arreglo X y encolarlas en la
respectiva cola. Luego, muestre primero las palabras que comiencen por la letra A,
después la que comiencen por la letra ‘B’, y así sucesivamente hasta la letra ‘Z’.
Análisis de Algoritmos Recursivos
Un método recursivo consta de dos partes: una caso base, en el cual se especifica el
valor de la función para uno o varios de los valores que se encuentran en el dominio de
dicha función y un caso general, en donde la función se especifica en términos de la
misma función.
De acuerdo a la forma en que se realice la llamada, la recursión puede ser:

- Directa: Cuando el método se invoca a sí mismo.
- Indirecta: Cuando un método invoca un segundo método y éste invoca al primero.
De acuerdo al número de llamadas, la recursión puede ser:

- Simple (Lineal): Cuando en una condición sólo existe una llamada recursiva.
- Múltiple: Cuando en una condición se presentan varias llamadas recursivas.
Para determinar el f(n), o la complejidad de una solución algorítmica recursiva, se han empleado
tres técnicas de resolución de ecuaciones de recurrencia:
- Expansión de Recurrencias
- Método de la Ecuación característica
- Fórmulas Maestras
Expansión de Recurrencias
Un sistema recurrente consiste de un conjunto de valores iniciales, o valores de la
función en unos puntos específicos y una ecuación recurrente en donde el valor la
función en el punto n está dado en términos de otro punto m, siendo n > m.
El método de expansión de recurrencias consiste en aplicar la función general a cada uno de los
valores de n hasta llegar a la condición base (inicial) la cual es reemplazada por su valor.
Dependiendo del tipo de ecuación obtenida en t(n), se encuentra el Orden de Magnitud del
método recursivo.
Ejemplo 1
Calcular el factorial de un número dado N.

En forma recursiva el factorial de un número dado N se define de la siguiente manera:
0! = 1
1! = 1 x 0!
2! = 2 x 1!
3! = 3 x 2!
.
.
.
N! = N x (N – 1)!
El modelo se puede especificar de la siguiente manera:
1, Si n= 0
Fact( n ) =
n * Fact(n – 1), Si n > 0
Parámetros de entrada:
N: Número al que se le desea calcular el factorial
Salida:
retorna el factorial del número N.
entero Fact( entero N )

{
Es ( N = = 0) Si: Retorne ( 1 )
Retorne ( N * Fact ( N –1) )
}
Para el ejemplo, el sistema recurrente se puede especificar de la siguiente manera:
1, Si n = 0
t( n) =
1 + t(n – 1), Si n >0
Si n = 0, el tiempo de ejecución es t(n) = 1

Si n > 0, el tiempo de ejecución t(n) será igual al tiempo de ejecución de la llamada con n-1, es
decir, t(n – 1) más 1, que es el costo de la multiplicación por n.
En este ejemplo, al aplicar la función general:

t(n) = 1 + t(n – 1)
= 1 + 1+ t(n – 2) = 2+ t(n – 2)
= 1 + 1+ 1+ t(n – 3) = 3+ t(n – 3)
.
.
.
= 1+1+1+…+ t(0) = n+ t(0)
t(n) = n + 1
Por lo tanto, el Orden de Magnitud de este método es O(N).
Si n = 4
t(4) = 1 + t(3)
= 1 + 1+ t(2)
= 1 + 1 + 1+ t(1)
= 1 + 1 + 1 + 1 +t(0)
Dado que t(0) es igual 1, t(4) es igual a 5.
Ejemplo 2
Dada la siguiente función recursiva
entero F2( entero N )

{
Es ( N= = 1) Si: Retorne ( 1 )
Retorne ( F2 ( N - 1) + F2(N - 1 ))
}
El sistema recurrente se puede especificar de la siguiente manera:
1, Si n = 1
t( n) =
1 + 2 t(n - 1), Si n > 1
Aplicación de la expansión de recurrencias:

t(n) = 1 + 2t(n - 1)
= 1 + 2( 1+ 2t(n - 2) = 3 + 4 t(n- 2)
= 3 + 4(1 + 2t(n – 3) = 7 + 8 t(n – 3)
= 7 + 8(1 + 2t(n – 4) = 15 + 16t(n – 4)
.
.
.
o sea que
t(n) = (2k - 1) + 2kt(n - k)
para k = n - 1
t(n) = (2n-1 - 1) + 2n-1t(1)
y el Orden de Magnitud de este método es O(2n).
Si n = 4
t(4) = 1 + 2t(3)
= 3 + 4 t( 2)
= 7 + 8 t( 1)
t(4) = (23 - 1) + 23= 7 + 8 = 15
Ejemplo 3
entero F3( entero N )

{
Es ( N = = 0) Si: Retorne ( 1 )
Retorne ( N * F3 ( N/2) )
}
1, Si n = 0
t( n) =
1 + t(n/2), Si n >0
Si n = 0, el tiempo de ejecución es t(n) = 1

Si n > 0, el tiempo de ejecución t(N) será igual al tiempo de ejecución de la llamada con n/2, es
decir, t(n/2) más 1 de la multiplicación por n.

t(n) = 1 + t(n/2)
= 1 + 1+ t(n/4) = 2 + t(n/4)
= 1 + 1+1 + t(n/8) = 3 + t(n/8)
= 1+1+1+1 + t(n/16) = 4+ t(n/16)
.
.
.
Cuando n = k:
= 1 +1+ …..+ t(0)
Dado que t(0) es igual 1, t(n) es igual a log2n + 2.
y el Orden de Magnitud de este método es O(log2n)
Si n = 16
t(16) = 1 + t(8)
= 1 + 1+ t(4)
= 1 + 1+1 + t(2)
= 1 + 1 + 1 + 1 + t(1)
= 1 + 1 + 1 + 1 + 1 + t(0) = 6
Si n= 16, log216 + 2 = 4 + 2
Ejemplo 4
entero F4( entero N, entero z )

{
Es ( N = = 0) Si: Retorne ( 1 )
No:{
Para i = 1 hasta N
{z=z+1}
Retorne ( F4 ( N - 1, z) )
}
1, Si n = 0
t( n) =
n + t(n -1), Si n >0

t(n) = n + t(n-1)
= n + (n-1) + t(n -2)
= n + (n-1) + (n – 2) +t(n -3)
.
.
= n + (n-1) + (n – 2) +t(n - k)
Cuando n = k
t(n) = n + (n-1) + (n – 2) + (n - 3) + …+ 2 + 1
= n*(n+1)/2
y el orden de Magnitud es O(n2)
Ecuación de Recurrencias
En este método se parte del sistema recurrente que resulta del método recursivo y se
resuelve la ecuación de recurrencia.
Ejemplo 1
Para el ejemplo del factorial de un número, en donde el sistema recurrente es:
1, Si n = 0
t( n) =
1 + t(n – 1), Si n >0
La ecuación de recurrencia que se obtiene es de la forma:

tn = tn-1 + 1, con la condición inicial t0 = 1
siendo una ecuación de recurrencia lineal no homogénea con coeficientes constantes,

cuya solución es:

Encontrar la solución para la ERLH:
La ecuación característica de la relación de recurrencia es: r - 1 = 0, o sea que r = 1

1

Encontrar la solución :
Como f(n) =A(1)n y se presenta multiplicidad de raíz, cada término de la ecuación es de
la forma, An*1n
Reemplazando en la ecuación original:
An – A(n – 1) = 1
A=1

indica que:
La solución general es:

n + c
Utilizando la condición inicial:

t0 = 1= , o sea que c = 1
y la solución general es:

1
Con base en la forma de la solución general, se obtiene el orden de magnitud. En este

caso, la ecuación es lineal y el orden de magnitud será igual a O(N)
Ejemplo 2
En la función F2 el sistema recurrente es
1, Si n = 1
t( n) =
1 + 2 t(n-1), Si n >1

tn =2tn-1 + 1, con la condición inicial t1 = 1
siendo una ecuación de recurrencia lineal no homogénea con coeficientes constantes,

cuya solución es:

La ecuación característica de la relación de recurrencia es: r - 2 = 0, o sea que r = 2

2

Como f(n) =A(1)n

A –2A = 1
A = -1

indica que: 1

2 1
y la solución general es:

2 1
Con base en la forma de la solución general, se obtiene que el orden de magnitud será
igual a O(2 ).
Ejemplo 3
Para la función F3 en donde el sistema de recurrencias es:
1, Si n = 0
t( n) =
1 + t(n/2), Si n >0

t(n) = 1 + t(n/2), con la condición inicial t0 = 1
Para plantear la ecuación de recurrencia se realiza un cambio de variable y se reemplaza

n por 2i. O sea,
t(2i) = t(2i-1) + 1, n >1
Luego se resuelve la ecuación de recurrencia para t(i)

ti = ti-1 + 1
resultando una ecuación de recurrencia lineal no homogénea.
ti(h) = ti - ti-1 = 0
Ecuación característica:
r - 1 = 0, r = 1
ti(h) = c*(1)i
La forma del f(n) para ti(P) es (1)i, pero como se presenta multiplicidad, f(n) es igual a:
Ai(1)i
Reemplazando en la ecuación:
Ai – A(i – 1)= 1
A=1
o sea que
ti = ( c + i) (1)i
para encontrar el valor de c:

t0 = 1, c =1
ti = ( 1 + i)
dado que n =2i , i = log2n

tn= log2n +1
Ejemplo 4
Para la función F4 el sistema recurrente es
1, Si n = 0
t( n) =
n + t(n -1), Si n >0

tn =tn-1 + n, con la condición inicial t0 = 1
La ecuación característica de la relación de recurrencia homogénea: r - 1 = 0, o sea que

r=1

1

Como f(n) = (An + B)(1)n y se presenta multiplicidad de raíz, f(n) = n(An + B)(1)n =
An2 + Bn

{An2 + Bn} - {A(n-1)2 + B(n-1) }= n
An2 + Bn - { A(n2 – 2n + 1) +Bn - B }= n
An2 + Bn - An2 + 2An - A - Bn + B = n
2An - A + B = n
En n: 2A = 1, A = ½
-A + B = 0, B = 1/2
1 1

2 2
Si t0 =1, c =1
Con base en la forma de la solución general, se obtiene que el orden de magnitud será
igual a O(n2)
Referencias
- Estructuras de Datos y Algoritmos. Alfred V.Aho, John E. Hopcroft, Jeffrey D.
Ullman. Addison-Wesley, Iberoamericana 1988.
- Fundamentos de Algoritmia. Brassard, Gilles, Bratley, Paul. Prentice-Hall. 1997.
- Estructura de Datos. Libro de Problemas. Luis Joyanes Aguilar, Ignacio Zahonero
Martínez, Matilde Fernández A y Lucas Sánchez G. Ed. Mc. Graw Hill. 1999
TALLER DE RECURSIÓN
1. Dado un arreglo de 7 elementos, el cual contiene los últimos 7 dígitos de su

identificación, de a un dígito por elemento. Haga seguimiento detallado a cada
uno de los siguientes métodos mostrando qué muestran al ser llamados con
sp#(v, 7, 1)
sp1(v, n, i)
{
Es (i <= n) Si:{ sp1(v, n, 2*i)
Muestre(v[i])
sp1(v, n, 2*i+1)
}
}
sp2(v, n, i)
{
Es (i <= n) Si:{ Muestre(v[i])
sp2(v, n, 2*i)
sp2(v, n, 2*i+1)
)
}
sp3(v, n, i)
{
Es (i <= n) Si: {sp3(v, n, 2*i)
sp3(v, n, 2*i+1)
Muestre(v[i])
}
)
sp4(v, n, i)
{
Es (i <= n) Si:{Muestre(v[i])
sp4(v, n, i+1)
Muestre(v[i])
}
}
2. Dados dos números enteros X y N, elaborar un método recursivo que calcule y

muestre a XN
3. Elaborar un método recursivo que retorne la suma de los elementos de un
arreglo unidimensional que contiene números enteros
4. Elaborar un método recursivo que reciba como entrada una palabra y la muestre
en orden inverso. Es decir, que primero muestre la ultima letra de la palabra,
luego la penúltima, y asi sucesivamente hasta la primera letra de la palabra de
entrada.
5. Elaborar un método recursivo que recorra y muestre los datos de una lista
simple enlazada de izquierda a derecha y de derecha a izquierda.
6. Elaborar un método recursivo para la siguiente función, denominada la función

de Ackermann
B + 1, A=0
W(A,B) = W(A - 1, 1), B=0
W(A - 1, W(A, B -1)), otro caso
Haga un seguimiento para W(1,3)
7. Considere que C(n, k) representa el número de diferentes comités de k personas

que pueden ser formados, dadas n personas.
a) Defina las condiciones de parada de la recursividad

b) Elabore la función recursiva para calcular C(n, k) con:
C(n, k)= C(n -1, k) + C(n - 1, k - 1) ∀n,k > 1
c) Haga el seguimiento mostrando cada uno de los pasos para C(6,2)
8. Encontrar el orden de magnitud utilizando ecuaciones de recurrencias de los

métodos:
a) Serie de Fibonacci
b) Búsqueda Binaria
c) Torres de Hanoi
Recursión
La recursión es una técnica de programación que se utiliza en la implementación de
modelos que se definen en términos de sí mismo. El objetivo de la recursión es dividir
un problema en subproblemas de iguales características pero de menor tamaño.
De acuerdo a la forma en que se realice la llamada, la recursión puede ser:
- Directa: Cuando el método se invoca a sí mismo.

- Indirecta: Cuando un método invoca un segundo método y éste invoca al primero.
De acuerdo al número de llamadas, la recursión puede ser:
- Simple (Lineal): Cuando en una condición sólo existe una llamada recursiva.
- Múltiple: Cuando en una condición se presentan varias llamadas recursivas.
Un método recursivo consta de 2 o más condiciones, en donde al menos una de ellas no

contiene una llamada recursiva. A esta condición se le denomina condición Base o de
terminación de la llamada recursiva.
La principal ventaja de la recursión es que permite una implementación de los modelos

recursivos, en una forma lógica y sencilla. La desventaja consiste en el consumo tanto
de espacio como de tiempo para el manejo de la recursión, ya que antes de cada llamada
recursiva utiliza una estructura de pila para almacenar direcciones de retorno, valores de
los parámetros y valores de las variables locales.
A continuación se explicará con ejemplos cómo funciona la recursión.
Ejemplo 1
Calcular el factorial de un número dado N.

El cálculo del factorial de un número N, se puede realizar de dos formas:
Iterativa Recursiva
0! = 1 (Por definición) 0! = 1
1! = 1*1 = 1 1! = 1 * 0!
2! = 1*2 = 2 2! = 2 * 1!
3! = 1* 2*3 = 6 3! = 3 * 2!
4! = 1*2*3*4= 24 4! = 4 * 3!
En general, en la forma recursiva, N! = N * (N – 1)!
La definición del modelo para el cálculo del factorial de un número en forma

recursiva es el siguiente:
1, N = 0
Fact( N ) =
N*Fact(N – 1), N > 0
En este caso, el modelo tiene 2 condiciones, en donde la condición base se presenta
cuando N = 0.
La implementación del modelo recursivo se realiza de la siguiente manera:
Entrada:
N: número entero al que se le va a calcular el factorial
Salida:
El método retorna un número entero que contiene el factorial de N.
entero Fact( entero N)

{
Es (N = = 0 ) Si: retorne (1)
retorne( N * Fact (N – 1))
L1
}
A continuación se presenta el seguimiento a la ejecución del método, si por ejemplo

N = 5.
Programa Factorial
{ entero factorial, N
entre N
L0 factorial = Fact(N) //invoca el método Fact
Muestre “El factorial de N es”: + factorial
}
Sea Lo la dirección de retorno, luego de ejecutarse el método Fact(N) y L1 la

dirección de retorno luego de la llamada recursiva dentro del método.
L1 0 1
L1 1 1*1=1
L1 2 2*1=2
L1 3 3*2=6
L1 4 4*6=24
L0 5 5*24=120
Dr N Fact
O sea que si N es diferente de cero llama recursivamente con N – 1, almacenando en

la pila la dirección de retorno al punto desde donde se invocó y el valor de N, hasta
llegar a la condición base, que en este caso es N = 0. Cuando N = 0 retorna a la
dirección almacenada en el tope de la pila (L1), que Fact(0) es 1 y desapila, luego
calcula Fact(1) que es igual a 1*Fact(0) = 1*1=1 y retorna a la dirección
almacenada en el tope de la pila (L1), que Fact(1) es 1 y desapila. Así se continúa la
ejecución hasta que la pila se encuentre vacía.
Otra forma de ver la ejecución es la siguiente:

factorial = Fact(5)
5 * Fact(4) = 5 * 24 = 120 retorna a principal el valor de 120
4*Fact(3) = 4 * 6 = 24
3*Fact(2) = 3*2= 6
2* Fact(1) = 2* 1 = 2
1*Fact(0) = 1*1 = 1
retorna 1
Ejemplo 2
Calcular el N-ésimo término de la serie de Fibonacci.

La serie de Fibonacci es 0 1 1 2 3 5 8 13….., en donde un término se genera a partir de
la suma de los 2 anteriores.
El modelo de la serie es el siguiente:
0, N = 1
Fib( N ) = 1, N = 2
Fib(N – 1) + Fib(N – 2), N > 2
Entrada:
N: número entero que contiene cuál es el N-ésismo término a calcular
Salida:
El método retorna el valor del N-ésismo término de la serie
entero Fib( entero N)

{
retorne( Fib (N – 1) + Fib(N-2))
L1 L2
}
A continuación se presenta el seguimiento a la ejecución del método, si por ejemplo

N = 5.
Programa Fibonacci
{ entero fibo, N
entre N
L0 fibo = Fib(N)
Muestre “El termino “ + N + “es”: + fibo
}
Sea Lo la dirección de retorno, luego de ejecutarse el método Fib(N), L1 la dirección

de retorno cuando retorne de la llamada de Fib(N -1) y L2 la dirección de retorno
cuando retorne de la llamada de Fib(N - 2)
L2 1 0
L1 2 1
L2 3 1 +0 = 1
L2 2 1
L2 1 0
L1 2 1
L1 3 1+0 = 1
L1 4 1+ 1= 2
L0 5 2+1= 3
Dr N Fib
fib(5) = 2 + 1 = 3
+
fib(4) =2 fib(3) = 1
+ +
fib(3) =1 fib(2) fib(2) fib(1)

+
fib(2) fib(1) 1 1 0
1 0
Ejemplo 3
Encontrar el Máximo Común Divisor entre dos enteros N y M
El Máximo Común Divisor entre dos enteros N y M se define de la siguiente manera:
MCD(M, N), M > N
MCD(N, M ) = N, M = 0
MCD(M, N%M), otro caso

en donde N%M, es el residuo de dividir N/M
Entrada:
N, M: números enteros
Salida:
El método retorna el Máximo Común Divisor entre N y M
entero MCD( entero N, entero M)

{ L1
Es (M > N ) Si: retorne (MCD(M, N))
Es (M = = 0 ) Si: retorne (N)
retorne( MCD(M, N%M))
L2
}
El seguimiento para N = 8 y M = 12 es el siguiente:
L2 4 0 4
L2 8 4 4
L1 12 8 4
L0 8 12 4
Dr N M MCD
o sea que el MCD(8, 12) = 4
Si N = 7 y M = 5:
L2 1 0 1
L2 2 1 1
L2 5 2 1
L0 7 5 1
Dr N M MCD
o sea que el MCD(7, 5) = 1
Ejemplo 4
Sea Q(M, N) el número de formas diferentes en que un entero M puede expresarse
como una suma de números menores o iguales que N.
Por ejemplo el si M =5 y N =3, el número de formas en que se puede expresar el

número 5 como la suma de números menores o iguales a 3 es igual a 5. Estas son:
1 + 1+ 1 +1 +1
1+1+1+2
2+2+1
3 + 1+ 1
3 +2
El modelo para encontrar Q(M, N) es el siguiente:
1, M =1 o N = 1
Q(M, M), M<N

Q(M, N ) =
1+ Q(M, M -1), M = N
Q(M, N-1) + Q(M – N,N), M > N
La implementación del modelo recursivo es:
Entrada:
M, N: números enteros
Salida:
El método retorna el número de formas
entero Q( entero M, entero N)

{
Es (M = =1) o (N= = 1) retorne (1)
L1
Es (M < N) retorne (Q(M, M))
L2
Es (M = N) retorne (1+ Q(M, M -1))
retorne (Q(M, N-1) + Q(M – N, N))
L3 L4
}
El seguimiento para M = 5 y N = 3 es el siguiente:
L2 2 1 1
L1 2 2 1+1=2
L4 2 3 2
L4 1 2 1
L3 3 1 1
L4 3 2 1 +1=2
L3 5 1 1
L3 5 2 1 + 2=3
L0 5 3 3 + 2 =5
Dr M N Q
siendo Q(5, 3) = 5.
Ejemplo 5
Calcular la raíz cuadrada de un número entero dado N, mediante el siguiente método
A, | | < E
Raiz( N, A, E ) = Raiz(N, (A2 + N)/(2*A), E), otro caso

en donde,
N: numero positivo al que se le desea encontrar la raíz cuadrada
A: Semilla o valor inicial (por encima o por debajo del valor del resultado)
E: Precisión del resultado. Mientras más pequeño sea E, más preciso es el resultado
Entrada:
N, A, E: números reales
Salida:
Raiz Cuadrada de N.
real Raiz( real N, real A, real E)

{
Es ( | | < E) retorne (A )
retorne (Raiz(N, (A2+N)/(2*A), E)
L1
}
Si por ejemplo N= 49, A=4, E=0.00001
L1 49 7.000000013 0.00001 7.000000013

L1 49 7.00042851 0.00001 7.000000013
L1 49 7.0778846 0.00001 7.000000013
L1 49 8.125 0.00001 7.000000013
L0 49 4 0.00001 7.000000013
Dr N A E Raiz
Cuando se encuentra que A2= (7.000000013)2 - 49 es menor que 0.00001, retorna que
la raíz cuadrada de 49 es 7.000000013. Como L1 es retornar el valor de A a la llamada
anterior, éste valor se retorna hasta cuando se llegue a que la pila se encuentre vacía.
Ejemplo 6
Un método para evaluar un polinomio de la forma
Pn(x) = a0xn + a1xn-1+a2xn-2+ …+an-1x + an
es el método de Horner. En donde n≥0 y los términos se encuentran ordenados en forma

descendente por el exponente.
En forma recursiva se define de la siguiente manera:

Po(x) = a0
Pn(x) = x* Pn-1(x) + an
A[0], N = 0
Eval( A, N, X ) = x*Eval(A, N – 1, x) + A[N], otro caso

A es un arreglo de tamaño N+1 que contiene los coeficientes [0,..,N]
N: es el grado del polinomio
X: punto a evaluar el polinomio
Entrada:
A: arreglo de coeficientes (Números reales)
N: grado de polinomio. Entero
X: punto a evaluar. Real
Salida:
Resultado de evaluar el polinomio de acuerdo al valor de X.
real Eval( arreglo A, entero N, real X)

{
Es (N = = 0) retorne (A[0] )
retorne (x*Eval(A, N-1,X) + A[N])
L1
}
A continuación se presenta el seguimiento para el polinomio
2X5 + 5X4 - 3X3 +4X -6
En este caso el arreglo A es igual a:
0 1 2 3 4 5
2 5 -3 0 4 -6
N=5 y X=1.0
L1 (*) 0 1 2
L1 (*) 1 1 1*2 + 5 = 7
L1 (*) 2 1 1*7 +(-3) = 4
L1 (*) 3 1 1*4 + 0 = 4
L1 (*) 4 1 1*4 + 4 = 8
L0 (*) 5 1 1*8 + (-6) = 2
Dr A N X Eval
(*): Se almacena el arreglo A
Para X = 1.0 el resultado de evaluar el polinomio es igual a 2.
En los ejemplos anteriores todos los métodos retornan un valor y en éste caso cuando se
realiza el seguimiento, se asigna una etiqueta en el punto en donde se invoca la llamada
recursiva, ya que en una misma instrucción se pueden tener varias veces llamadas
recursivas, o se puede presentar que luego de regresar de la llamada se realice alguna
operación.
Cuando se invoca un método que no retorna un valor, al realizar el seguimiento, se

etiqueta la instrucción siguiente a la invocación del método. A continuación se
presentan algunos ejemplos.
Ejemplo 7
Elaborar un método recursivo que muestre los valores contenidos en un arreglo
unidimensional.
Entrada:
A: arreglo unidimensional
N: tamaño del arreglo A
Mostrar(arreglo A, entero N)
{
Es(N> 0) Si:{Muestre A[N]
Mostrar(A, N-1)
}
}L1
Si por ejemplo, el arreglo A contiene los valores

1 2 3 4 5 6
10 35 8 12 43 64
L1 (*) 0
L1 (*) 1 10
L1 (*) 2 35
L1 (*) 3 8
L1 (*) 4 12
L1 (*) 5 43
L0 (*) 6 64
Dr A N Muestra
(*): Valores del arreglo A
Cuando se invoca el método por primera vez, N = 6, muestra A[6]=64 y llama el

método Mostrar con N=5, muestra A[5]=43 y llama Mostrar con N=4,y así se continua
la ejecución hasta llegar a N = 0. En este caso retorna a L1 que es regresar a la
instrucción siguiente de Mostrar con el N anterior a la llamada y desapilar. Se realiza el
mismo procedimiento hasta que la pila se encuentre vacia.
¿Cómo se implementaría el método si se debe mostrar primero A[1]?
Ejemplo 8
Elaborar un método recursivo que muestre las permutaciones generadas con N valores
lógicos.
Análisis del problema

El procedimiento para generar las permutaciones de N valores lógicos se definen como:
1. Dejar el primer valor fijo, para generar permutaciones sobre los N-1 restantes.
2. Negar el primer valor
3. Nuevamente, dejar el primer valor fijo, para generar permutaciones sobre los N-
1 restantes
Si por ejemplo N=3 y los valores se inicializan en VVV, las permutaciones obtenidas
son:
VVV VVF VFV VFF
Se niega el primer valor y nuevamente se realizan permutaciones sobre los dos restantes
FVV FVF FFV FFF
Si N= 4 y se ini
cializa en VVVV
VVVV VVVF VVFV VVFF VFVV VFVF VFFV VFFF
FVVV FVVF FVFV FVFF FFVV FFVF FFFV FFFF
Entrada:
A: arreglo unidimensional de valores lógicos
N: tamaño del arreglo
Pos: Posición a partir de la cual se realiza la permutación. Inicialmente P = 1.
El método muestra cada una de las permutaciones
LOGICO(arreglo A entero N, entero Pos)

{
Es (Pos ≤ N+1) Si:{LOGICO(A, N, Pos +1)
L1 A[Pos] = Not A[Pos]
LOGICO(A, N, Pos +1)
L2 A[Pos] = Not A[Pos]
}
No: Para i= 1 hasta N
Muestre A[i]
}
El seguimiento para N=3 es el siguiente:
L2 FFF 3 4 FFF (8)

L1 FFV 3 4 FFV (7)
FFV
FFF
L2 FFV 3 3
L2 FVF 3 4 FVF( 6)
L1 FVV 3 4 FVV (5)
FVV
FVF
L1 FVV 3 3
FVV
FFV
L2 FVV 3 2
L2 VFF 3 4 VFF (4)
L1 VFV 3 4 VFV (3)
VFV
VFF
L2 VFV 3 3
L2 VVF 3 4 VVF (2)
L1 VVV 3 4 VVV (1)
VVV
VVF
L1 VVV 3 3
VVV
VFV
L1 VVV 3 2
VVV
FVV
L0 VVV 3 1
Dr A N Pos Muestra
Ejemplo 9
Elaborar un método recursivo que muestre las permutaciones generadas con N símbolos
dados.
Análisis del problema

El procedimiento para generar las permutaciones de N símbolos es el siguiente:
Para cada uno de los N símbolos, dejar el primer valor fijo, para generar permutaciones
sobre los N-1 restantes.
Si por ejemplo N=3 y los símbolos son ABC, las permutaciones obtenidas son:
ABC ACB BAC BCA CBA CAB
Entrada:
A: arreglo unidimensional de símbolos de tipo hilera
N: tamaño del arreglo
Pos: Posición a partir de la cual se realiza la permutación. Inicialmente P = 1.
El método muestra cada una de las permutaciones
Permutar(hilera A[ ], entero N, entero Pos)

{
Es (Pos ≤ N) Si:{Para i = Pos hasta N
{ Intercambiar (A[Pos], A[i]))
Permutar(A, N; Pos +1)
L1 Intercambiar (A[Pos], A[i]))
}
No: Para k= 1 hasta N
Muestre A[k]
}
Intercambiar(hilera A[P], hilera A[L] )

{hilera aux = A[P]
A[P] = A[ L]
A[L] = aux
}
El seguimiento para N = 3 es el siguiente:

L1 CAB 3 3 CAB (6)
L1 CBA 3 3 CBA (5)
CBA
CAB
L1 CBA 3 2 2,3,
L1 BCA 3 3 BCA (4)
L1 BAC 3 3 BAC (3)
BAC
BCA
L1 BAC 3 2 2,3
L1 ACB 3 3 ACB (2)
L1 ABC 3 3 ABC (1)
ABC
ACB
L1 ABC 3 2 2,3
ABC
CBA
ABC
BAC
L0 ABC 3 1 1,2,3
Dr A N Pos I Muestra
Método de Ordenamiento MergeSort y QuickSort
Una técnica muy utilizada para el diseño de algoritmos es "Dividir para conquistar".
Los algoritmos de este tipo se caracterizan por estar diseñados siguiendo estrictamente
las siguientes fases:
Dividir: Se divide el problema en partes más pequeñas.

Conquistar: Se resuelven recursivamente los problemas más pequeños
Combinar: Los problemas más pequeños se combinan para resolver el grande.
El algoritmo de MergeSort es un ejemplo clásico de algoritmo que utiliza el principio de

dividir para conquistar. Si el arreglo a ordenar tiene más de dos elementos se divide en
dos mitades, se invoca recursivamente el algoritmo y luego se hace una mezcla de las
dos mitades ordenadas.
Datos de Entrada:
A: arreglo unidimensional de valores numéricos enteros
LI: Numérico entero. Inicialmente igual a 1
LS: Numérico entero. Inicialmente igual a N(Tamaño del arreglo)
Resultado
MERGESORT (entero A[ ], entero LI, entero LS)

{
entero MED
Es ( LI = = LS) Si: Retorne
MED = (LI + LS) / 2
MERGESORT(A, LI, MED)
L1 MERGESORT(A, MED+1, LS)
L2 MERGE(A, LI, MED, LS)
}L3 //fin
MERGE( entero A[ ], entero INF, entero M, entero SUP)
{
entero N = SUP – INF +1
entero AUX[ N ]
entero I1 = INF, I2 = M +1, J = 1
Mientras ( (I1 M) (I2 SUP) )
{ Es (A[ I1] < A[ I2] ) Si:{ AUX[J] = A[I1]
I1 = I1 +1
}
No: {AUX[J] = A[I2]
I2 = I2 +1
}
J = J +1
}
Mientras (I1 M)
{
AUX[J] = A[I1]
I1 = I1 + 1, J = J +1
}
Mientras (I2 SUP)
{
AUX[J] = A[I2]
I2 = I2 + 1, J = J +1
}
Para j = 1 hasta N
{ A[ INF + j - 1] = AUX[ j ]
}
} // fin Merge
Ejemplo:
12 35 6 20 43 68 9 3 40 70
1 2 3 4 5 6 7 8 9 10
L2 10 10
L1 9 9
L2 9 10 9
L2 8 8
L2 7 7
L1 6 6
L1 6 7 6
L1 6 8 7
L2 6 10 8
L2 5 5
L1 4 4 L3 1 5 10
L2 4 5 4 L3 6 8 10
L2 3 3 L3 9 9 10
L2 2 2 L3 6 7 8
L1 1 1 L3 6 6 7
L1 1 2 1 L3 1 3 5
L1 1 3 2 L3 4 4 5
L1 1 5 3 L3 1 2 3
L1 1 10 5 L3 1 1 2
Dr LI LS M Dr INF M SUP
MergeSort Merge
Análisis de la complejidad del método de Ordenamiento MergeSort
Con base en el método MergeSort anterior, el modelo para encontrar la complejidad es

el siguiente:
1, n =1
T(n) =
2T(n/2) + O(n), n > 1
El cual resulta de tener dos llamadas recursivas de MergeSort con n/2 elementos y O(n)
es el orden de magnitud del método Merge.
Para plantear la ecuación de recurrencia se realiza un cambio de variable y se reemplaza

n por 2i. O sea,
t(2i) = 2t(2i-1) + 2i, n >1
ti = 2ti-1 + 2i
resultando una ecuación de recurrencia lineal no homogénea.

ti(H) = ti - 2ti-1 = 0
Ecuación característica:
r - 2 = 0, r = 2,
ti(H) = c*(2)i
La forma del f(n) para ti(P) es 2i, pero como se presenta multiplicidad, f(n) es igual a:
Ai2i
Reemplazando en la ecuación:
Ai2i – 2[A(i – 1)2i-1] = 2i
Ai2i – Ai2i + A2i = 2i
A2i = 2i, o sea que A = 1
ti = ( c + i) 2i
dado que n =2i y i = log2n

tn= ( c + log2n)n
tn= n*log2n + cn
Lo que indica que el orden de magnitud del MergeSort es O(nlog2n).
O sea que el MergeSort es más eficiente que los métodos de Burbuja, Selección e
Inserción que son de orden de magnitud O(n2).
Método de Ordenamiento QuickSort
Este método también se basa en la estrategia de diseño de algoritmos "Dividir para

conquistar".
El método QuickSort o de Ordenamiento Rápido divide el arreglo a ordenar en dos

sublistas, una con los elementos menores o iguales a un cierto valor denominado pivote,
y otra con los elementos mayores al pivote. El valor del pivote es un valor arbitrario
seleccionado del arreglo de entrada.
El procedimiento es el siguiente:
- Elegir un elemento de la lista a ordenar, al que se denomina pivote.
- Resituar los demás elementos de la lista a cada lado del pivote, de manera que a un
lado queden todos los menores que él, y al otro los mayores. Los elementos iguales al
pivote pueden ser colocados tanto a su derecha como a su izquierda, dependiendo de
la implementación deseada. En este momento, el pivote ocupa exactamente el lugar
que le corresponderá en la lista ordenada.
- La lista queda separada en dos sublistas, una formada por los elementos a la
izquierda del pivote, y otra por los elementos a su derecha.
- Repetir este proceso de forma recursiva para cada sublista mientras éstas contengan
uno o más elementos. Una vez terminado este proceso todos los elementos estarán
ordenados.
Datos de Entrada:
A: arreglo unidimensional de valores numéricos enteros
IZQ: Numérico entero. Inicialmente igual a 1
DER: Numérico entero. Inicialmente igual a N(Tamaño del arreglo)
Resultado
QUICKSORT (entero A[ ], entero IZQ, entero DER)

{
entero i = IZQ, j = DER, aux, pivote
Es ( DER < IZQ) Si: retorne
pivote = (IZQ + DER) / 2
Mientras ( i < = j)
{
Mientras( A[i] < A[pivote])& (i < = DER) i = i + 1
Mientras( A[j] > A[pivote]) & (j > = IZQ) j = j - 1
Es ( i < = j) Si: { aux = A[i]
A[i] = A[j]
A[j] = aux
i=i+1
j=j–1
}
}
QUICKSORT ( A, IZQ, j)
QUICKSORT ( A, i, DER)
}
Ejercicios:
1. Realizar un seguimiento al método QuickSort con el ejemplo del MergeSort

2. Encontrar el orden de Magnitud del QuickSort utilizando el método de Ecuación de
Recurrencias.

Algoritmia II

Cargado por

Copyright:

Formatos disponibles

Algoritmia II

Cargado por

Información del documento

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

Algoritmia II

Cargado por

Copyright:

Formatos disponibles

Curso: Lógica y Representación II

Medición del tiempo de ejecución de un Programa:

- Complejidad temporal: Indica la cantidad de tiempo que requiere un algoritmo

El tiempo de ejecución de un programa en función de n, no sólo depende de los datos

En general, la cantidad de recursos que consume un algoritmo para resolver un

Por ejemplo, el tamaño de cada uno de los siguientes problemas es:

Tipos de Medición de T(N):

Notación Asintótica (O grande)

Tipos de Ordenes de Magnitud:

O(1): Complejidad constante. Es la más eficiente. Resulta de algoritmos que no

Para cuando n es lo suficientemente grande, los órdenes de magnitud se pueden ordenar

La siguiente tabla muestra el comportamiento de las diferentes funciones para diferentes

N O(logbN) O(N) O(N logbN) O(N2) O(N3) O(2N) O(n!)

f(n) = 6N3 + 4N + 5Nlog3N +12

f(n)= N*(N+1) +5N

Asignación del f(n) para cada tipo de instrucción:

- Estructuras de decisión lógica: el f(n) será igual a 1 de evaluar la condición, más

Es (A > D) Si:{ A=A+2

El f(n) asignado a la decisión lógica será igual a: 1 de evaluar la condición (A > D)

Es (A > D) Si: Es (A > C) Si: { A=A+C

- Estructuras de Selección Múltiple: el f(n) será igual a 1 más el máximo f(n)

- Estructuras de Ciclos predefinidos: El f(n) será igual al número de veces que se

Luego el total de veces que se ejecuta el ciclo J es igual a:

más N veces que resulta del fin de chequeo del ciclo J.

El número de veces que se ejecuta el ciclo interno K se puede expresar como,

     

Siendo (1) + (2) igual a:

El número de veces que se ejecuta la instrucción del ciclo va a depender de

En general, si la instrucción que altera la condición del ciclo es multiplicada,

- Llamadas a Procedimientos: Cuando se tiene la llamada a un procedimiento, el

Análisis del Problema:

Programa Suma2 f(n)

Comparando el orden de magnitud de la solución 1 O(N), con el orden de magnitud de

Análisis del Problema:

real Serie_Aritmetica(real a1, real d, entero N) f(n)

y la suma de los N términos es:

Utilizando estas 2 fórmulas, otra solución algorítmica es la siguiente:

real Serie_Aritmetica(real a1, real d, entero N) f(n)

En una serie geométrica:

El N-ésimo término es igual a:

y la suma de los N términos es:

- Fundamentos de Algoritmia. Brassard, Gilles, Bratley, Paul. Prentice-Hall. 1997.

- Estructura de Datos. Libro de Problemas. Luis Joyanes Aguilar, Ignacio Zahonero

3. a) Elaborar un método que tiene como entrada un arreglo unidimensional A y que

4. Encontrar el contador de frecuencia y el orden de magnitud para cada uno de los

tmp= tmp div 2

g) entero p7 (entero n1, entero n2, entero m1, entero m2)

Para j = 1 hasta n, inc 2 {

i) hilera NumBin( entero n)

El proceso consiste en revisar el conjunto de elementos con el fin de localizar un

Los métodos de búsqueda más utilizados son:

hilera BÚSQUEDA_LINEAL( entero V) f(n)

Búsqueda Binaria: este método se utiliza sobre un arreglo unidimensional ordenado. El

Se definen dos variables:

Se ubica el elemento que se encuentra en la posición del medio en el arreglo:

Se compara A[Medio] con el valor a buscar (V):

En el caso de que no exista V en el arreglo, el algoritmo termina cuando LI > LS.

Para el ejemplo, si el valor a buscar V es igual a 15:

A: Arreglo unidimensional ordenado de N valores numéricos enteros

Dependiendo entonces de la periodicidad con que se deban realizar búsquedas sobre un