PEC3 20211 Solucion

Prácticas de Programación
PEC3 - 20211
Fecha límite de entrega: 31 / 10 / 2021
Formato y fecha de entrega
La PEC debe entregarse antes del día 31 de octubre de 2021 a las 23:59.
Es necesario entregar un fichero en formato ZIP, que contenga:
● Un documento en formato pdf con las respuestas de los ejercicios. El documento
debe indicar en su primera página el nombre y apellidos del estudiante que
hace la entrega.
Es necesario hacer la entrega en el apartado de entregas de EC del aula de teoría
antes de la fecha de entrega.
Objetivos
● Saber interpretar y seguir el código de terceras personas.

● Adquirir los conceptos teóricos explicados sobre las técnicas de análisis de algoritmos
y recursividad.
● Diseñar funciones recursivas, identificando los casos base y recursivos, siendo
capaces de simular la secuencia de llamadas dada una entrada.
PEC 3 – Prácticas de programación 20211 pag 1

Criterios de corrección:
Cada ejercicio tiene asociada su puntuación sobre el total de la actividad. Se valorará

tanto que las respuestas sean correctas como que también sean completas.
● No seguir el formato de entrega, tanto por lo que se refiere al tipo y nombre
de los ficheros como al contenido solicitado, comportará una penalización
importante o la cualificación con una D de la actividad.
● En los ejercicios en que se pide lenguaje algorítmico, se debe respetar el
formato.
● En el caso de ejercicios en lenguaje C, estos deben compilar para ser
evaluados. Si compilan, se valorará:
○ Que funcionen tal como se describe en el enunciado.
○ Que es respeten los criterios de estilo y que el código esté
debidamente comentado.
○ Que les estructuras utilizadas sean las correctas.
Aviso
Aprovechamos para recordar que está totalmente prohibido copiar en las PECs de
la asignatura. Se entiende que puede haber un trabajo o comunicación entre los
estudiantes durante la realización de la actividad, pero la entrega de esta debe que
ser individual y diferenciada del resto. Las entregas serán analizadas con
herramientas de detección de plagio.
Así pues, las entregas que contengan alguna parte idéntica respecto a entregas de
otros estudiantes serán consideradas copias y todos los implicados (sin que sea
relevante el vínculo existente entre ellos) suspenderán la actividad entregada.
Guía citación:
https://biblioteca.uoc.edu/es/contenidos/Como-citar/index.html
Monográfico sobre plagio:

http://biblioteca.uoc.edu/es/biblioguias/biblioguia/Plagio-academico/

Observaciones
Esta PEC presenta el proyecto que se desarrollará durante las distintas actividades
del semestre, que se ha simplificado y adaptado a las necesidades académicas.
En este documento se utilizan los siguientes símbolos para hacer referencia a los
bloques de diseño y programación:
Indica que el código mostrado es en lenguaje algorítmico.
Indica que el código mostrado es en lenguaje C.
Muestra la ejecución de un programa en lenguaje C.

Ejercicio 1: Conceptos básicos de recursividad [40%]
Dada la función recursiva mystery, calcula qué valor devuelve la llamada mystery(6)
y completa el modelo de las copias para ver cómo has llegado al resultado:
function mystery (n : integer ) : integer

var
result : integer;
end var
if n ≤ 1 then
result := 2;
else
if (n mod 2) = 0 then
result := n + mystery (n-1);
else
result := n + (mystery (n-2) * mystery(n-3)) ;
end if
end if
return result;
end function
El resultado es 39, que resulta de ejecutar la secuencia de

llamadas representadas en la siguiente figura:
Mystery(6)
Result = 39
Mystery(5)
Result = 33
Mystery(3) Mystery(2)
Result = 7 Result = 4
Mystery(1) Mystery(0) Mystery(1)

Result = 2 Result = 2 Result = 2

Ejercicio 2: Diseño de algoritmos recursivos [60%]
Para el análisis de los contactos estrechos, se ha detectado la necesidad de tener

una mejor representación de la información de posicionamiento. Con este fin, a partir
de los tipos tCoordinate y tDateTime utilizados anteriormente se han definido los
siguientes tipos de datos:
type
tCoordinateNode = record
coordinate : tCoordinate;
numPersons : integer;
next: pointer to tCoordinateNode;
end record
tDateTimeNode = record
dateTime : tDateTime;
coordinatesList : pointer to tCoordinateNode;
next: pointer to tDateTimeNode;
end record
end type
La idea es guardar una lista de momentos de tiempo tDateTime, y para cada

momento de tiempo la lista de coordenadas tCoordinate en las que hay alguna
persona. El tipo de datos tDateTimeNode representa un nodo de la lista de momentos
de tiempo, y el tipo tCoordinateNode un nodo de la lista de coordenadas. A
continuación se puede ver una representación gráfica:

Donde los nodos en azul representan los distintos momentos temporales
tDateTimeNode, y los nodos en gris las distintas coordenadas para cada momento
de tiempo tCoordinateNode.
Se pide definir en lenguaje algorítmico las siguientes funciones recursivas:
a) La función numPeopleCoordinates que dado el puntero al primer nodo de una

lista de coordenadas calcule el total de personas que hay en las coordenadas
de la lista. La firma de la función es la siguiente:
function numPeopleCoordinates(list: pointer to tCoordinateNode) : integer
b) La función numPeopleTime que dado el puntero al primer nodo de una lista

ordenada de momentos temporales (cada nodo contiene información de un
momento temporal estrictamente mayor al anterior), un momento temporal
inicial y un momento temporal final, calcule el total de personas que hay en
todas las coordenadas entre estos momentos temporales.
function numPeopleTime(list: pointer to tDateTimeNode, start: tDateTime,

end: tDateTime) : integer
Para este ejercicio podéis disponer de la función:
function datetime_cmp(dt1: tDateTime, dt2: tDateTime): integer
que dados dos momentos temporales dt1 y dt2, devuelve:
● -1 si dt1 < dt2

● 0 si dt1 == dt2
● 1 si dt1 > dt2

Nota: Recordad que en los nodos terminales de una lista, los punteros “next” tienen
un valor NULL. De la misma manera, una lista vacía será un puntero con un valor a
NULL.
Solución
function numPeopleCoordinates(list: pointer to tCoordinateNode) : integer

var
result : integer;
end var
if list == NULL then
{ Trivial case: empty list }
result := 0;
else if list->next == NULL then
{ Trivial case: end of the list }
result := list.numPersons;
else
{ Recursive call }
result := list.numPersons + numPeopleCoordinates(list->next);
end if
return result;
end function
function numPeopleTime(list: pointer to tDateTimeNode, start: tDateTime,

end: tDateTime) : integer
var
result : integer;
people : integer;
end var
if list == NULL then
{ Trivial case: empty list }
result := 0;
else if datetime_cmp(list->dateTime, end) > 0 then
{ Trivial case: No nodes in the time range}
result := 0;
else if datetime_cmp(list->dateTime, end) = 0 then
{ Trivial case: Last node in the time range}
result := numPeopleCoordinates(list->coordinatesList);
else if datetime_cmp(list->dateTime, start) < 0 then
{ Recursive call: Before start }
result := numPeopleTime(list->next, start, end);
else
{ Recursive call: In the range }
people := numPeopleCoordinates(list->coordinatesList);
result := people + numPeopleTime(list->next, start, end);
end if
return result;
end function

PEC3 20211 Solucion

Cargado por

Copyright:

Formatos disponibles

PEC3 20211 Solucion

Cargado por

Información del documento

Título original

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

PEC3 20211 Solucion

Cargado por

Copyright:

Formatos disponibles

Prácticas de Programación

Formato y fecha de entrega

● Saber interpretar y seguir el código de terceras personas.

PEC 3 – Prácticas de programación 20211 pag 1

Cada ejercicio tiene asociada su puntuación sobre el total de la actividad. Se valorará

Monográfico sobre plagio:

PEC 3 – Prácticas de programación 20211 pag 2

Indica que el código mostrado es en lenguaje algorítmico.

Indica que el código mostrado es en lenguaje C.

Muestra la ejecución de un programa en lenguaje C.

PEC 3 – Prácticas de programación 20211 pag 3

function mystery (n : integer ) : integer

El resultado es 39, que resulta de ejecutar la secuencia de

Mystery(1) Mystery(0) Mystery(1)

PEC 3 – Prácticas de programación 20211 pag 4

Para el análisis de los contactos estrechos, se ha detectado la necesidad de tener

La idea es guardar una lista de momentos de tiempo tDateTime, y para cada

PEC 3 – Prácticas de programación 20211 pag 5

Se pide definir en lenguaje algorítmico las siguientes funciones recursivas:

a) La función numPeopleCoordinates que dado el puntero al primer nodo de una

function numPeopleCoordinates(list: pointer to tCoordinateNode) : integer

b) La función numPeopleTime que dado el puntero al primer nodo de una lista

function numPeopleTime(list: pointer to tDateTimeNode, start: tDateTime,

Para este ejercicio podéis disponer de la función:

function datetime_cmp(dt1: tDateTime, dt2: tDateTime): integer

que dados dos momentos temporales dt1 y dt2, devuelve:

● -1 si dt1 < dt2

PEC 3 – Prácticas de programación 20211 pag 6

function numPeopleCoordinates(list: pointer to tCoordinateNode) : integer

function numPeopleTime(list: pointer to tDateTimeNode, start: tDateTime,

PEC 3 – Prácticas de programación 20211 pag 7

También podría gustarte