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 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