Algoritmos y Programación (BPTSP05)

[pic 1]

Universidad Metropolitana

Facultad de Ingeniería

Departamento de Gestión de Proyectos y Sistemas

Algoritmos y Programación (BPTSP05)

Parcial I

Pregunta 1 (5 ptos):

Se le da una lista de números enteros no negativos. Deberá realizar una función que:

• Elegir un entero positivo `x` tal que, `x` sea menor o igual que el elemento distinto de cero más pequeño en `nums`.
• Restar `x` de cada elemento positivo en `nums`.
• Devolver el número mínimo de operaciones para hacer que cada elemento en `nums` sea igual a 0.

Input: `nums = [1,5,0,3,5]`

Output: 3

Explicación:

• En la primera operación, elige `x = 1`. Ahora, `nums = [0,4,0,2,4]`.
• En la segunda operación, elige `x = 2`. Ahora, `nums = [0,2,0,0,2]`.
• En la tercera operación, elige `x = 2`. Ahora, `nums = [0,0,0,0,0]`.

Pregunta 2 (5 puntos)

        Se nos da una lista nums de enteros que representa una lista encriptada con "saman encoding". En esta lista la primera mitad de elementos (desde el índice 0 hasta el índice (n/2)-1) representan valores, y la segunda mitad (desde n/2 hasta el último indice) representan frecuencias.

Considere cada par de elementos [val, freq] = [nums[i], nums[i+n/2]] (con i >= 0, i < n/2 y n = tamaño de la lista).

Para cada uno de estos pares, existen freq elementos con valor val concatenados en una sublista Concatena todas las sublistas de izquierda a derecha para generar la lista descomprimida. Devuelva la lista descomprimida.

• Input: nums = [1,2,3,4]
• Ouput: [1,1,1,2,2,2,2]
• Explicación: 

El primer par [1,3] significa que tenemos val = 1 y freq = 3 así que generamos la matriz [1,1,1].

El segundo par [2,4] significa que tenemos val = 2 y freq = 4 así que generamos [2,2,2,2].

Al final la concatenación [1,1,1] + [2,2,2,2] es [1,1,1,2,2,2,2].

Pregunta 3: (5 puntos)

Dada tres listas de números de tamaño n con elementos de la forma `[x1,x2,...,xn], [y1,y2,...,yn] y [z1,z2,…,zn]`

Realice una función que regrese una lista organizada de la siguiente forma. `[x1,y1,z1,x2,y2,z2,...,xn,yn,zn]`

Input: x = [2,5,1] y = [3,4,7], z = [2,0,4] n = 3

Output: [2,3,2,5,4,0,1,7,4]

Input: x = [1,2,3,4], y =[4,3,2,1], z =[5,6,7,8] n = 4

Output: [1,4,5,2,3,6,3,2,7,4,1,8]

Input: x = [1,1] y = [2,2] z =[3,3] n = 2

Output: [1,2,3,1,2,3]

Pregunta 4 (5 puntos)

Dado un arreglo de enteros nums de 2n enteros, agrupe estos enteros en n pares (a1, b1), (a2, b2), ..., (an, bn) de tal forma que la suma de max(ai, bi) para todos sea mínima. Devuelve la suma minimizada.

• Input: nums = [1,4,3,2]
• OuTput: 4
• Explicación: 

Todas las posibles emparejamientos (ignorando el orden de los elementos) son:

1. (1, 4), (2, 3) -> max(1, 4) + max(2, 3) = 4 + 3 = 7
2. (1, 3), (2, 4) -> max(1, 3) + max(2, 4) = 3 + 4 = 7
3. (1, 2), (3, 4) -> max(1, 2) + max(3, 4) = 2 + 4 = 6

Entonces la suma mínima posible es 6.

...