Fecha y hora actual: Martes 16 Oct 2018 13:45
Índice del Foro

Foros de programación informática, diseño gráfico y Web

En esta comunidad intentaremos dar soporte de programación a todos los niveles, desde principiantes a profesionales de la informática, desarrollo de programas, programación web y mucho más.

Programando desde 0: 38- Ejercicios de recursividad.

Responder al Tema Ir a página Anterior1234Siguiente

Índice del Foro > Programación en general > Programando desde 0: 38- Ejercicios de recursividad.

Autor Mensaje
daalpri
Usuario Inquieto


Registrado: 28 Dic 2014
Mensajes: 104

Mensaje Publicado: Viernes 17 Mar 2017 18:02

Título del mensaje: Programando desde 0: 38- Ejercicios de recursividad.

Responder citando

Ejercicio2:

Este me parecio mas sencillo que el primero
Use la misma estructura de datos.
Código:

PROCEDURE ExisteElemento(L:LNat;x:CARDINAL):BOOLEAN;

VAR
 aux:LNat;
 existe:BOOLEAN;

BEGIN

(*Iniciamos la variable*)
aux:=L;

(*Analizamos los casos posibles para una solucion inmediata al problema*)

(*El primer caso base sera que la lista este vacia o lleguemos al final de ella
sin encontrar coincidencias, por lo tanto sera FALSE*)
IF aux=NIL THEN
 existe:=FALSE;

(*El segundo caso base sera que encontremos el elemento que buscamos, por tanto
sera TRUE*)
ELSIF aux^.elem=x THEN
 existe:=TRUE;

(*La llamada recursiva sera en los demas casos, es decir si los elementos
comparados no coinciden y aun no hemos llegado al final de la lista, la rellamada
sera desde la posicion siguiente en la lista*)
ELSE
 existe:=ExisteElemento(aux^.sig,x);
 END;

(*El retorno de la funcion sera la variable "existe"*)
RETURN existe;

END ExisteElemento;

Volver arriba
Ver perfil del usuario Enviar mensaje privado
Kyshuo Ayame
Moderador Global


Registrado: 07 Ene 2011
Mensajes: 1030

Mensaje Publicado: Viernes 17 Mar 2017 18:13

Título del mensaje: Programando desde 0: 38- Ejercicios de recursividad.

Responder citando

Un trabajo excelente. La recursividad cuesta al principio pero como ves lo vas haciendo. No importa si tus códigos quedan complejos o largos, ahora estás entrenando tu mente, desarrollando conexiones neuronales (literalmente es así). Luego será sencillo.

Fíjate, si hiciste el juego Buscaminas, que despejar las celdas circundantes se puede hacer muy fácil con recursividad. Cuando yo estudiaba se nos pedía que lo hiciéramos así, y podrás imaginarte que casi muero en el intento.

Es un gusto poner este material y que sea aprovechado por la gente que, como tu, dedica su tiempo a tomar ACCION y hacer los ejercicios.

Sigue así.

Volver arriba
Ver perfil del usuario Enviar mensaje privado
daalpri
Usuario Inquieto


Registrado: 28 Dic 2014
Mensajes: 104

Mensaje Publicado: Sábado 18 Mar 2017 00:47

Título del mensaje: Programando desde 0: 38- Ejercicios de recursividad.

Responder citando

Ejercicio 3:

Este tampoco me parecio demasiado dificil.
La estructura usada para estas dos funciones
Código:

TYPE
 LInt=POINTER TO NodoLista;
 NodoLista=RECORD
  elem:INTEGER;
  sig:LInt;
  END;


Primera parte:
Código:

PROCEDURE Ocurrencia(L:LInt;x:INTEGER):CARDINAL;

VAR
 aux:LInt;
 coincidencias:CARDINAL;

BEGIN

(*Iniciamos las variables*)
aux:=L;
coincidencias:=0;

(*el caso base que se me ocurre y que terminaria la recursion seria llegar al
final, ya que de todas formas la lista habria que recorrerla entera*)
IF aux<>NIL THEN

(*Si el elemento coincide con el que buscamos sumamos 1 a coincidencias*)
 IF aux^.elem=x THEN
  coincidencias:=coincidencias+1;
  END;

(*A coincidencias le sumamos tambien las coincidencias que nos resulten de la
rellamada desde la posicion siguiente, de forma que ira recogiendo todas las
coincidencias de la lista*)
 coincidencias:=coincidencias+Ocurrencia(aux^.sig,x);
 END;

(*De esta forma retornamos el valor de coincidencias*)
RETURN coincidencias;

END Ocurrencia;

Y la segunda parte:
Código:

PROCEDURE Suma(L:LInt):INTEGER;

VAR
 aux:LInt;
 suma:INTEGER;

BEGIN

(*Iniciamos las variables*)
aux:=L;
suma:=0;

(*El caso base sera llegar al final de la lista*)
IF aux<>NIL THEN

(*Mientras no lleguemos al final iremos sumando el elemento actual mas la suma
de las rellamadas*)
 suma:=suma+aux^.elem+Suma(aux^.sig);
 END;

(*Retornamos el valor que ha ido acumulando la variable "suma"*)
RETURN suma;

END Suma;

Volver arriba
Ver perfil del usuario Enviar mensaje privado
daalpri
Usuario Inquieto


Registrado: 28 Dic 2014
Mensajes: 104

Mensaje Publicado: Lunes 20 Mar 2017 16:08

Título del mensaje: Programando desde 0: 38- Ejercicios de recursividad.

Responder citando

Ejercicio 4:
este me ha dado muchos dolores de cabeza, pero ya esta jijiji
Código:

PROCEDURE Eliminar(L:LInt;x:INTEGER):LInt;

VAR
 aux,lista:LInt;

BEGIN

(*Iniciamos la variable con la que trabajaremos*)
lista:=L;

(*El caso base sera si el elemento que queremos borrar es el primero de la lista,
en ese caso lo eliminamos y listo*)
IF lista^.elem=x THEN
 aux:=lista^.sig;
 DISPOSE(lista);
 lista:=aux;

(*en caso contrario seguimos avanzando en la lista y recojeremos la regresion en
lista^.sig, para enganchar la lista detras del elemento eliminado*)
ELSE
 lista^.sig:=Eliminar(lista^.sig,x);
 END;

(*Retornamos el valor de "lista"*)
RETURN lista;

END Eliminar;

Volver arriba
Ver perfil del usuario Enviar mensaje privado
daalpri
Usuario Inquieto


Registrado: 28 Dic 2014
Mensajes: 104

Mensaje Publicado: Lunes 20 Mar 2017 16:16

Título del mensaje: Programando desde 0: 38- Ejercicios de recursividad.

Responder citando

¿Para el ejercicio 5 suponemos que la lista ya esta ordenada?

Volver arriba
Ver perfil del usuario Enviar mensaje privado
Kyshuo Ayame
Moderador Global


Registrado: 07 Ene 2011
Mensajes: 1030

Mensaje Publicado: Lunes 20 Mar 2017 17:45

Título del mensaje: Programando desde 0: 38- Ejercicios de recursividad.

Responder citando

Si, la idea es que la operación vaya recibiendo elementos y los inserte ordenados. Tendrás que ver el caso de lista vacía y luego ir agrandándola.

Volver arriba
Ver perfil del usuario Enviar mensaje privado
daalpri
Usuario Inquieto


Registrado: 28 Dic 2014
Mensajes: 104

Mensaje Publicado: Miércoles 22 Mar 2017 17:16

Título del mensaje: Programando desde 0: 38- Ejercicios de recursividad.

Responder citando

Ejercicio 5:
Código:

PROCEDURE InsertarOrdenado(L:LInt;x:INTEGER):LInt;

VAR
 aux:LInt;

BEGIN

(*Analizamos los casos en que la solucion es inmediata*)
(*El primer caso base es cuando la lista es vacia*)
IF L=NIL THEN
 NEW(L);
 L^.elem:=x;
 L^.sig:=NIL;

(*Otro caso de solucion inmediata seria si x es mayor que el elemento, entonces
colocamos x antes del elemento*)
ELSIF L^.elem>=x THEN
 NEW(aux);
 aux^.elem:=x;
 aux^.sig:=L;
 L:=aux;

(*Tambien es inmediato si llegamos al final de la lista y no hemos encontrado
ningun elemento que sea mayor que x*)
ELSIF L^.sig=NIL THEN
 NEW(L^.sig);
 aux:=L^.sig;
 aux^.elem:=x;
 aux^.sig:=NIL;

(*Para los demas casos hacemos la rellamada a la funcion desde la posicion
siguiente, quedando pendiente de recoger el resultado la posicion siguiente a la
actual*)
ELSE
 L^.sig:=InsertarOrdenado(L^.sig,x);
 END;

(*Retornamos el valor de L para cada caso*)
RETURN L;

END InsertarOrdenado;

Volver arriba
Ver perfil del usuario Enviar mensaje privado
daalpri
Usuario Inquieto


Registrado: 28 Dic 2014
Mensajes: 104

Mensaje Publicado: Miércoles 29 Mar 2017 22:30

Título del mensaje: Programando desde 0: 38- Ejercicios de recursividad.

Responder citando

Ejercicio 6:
Código:
PROCEDURE OrdenarLista(L:LInt):LInt;

VAR
 aux:LInt; (*para recorrer la lista*)
 menor:LInt; (*para guardar el menor elemento de la lista*)
 apuntador:LInt; (*para guardar la posicion anterior al menor elemento y poder
                   enlazar las dos partes en que queda divivida la lista*)
      
BEGIN

(*Iniciamos la variable para recorrer la lista*)
aux:=L;

(*Si la lista esta vacia*)
IF aux<>NIL THEN

(*O consta de un solo elemento ya esta ordenada*)
 IF aux^.sig<>NIL THEN

  menor:=aux; (*de momento el menor elemento sera el primero*)

  WHILE aux^.sig<>NIL DO (*recorremos la lista*)

(*Comparamos "menor" con el elemento siguiente de la lista*)
   IF menor^.elem>aux^.sig^.elem THEN (*y si es mayor*)
    menor:=aux^.sig; (*el siguiente elemento sera el menor de momento*)
    apuntador:=aux; (*dejamos un puntero apuntando al elemento anterior al
                     menor para enlazar la lista cuando llevemos el elemento
           "menor" al principio de la lista*)
    END; (*del IF*)

   aux:=aux^.sig; (*avanzamos en la lista*)

  END; (*del WHILE*)

 (*Hasta aqui ya tenemos buscado el menor elemento de la lista, lo sacamos de la
 lista lo colocamos delante del primero salvo que el menor ya sea el primero*)
  IF menor<>L THEN
   apuntador^.sig:=menor^.sig;
   menor^.sig:=L;
   L:=menor;
   END;

 (*Rellamamos al procedimiento para hallar el siguiente de la lista*)
  L^.sig:=OrdenarLista(L^.sig);

  END; (*del IF secundario*)
 END; (*del IF principal*)

RETURN L; (*retornamos la lista con el menor elemento colocado al principio*)

END OrdenarLista;

Volver arriba
Ver perfil del usuario Enviar mensaje privado
daalpri
Usuario Inquieto


Registrado: 28 Dic 2014
Mensajes: 104

Mensaje Publicado: Miércoles 29 Mar 2017 22:33

Título del mensaje: Programando desde 0: 38- Ejercicios de recursividad.

Responder citando

La idea del ejercicio 7 es ir cogiendo elementos de una lista y otra alternativamente e ir ordenandolos o unir las dos listas y despues ordenar la resultante?
Gracias de antemano

Volver arriba
Ver perfil del usuario Enviar mensaje privado
Kyshuo Ayame
Moderador Global


Registrado: 07 Ene 2011
Mensajes: 1030

Mensaje Publicado: Jueves 30 Mar 2017 18:30

Título del mensaje: Programando desde 0: 38- Ejercicios de recursividad.

Responder citando

La idea es ir mirando ambas listas e ir insertando ordenadamente en L3 si que se modifiquen las listas originales.

El ejercicio no aclara si L3 debe compartir memoria con las listas L1 y L2, así que hazlo como te parezca mejor.

Volver arriba
Ver perfil del usuario Enviar mensaje privado
daalpri
Usuario Inquieto


Registrado: 28 Dic 2014
Mensajes: 104

Mensaje Publicado: Lunes 24 Sep 2018 13:00

Título del mensaje: Programando desde 0: 38- Ejercicios de recursividad.

Responder citando

Pues despues de tener que abandonar el curso por problemas familiares y personales, por fin puedo retomarlo donde lo deje.

Mi solucion para el ejercicio7:
Código:

PROCEDURE Merge(L1,L2:LNat):LNat;

VAR
 L3:LNat;

BEGIN

(*Si las dos listas estan vacias, la nueva tambien lo estara*)
IF (L1=NIL) AND (L2=NIL) THEN
 NEW (L3);
 L3:=NIL;

(*Si una de las dos listas esta vacia o llega al final antes que la otra a
partir de ese punto solo añadiremos a la lista nueva los elementos de la que
no este vacia*)
ELSIF L1=NIL THEN
 L3:=L2;

ELSIF L2=NIL THEN
 L3:=L1;

(*Si las dos listas tienen elementos, creamos los nodulos en L3 y los llenamos
con el primer dato de cada lista*)
ELSE
  NEW (L3);
  L3^.elem:=L1^.elem;
  NEW (L3^.sig);
  L3^.sig^.elem:=L2^.elem;

(*El siguiente dato queda a la espera de los 2 nodulos que formaran los dos
siguientes datos de las listas originales*)
  L3^.sig^.sig:=Merge(L1^.sig,L2^.sig);
 END;

(*Por ultimo ordenamos la lista resultante*)
L3:=OrdenarLista(L3);

RETURN L3;

END Merge;


espero que Kyshuo aun este por aqui para brindarme su ayuda

Volver arriba
Ver perfil del usuario Enviar mensaje privado
Kyshuo Ayame
Moderador Global


Registrado: 07 Ene 2011
Mensajes: 1030

Mensaje Publicado: Martes 25 Sep 2018 13:49

Título del mensaje: Programando desde 0: 38- Ejercicios de recursividad.

Responder citando

Siempre ando por aquí Guiño

Un gran trabajo amigo. Y por cierto, gracias por tus palabras.

Volver arriba
Ver perfil del usuario Enviar mensaje privado
daalpri
Usuario Inquieto


Registrado: 28 Dic 2014
Mensajes: 104

Mensaje Publicado: Martes 25 Sep 2018 17:51

Título del mensaje: Programando desde 0: 38- Ejercicios de recursividad.

Responder citando

Ejercicio8:
Código:

PROCEDURE Invertir(L:LInt):LInt;

(*Usamos dos variables, "iter" para recorrer la lista hasta el ultimo elemento
y "aux" para copiar ese elemento y colocarlo al principio*)
VAR
 iter,aux:LInt;

BEGIN

(*Discriminamos que la lista no este vacia que seria un caso base*)
IF L<>NIL THEN

 (*Discriminamos tambien que no sea una lista con un unico elemento, que
 tambien seria un caso base*)
 IF L^.sig<>NIL THEN

  (*Usamos "iter" para recorrer la lista hasta que estemos apuntando al
  ultimo elemento*)
  iter:=L;

  WHILE iter^.sig<>NIL DO
   iter:=iter^.sig;
   END;

  (*Creamos un puntero "aux" con los mismos datos del ultimo elemento*)
  NEW(aux);
  aux^.elem:=iter^.elem;
  aux^.sig:=NIL;

  (*Eliminamos ahora el ultimo elemento de la lista*)
  iter:=L;
  WHILE iter^.sig^.sig<>NIL DO
   iter:=iter^.sig
   END;
   DISPOSE (iter^.sig);
   iter^.sig:=NIL;

  (*Colocamos aux al principio de la lista*)
  aux^.sig:=L;
  L:=aux;

  (*El elemento siguiente de la lista sera el ultimo que ha quedado*)
  L^.sig:=Invertir(L^.sig);

  END;
 END;

(*Retornamos la nueva lista*)
RETURN L;

END Invertir;

Volver arriba
Ver perfil del usuario Enviar mensaje privado
daalpri
Usuario Inquieto


Registrado: 28 Dic 2014
Mensajes: 104

Mensaje Publicado: Miércoles 26 Sep 2018 11:45

Título del mensaje: Programando desde 0: 38- Ejercicios de recursividad.

Responder citando

Ejercicio 9:
Código:

PROCEDURE Maximo(L:LNat):CARDINAL;

(*Una variable para ir recogiendo el elemento mayor*)
VAR
 mayor:CARDINAL;

BEGIN

(*Si la lista esta vacia retornamos 0*)
IF L=NIL THEN
 RETURN 0;

(*Si la liste solo tiene un elemento, sera el mayor*)
ELSIF L^.sig=NIL THEN
 RETURN L^.elem;

(*Si tiene mas de un elemento vamos avanzando por la lista, en un primer momento
asignamos a "mayor" el ultimo de la lista y en la regresion vamos devolviendo
el mayor de la comparacion del que consideramos mayor y el elemento anterior*)
ELSE
 mayor:=Maximo(L^.sig);
 IF mayor>L^.elem THEN
  RETURN mayor;
 ELSE
  RETURN L^.elem;
  END;
 END;

END Maximo;

Volver arriba
Ver perfil del usuario Enviar mensaje privado
daalpri
Usuario Inquieto


Registrado: 28 Dic 2014
Mensajes: 104

Mensaje Publicado: Sábado 06 Oct 2018 13:54

Título del mensaje: Programando desde 0: 38- Ejercicios de recursividad.

Responder citando

Ufff, este me ha dado muchos quebraderos de cabeza, tantos que al final hice algo de trampa.
Como las baldosas estan numeradas de 0 en adelante, en lugar de trabajar con listas encadenadas trabaje con numeros naturales.

Despues de hacer cientos de listas de numeritos (0,1,2,3,4,5), (0,2,3,4,5), (0,1,3,4,5)... y un monton de dibujitos de las baldosas y los saltos, se me ocurrio que para llegar a una baldosa, por ejemplo la 5, se podia llegar desde la baldosa 4 (4+1) o desde la baldosa 3 (3+2), que eran los unicos movimientos posibles, y asi con todas menos para la baldosa 1 y la 2.

Bueno, sin mas rollo te dejo el codigo y espero tus comentarios
Código:

MODULE Cap38Ejercicio10;

FROM SWholeIO IMPORT ReadCard,WriteCard;
FROM STextIO IMPORT WriteString,WriteLn;

VAR

 BaldosaDestino:CARDINAL;

(*----------------------------------------------------------------------------*)

PROCEDURE CaminosPosibles(Destino:CARDINAL):CARDINAL;

BEGIN

IF Destino=1 THEN
 RETURN 1;
ELSIF Destino=2 THEN
 RETURN 2;
ELSE
 RETURN CaminosPosibles(Destino-1)+CaminosPosibles(Destino-2);
 END;

END CaminosPosibles;

(*----------------------------------------------------------------------------*)

BEGIN

WriteString("¿A que baldosa quieres saltar? ");
ReadCard(BaldosaDestino);
WriteLn;
WriteLn;
WriteString("Existen ");
WriteCard(CaminosPosibles(BaldosaDestino),1);
WriteString(" caminos");
WriteLn;
WriteLn;

END Cap38Ejercicio10.

Volver arriba
Ver perfil del usuario Enviar mensaje privado
Responder al Tema Ir a página Anterior1234Siguiente
Mostrar mensajes anteriores:   
Ir a:  
Todas las horas están en GMT + 2 Horas

Temas relacionados

Tema Autor Foros Respuestas Publicado
El foro no contiene ningún mensaje nuevo

Llamada a web service desde form

mrrobot2 Programación Web en general 1 Martes 14 Nov 2017 00:50 Ver último mensaje
El foro no contiene ningún mensaje nuevo

[Duda] Ejercicios Archivo Binario - En C

Pedrolo C, C#, Visual C++ 1 Viernes 03 Nov 2017 04:17 Ver último mensaje
El foro no contiene ningún mensaje nuevo

Crear web desde 0

javitc Programación Web en general 11 Sábado 30 Sep 2017 21:23 Ver último mensaje
El foro no contiene ningún mensaje nuevo

Nuevo desde México!

MarioC Preséntate a la comunidad 1 Viernes 30 Dic 2016 19:39 Ver último mensaje
El foro no contiene ningún mensaje nuevo

Control HTML (o Jquery) desde VBA

morfeoct Visual Basic y VBA 3 Jueves 24 Nov 2016 18:34 Ver último mensaje
Panel de Control
No puede crear mensajes, No puede responder temas, No puede editar sus mensajes, No puede borrar sus mensajes, No puede votar en encuestas,