Lección 033 a 035: Ejercicios de Recursividad

Los siguientes ejercicios aplican, de forma progresiva, los conceptos dados en las lecciones que corresponden al tema Recursión, comprendidas por la 33, 34 y 35 inclusive. Es sumamente importante que traten de realizar la mayoría de ellos para comprender por fin este tema tan complicado.

==================================================================================

Ejercicio 1: Fácil

Escriban una función booleana recursiva llamada SonIguales que reciba dos listas como parámetros y devuelva TURE si son iguales (mismos elementos en el mismo orden), o FALSE en caso contrario.

==================================================================================
Ejercicio 2: Fácil

Escriban una función recursiva llamada ExisteElemento que verifique si un elemento x se encuentra en una lista L.

==================================================================================
Ejercicio 3: Fácil

Escriban una función recursiva llamada Ocurrencia que cuente la cantidad de ocurrencias de un elemento x en una lista L.

Escriban una función recursiva llamada Suma que retorne la suma de los elementos de una lista de enteros  L.

==================================================================================
Ejercicio 4: Fácil

Escriba una función recursiva llamada Eliminar que elimine el elemento x de la lista L.
==================================================================================
Ejercicio 5: Medio

Escriban una función recursiva llamada InsertarOrdenado que inserte en forma ordenada un elemento x en una lista ordenada L.

==================================================================================
Ejercicio 6: Medio

Escriban una función recursiva llamada OrdenarLista que ordene una lista L.
==================================================================================
Ejercicio 7: Medio

Escriban una función recursiva llamada Merge que, a partir de dos listas ordenadas L1 y L2, genere una lista ordenada L3, a través de un proceso de intercalación de elementos (merge).

==================================================================================
Ejercicio 8: Medio

Escriba una función recursiva llamada Invertir que, dada una lista L, la invierta.

==================================================================================
Ejercicio 9: Fácil

Escriba una función recursiva llamada Maximo que calcule el máximo de una lista de naturales L.

==================================================================================
Ejercicio 10: Difícil

En una hilera de una calle con adoquines unos niños juegan a la rayuela. Para esto numeran los adoquines de la siguiente forma:



Los movimientos permitidos del juego son:

• Al principio del juego los niños se ubican en el adoquín 0.
  
• De un adoquín numerado i se puede saltar al adoquín numerado i+1.
  
• De un adoquín numerado i se puede saltar al adoquín numerado i+2 (sin pasar por el adoquín i+1)
  
• Por ejemplo, el número de caminos posibles para n=3 es 3 y son los siguientes: (0,1,2,3), (0,2,3) y (0,1,3).
  

Escriban una función recursiva llamada CaminosPosibles que calcule el número de caminos posibles para alcanzar un adoquín objetivo numerado con n (mayor que cero).

==================================================================================
Ejercicio 11: Medio

Escriban una función recursiva llamada MCD que calcule el Máximo Común Divisor de dos naturales a y b (con a >= b).

==================================================================================
Ejercicio 12 – Problema de las Torres de Hanoi: Muy difícil

Escenario: existen tres cilindros verticales donde es posible insertar discos. En uno de los cilindros hay n discos todos de diferente tamaño, colocados en orden de tamaño con el más chico arriba. Los otros dos cilindros están vacíos.



El  problema es  pasar  la torre de discos completa a otro de  los cilindros  usando como único movimiento elemental  el   cambio de un disco de un  cilindro  a otro  cualquiera,  sin que en ningún momento un disco vaya a colocarse encima de otro más chico que él.  

Escriban el  pseudocódigo de  los procedimientos  que consideren necesarios  para  imprimir  las secuencias de movimientos elementales  que  resuelvan el  problema de  las   torres  de Hanoi, de cualquier tamaño.  Los movimientos elementales son de la forma: MOVER DISCO x DEL cilindroY AL cilindroZ.
En este enlace pueden jugar con el problema de las Torres de Hanoi para visualizarlo mejor.

==================================================================================
Notas acerca de los ejercicios 13 al 17:

Tengan en cuenta que para algunos de los siguientes ejercicios, es importante considerar:

1. Que puede ser necesario definir funciones auxiliares.
   
2. Que   los   parámetros   de   entrada   o  salida   de   las   funciones   pueden   contener  más   de   un elemento (ej: un parámetro que es una pareja).
   
3. Es parte de la resolución de los problemas decidir que parámetros son necesarios considerar para la entrada o salida de la función.
   

====================================================================================
Ejercicio 13: Dificil

Implementen en MODULA-2 y usando recursión el procedimiento del ejercicio 8 del apartado anterior de ejercicios de aplicación. Dicho procedimiento recibe como parámetro una lista de naturales de tipo LNat y muestra todos los números de dicha lista, desde el último al primero, es decir, al revés. Ver el tipo LNat definido en el ejercicio 8 del apartado anterior de ejercicios de aplicación.

====================================================================================
Ejercicio 14: Muy Dificil

Consideren la siguiente representación de polinomios mediante Listas de coeficientes:
P(x) = anxn + an-1x n-1 +…+ a1x1 + a0x0  se representa mediante la lista an, an-1, ... , a1, a0.. Escriban   el  pseudocódigo de  una   función  recursiva  que  evalúe un polinomio usando  la regla de Horner (P(x) = ((...((an* x) + an-1)x )+ ... + a1)x + a0). Luego implementen dicho pseudocódigo en Modula 2.

====================================================================================
Ejercicio 15: Dificil

Escriban una  función  recursiva  SumaC  que dada una  lista de Enteros  positivos, indique la mínima cantidad de elementos consecutivos al final de la lista cuya suma  sea mayor o  igual  que una determinada cantidad C, que   se   recibe   como parámetro. Algunos ejemplos son:

1, 2, 3, 4, 5, 6, 7 con C = 8 da 2 porque ( 6+7=13 > 8)
7, 6, 5, 4, 3, 2, 1 con C = 8 da 4 porque (4+3+2+1=10 > 8)
3, 6, 1, 7, 5, 2, 9 con C = 13 da 3 porque (5+2+9=16 > 13)

Nota: Si  C supera  la suma de todos  los elementos de  la  lista deberá retornarse  la cantidad de elementos que tiene la lista.
Para este ejercicio no se permite invertir la lista y luego resolverlo para los primeros elementos.

====================================================================================
Ejercicio 16: Muy difícil

Consideren la siguiente representación de números binarios mediante Listas de dígitos:

el número binario 1 (en base 10 es el 1) se representa mediante la lista [1]
el número binario 10 (en base 10 es el 2) se representa mediante la lista [1,0]
el número binario 110 (en base 10 es el 6) se representa mediante la lista [1,1,0]

Escriban  un  procedimiento   recursivo  Incremento  que  le  sume 1 a un número binario, sin duplicar la lista. Algunos ejemplos de resultados son:

Incremento([1]) = [1,0]
Incremento([1,0])= [1,1]
Incremento([1,1,0]) = [1,1,1]

Sugerencia: Considere como precondición de su procedimiento que la lista no puede ser vacía.

====================================================================================
Ejercicio 17: Muy difícil

Una  isla  es  una  agrupación de celdas   (al  menos  una)   con  valor  1,  cada una de  las   cuales  es adyacente horizontal  y/o verticalmente a una celda del  mismo grupo. Una  isla está delimitada, horizontal y verticalmente, por celdas con valor 0 o por los límites (fronteras) del mapa.



Por   ejemplo,  en   el  mapa   que   se   presenta   de tamaño   5x10,   hay   6   islas,   las   cuales están compuestas de las siguientes celdas:

• Isla 1: (1,1) (1,2) (1,3) (2,1) (2,2)
  
• Isla 2: (3,4)
  
• Isla 3: (4,5)
  
• Isla 4: (5,1) (5,2) (5,3)
  
• Isla   5:  (1,6) (1,7) (1,8) (1,9) (1,10)   (2,10) (2,7) (3,7) (4,7) (5,7) (5,8)
  
• Isla 6: (5,10)
  

Notar que (3,4) y (4,5) no forman una isla, sino que son dos islas distintas.

Escriban el  pseudocódigo de un programa que, dado un mapa representado por una matriz de tamaño  NxM  de   ceros   y   unos,  donde   0   representa   agua   y   1   tierra,  imprima   las   islas encontradas en el mismo.

Nota: Se pide que el  programa  imprima las celdas de cada isla del mapa  siguiendo el formato del ejemplo. El orden de impresión entre las islas no es relevante, ni tampoco el orden en que se imprimen las celdas de cada isla.

=========================================================================

Navegación:

• Ir al índice del curso.
  
• Ir al índice de ejercicios de Modula 2.
  

Buenas, por ahora teoricamente voy entendiendo las cosas, queria saber si el razonamiento de este codigo es correcto:

Código:

PROCEDURE ExisteElemento ( lista : Lista; num : INTEGER) : BOOLEAN;
   BEGIN
      IF lista=NIL THEN RETURN FALSE
      ELSIF lista^.num=num THEN RETURN TRUE
      ELSIF lista^.sig=NIL THEN
         IF lista^.num=num THEN RETURN TRUE
         ELSE RETURN FALSE
         END;
      ELSIF ExisteElemento(lista^.sig,num) THEN RETURN TRUE
      END;
      RETURN FALSE;
   END ExisteElemento;

En apariencia estaría bien, deberías seguir tu código a mano paso a paso con algunos ejemplos de entrada y ver si realmente aplica para todos los casos.

Saludos.