Lista de ejercicios 02
Pilas, Colas y repaso de Recursividad
IMPORTANTE: Implementar los ejercicios
siguientes, utilizando POO en C++
1. Elabore un programa que permita simular el
funcionamiento de una estructura tipo Pila que contenga los métodos: inserta_pila, sacar_pila, y mostrar_pila.
2. Lea una palabra por el teclado y determine si la
palabra es palíndromo”
3. implemente el juego algoritmo iterativo para el juego
de las torres de Hanoi (use pilas para simular la recursividad).
4. Leer una expresión aritmética en notación infija y conviértala a notación postfija y prefija.
5. Leer una expresión aritmética en notación post fija y
obtenga su valor numérico. (Complemente le programa del ejercicio anterior).
6. Leer una frase y luego invierta el orden de las palabras
en la frase. Por Ejemplo: “una imagen vale por mil palabras” debe convertirse
en “palabras mil por vale imagen una”.
7. Simular la operación de n pilas operando
simultáneamente y donde se saca y¡o
inserta elementos al azar a cualquiera de las pilas. Determine cual es la pila
de mayor trabajo y cual es la pila de menos trabajo en un tiempo determinado de
operación.
8. Usando pilas efectúe operaciones de suma y resta de
dos números de más de 10 dígitos.
9. Mediante el uso de pilas efectúe la operación de
división de dos números bastante grandes (más de 10 dígitos). Para ello utilice
el método de restas sucesivas para efectuar la división.
10. En un almacén se guarda mercadería en contenedores. No
es posible colocar más de n contenedores uno encima del otro y, no hay área
para más de m pilas de contenedores. Cada contendor tiene un número y un nombre de la empresa propietaria.
Elabore un programa que permita gestionar el ingreso y salida de contenedores.
Note que para retirar un contenedor es necesario retirar los contenedores que
están encima de él y colocarlos en otra pila.
11. Elabore un programa que lea un archivo .CPP y
determine si los símbolos { } , [ ] y ( ) estén correctamente balanceados. Si no se
encuentra balanceado, que muestre el error indicando el símbolo faltante.
12. Se desea implementar dos pilas, y se dispone de un
solo vector de N componentes. Implementar ambas pilas de manera que se pueda
aprovechar al máximo el vector. Las operaciones de pila tendrán que llevar un
parámetro adicional que indique sobre qué pila se quiere realizar la operación
(pila 1 ó pila 2).
Nota: Las
dos pilas crecen partiendo de los extremos del arreglo
13. Implementar las mismas
operaciones que se indican en el ejercicio 1 pero ahora utilice listas
enlazadas.
14. Se tienen dos pilas (stacks)
que contienen números enteros; la primera ordenada ascendentemente desde el
tope hacia el fondo, y la segunda ordenada descendentemente desde el tope hacia
el fondo. Si se cuenta con la clase CPila que
contiene las operaciones básicas definidas para pilas, elabore un programa que
fusione ambas pilas en una tercera ordenada descendentemente desde el tope
hacia el fondo.
NOTA: no debe utilizar pilas auxiliares.
15. Se tiene una lista con los datos de los clientes de
una compañía de telefonía celular, los cuales pueden aparecer repetidos en la
lista, si tienen registrado más de un número telefónico. La compañía para su
próximo aniversario desea enviar un regalo a sus clientes, sin repetir regalos
a un mismo cliente. Los regalos se encuentran almacenados en una pila de
regalos. Se desea elaborar un programa en C++
que permita generar una nueva estructura donde los clientes aparezcan
sólo una vez con sus regalos asignados.
16. Escribir un programa que invierta el contenido de una
cola. Usted puede utilizar estructuras de datos auxiliares para hacerlo.
17. Una matriz de N-filas puede ser vista como N-colas
consecutivas, donde la operación de introducir un elemento en la cola, debería
recibir el elemento a introducir y el identificador de la cola i donde se
desea meter el elemento. Elabore un método que permita implementar la operación
inserta_cola en una sucesión de N-colas en un objeto
matriz NxM. M es la capacidad máxima de cada cola.
18. Implemente el objeto Cola en C++ de manera que reciba
los datos de personas en una cola de un banco, esto es, nombre y el tipo de
transacciones a realizar. Se requiere
conocer el tiempo estimado de permanencia de cualquier persona el la cola, si
se conocen los tiempos estimados para cada tipo de transacción:
Retiro 4 min
Depósito 2
min
Consulta 3.5
min
Actualización 5 min
Pagos 2 min
19. Elabore un programa en C++ que simule el
funcionamiento de una estructura de datos tipo Cola_Circular
y otra estructura tipo Cola_Prioritaria. Para el
primer caso use arreglos y para el segundo caso use listas enlazadas. Para el
caso de las colas prioritarias asigne un nivel de prioridad de 1, 2 o 3. El
nivel 1 indica mayor prioridad y 3 la menor prioridad. El programa debe
contener los métodos Inserta_Circular, Elimina_Citrcular, Mostrar_Cola, Inserta_Priorit, Elimina_Priorit.
20. Unos vehículos blindados intentan pasar un puente
defectuoso. Para ello forman un cola para atravesarlo y la probabilidad de
éxito al momento de cruzar e puente es de 0.9 al inicio. Cada vez que un
vehículo entra al puente, éste se deteriora más y la probabilidad de éxito se
reduce en 0.06. Para un total de n vehículos
blindados, cuantos lograron atravesar el puente?
Cuántos cayeron en el intento?
Ejercicios de repaso – Recursividad
1.
Implemente un
algoritmo recursivo que permita calcular el número de combinaciones de n
elementos tomados de m en m.
2. Escribir una función recursiva que devuelva la
cantidad de dígitos de un número entero.
3. Escribir un procedimiento recursivo que calcule z*v,
mediante sumas sucesivas, con z , v enteros.
4. Proponer un procedimiento recursivo tal que dado un
arreglo de números reales permita calcular el mínimo elemento del vector y su
posición
5. Diseñe e implemente un método recursivo que nos permita
obtener el determinante de una matriz cuadrada de dimensión de orden nxn.
6. Implementa una función recursiva que, dado un número
entero, muestre por pantalla su valor en binario.
7. Escribir una función recursiva que halle la suma de
los primeros "n" números naturales.
8. Determinar si un número es primo utilizando
recursividad.
9. Calcular la suma de los elementos impares de un
arreglo de n enteros. Use recursividad.
10. Determinar en forma recursiva la secuencia de
movimientos de n discos sobre una torre de Hanoi que posee los pilares_ Origen
– Auxiliar – Destino