Examen de Prácticas de programación UOC 2021 · Prueba de síntesis enero 2021

Partiendo del modelo de datos de la gestión de espacios de trabajo compartido (coworking), se definen las siguientes constantes y tipos:

const

MAX_ANNEXES: integer:= 3;

end const

type

tPartner = record

id: integer;

name: string;

discount: integer;

end record

tContractAnnex = record

idWorkSpace: integer;

price: real;

end record

tContract = record

idPartner: integer;

month: integer;

year: integer;

annexesSet: vector[MAX_ANNEXES] of tContractAnnex;

numAnnex: integer;

end record

tCoworking = record

partnersSet: pointer to tPartner;

numPartners: integer;

contractsSet: pointer to tContract;

numContracts: integer;

end record

end type

Se plantea la especificación de la siguiente función:

function top_clients (c: tCoworking; x: integer): integer

Dicha función computa y retorna la cantidad de socios ( partners) que cuentan con más de $x$ contratos que posean el número máximo permitido de anexos.

a. Indica las precondiciones formales requeridas por la función top_clients considerando que la empresa dispone como mínimo de un socio y que el valor de $x$ es estrictamente mayor que cero. Justifica la formulación en una o dos líneas.

Partiendo del modelo de datos de la gestión de espacios de trabajo compartido (coworking), se definen las siguientes constantes y tipos:

const

MAX_ANNEXES: integer:= 3;

end const

type

tPartner = record

id: integer;

name: string;

discount: integer;

end record

tContractAnnex = record

idWorkSpace: integer;

price: real;

end record

tContract = record

idPartner: integer;

month: integer;

year: integer;

annexesSet: vector[MAX_ANNEXES] of tContractAnnex;

numAnnex: integer;

end record

tCoworking = record

partnersSet: pointer to tPartner;

numPartners: integer;

contractsSet: pointer to tContract;

numContracts: integer;

end record

end type

Se plantea la especificación de la siguiente función:

function top_clients (c: tCoworking; x: integer): integer

Dicha función computa y retorna la cantidad de socios ( partners) que cuentan con más de $x$ contratos que posean el número máximo permitido de anexos.

b. Implementa la función top_clients en pseudocódigo o lenguaje algorítmico empleando descomposición modular mediante diseño descendente. Implementa asimismo cada una de las funciones auxiliares de los diferentes niveles, acompañándolas de una breve explicación de una o dos líneas indicando su cometido.

Se facilita la siguiente función recursiva desarrollada en lenguaje C:

#define MAX 42

int guess(int v[MAX], int p, int d)

{

int result;

assert(0 <= p && p < MAX && d > 0);

if (p == 0) {

if (v[0] % d == 0) result = 1; // (1)

else result = 0; // (2)

} else { // (3)

result = guess(v, p-1, d); // (4)

if (v[p] % d == 0) result++; // (5)

} // (6)

return result; // (7)

}

a.

Determina y explica qué modalidades o tipologías de recursividad exhibe este algoritmo.

b.

Explica el comportamiento semántico de la función guess (qué calcula). Detalla además la traza paso a paso empleando un diagrama o esquema de pila/cajas para la llamada:

int test;

test = guess({2, 6, 7, 9}, 3, 3);

Se facilita la siguiente función recursiva desarrollada en lenguaje C:

#define MAX 42

int guess(int v[MAX], int p, int d)

{

int result;

assert(0 <= p && p < MAX && d > 0);

if (p == 0) {

if (v[0] % d == 0) result = 1; // (1)

else result = 0; // (2)

} else { // (3)

result = guess(v, p-1, d); // (4)

if (v[p] % d == 0) result++; // (5)

} // (6)

return result; // (7)

}

c.

Implementa una versión iterativa equivalente en lenguaje C y justifica por escrito el diseño adoptado.

int guess_iterative(int v[MAX], int p, int d)

Se facilita la siguiente función recursiva desarrollada en lenguaje C:

#define MAX 42

int guess(int v[MAX], int p, int d)

{

int result;

assert(0 <= p && p < MAX && d > 0);

if (p == 0) {

if (v[0] % d == 0) result = 1; // (1)

else result = 0; // (2)

} else { // (3)

result = guess(v, p-1, d); // (4)

if (v[p] % d == 0) result++; // (5)

} // (6)

return result; // (7)

}

d.

Calcula y argumenta la complejidad asintótica temporal del algoritmo original en su formato recursivo.

e.

Frente a una propuesta alternativa para el método guess con un orden de complejidad casi-lineal ($O(n \log n)$), razona en 4 o 5 líneas si convendría adoptar dicha propuesta.