main vectores
TRANSCRIPT
.
INF-111
2da Guía de Ejercicios
Ejercicios de Vectores, Matrices y Métodos deOrdenación
También puedes encontrar esta práctica en...
http://es.todo111.wikia.com/wiki/Ejercicios_para_el_Segundo_Parcial
Autores:
Mauricio Alarcónr00t García
D'jalmar GutierrezArun Limachi
Agradecimientos especiales a:
Jhtan Castro
5 de mayo de 2014
Índice
1. Vectores y Matrices 41.1. ½Bienvenido al mundo de los Vectores! . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.1.1. Leyendo vectores (1pt) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41.1.2. Mostrando vectores (1pt) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41.1.3. Leyendo matrices (1pt) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41.1.4. Mostrando matrices (1pt) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41.1.5. Shush repetidos! (3pts) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41.1.6. Conjunto Unión (3pts) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51.1.7. Cacería de Índices (3pts) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51.1.8. La Diagonal (2pts) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51.1.9. Iésimo vector �la (2pts) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61.1.10. Eliminar un elemento sin dejar rastro (3pts) . . . . . . . . . . . . . . . . . . . 61.1.11. Eliminar un vector sin dejar rastro (3pts) . . . . . . . . . . . . . . . . . . . . . 61.1.12. Insertando un elemento (Vector) (2pts) . . . . . . . . . . . . . . . . . . . . . 71.1.13. Insertando un vector (Matriz) (2pts) . . . . . . . . . . . . . . . . . . . . . . . 71.1.14. Agrandando vectores (10pts) . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.2. Problemas sencillos (Ad-Hoc) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81.2.1. La criba de Erastóstenes (10pts) . . . . . . . . . . . . . . . . . . . . . . . . . 81.2.2. y también el �bonacci? (8pts) . . . . . . . . . . . . . . . . . . . . . . . . . . 91.2.3. ¾Rapidez o Memoria? (5pts) . . . . . . . . . . . . . . . . . . . . . . . . . . . 91.2.4. Suma Máxima (5pts) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91.2.5. Sumatoria del rango (5pts) . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91.2.6. Suma de la pequeña Matriz (10pts) . . . . . . . . . . . . . . . . . . . . . . . 101.2.7. Rango con la sumatoria más grande (10pts) . . . . . . . . . . . . . . . . . . . 101.2.8. Submatriz con la suma más grande (10pts) . . . . . . . . . . . . . . . . . . . 101.2.9. Vector de primos (10pts) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101.2.10. ¾Cuántos primos? (10pts) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.3. Dibujando en Matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101.3.1. X (1pt) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111.3.2. Y (2pts) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111.3.3. Tablero de Ajedrez (5pts) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121.3.4. El triángulo de Pascal .(20pts) . . . . . . . . . . . . . . . . . . . . . . . . . . 121.3.5. Rectángulos Concéntricos (5pts) . . . . . . . . . . . . . . . . . . . . . . . . . 131.3.6. Espiral (5pts) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131.3.7. Gusano (5pts) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141.3.8. Gusano Inclinado (10pts) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141.3.9. Diamantes (5pts) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 151.3.10. Triforce (30pts) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161.3.11. I accidentally the whole city! (40pts) . . . . . . . . . . . . . . . . . . . . . . . 17
1.4. Razonamiento y Lógica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 181.4.1. El Teleférico (10pts) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 181.4.2. OVNI (10pts) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 191.4.3. �Estoy a dieta� (20pts) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 201.4.4. Sembrando Semillas Mágicas (l33t h4x0r) . . . . . . . . . . . . . . . . . . . . 211.4.5. Mi amigo superticioso (10pts) . . . . . . . . . . . . . . . . . . . . . . . . . . 22
1
1.4.6. Facebook (l33t h4x0r) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
2. Métodos de Ordenación 262.1. Repaso de Métodos de Ordenación . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
2.1.1. Funcionamiento de Bubble Sort (Método Burbuja) (10pts) . . . . . . . . . . . 262.1.2. Algoritmo de Bubble Sort (10pts) . . . . . . . . . . . . . . . . . . . . . . . . 262.1.3. Desventaja del método burbuja (10pts) . . . . . . . . . . . . . . . . . . . . . 262.1.4. Funcionamiento de Insertion Sort (por inserción) (10pts) . . . . . . . . . . . . 262.1.5. Algoritmo de Insertion Sort (10pts) . . . . . . . . . . . . . . . . . . . . . . . 262.1.6. Desventajas... (10pts) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 262.1.7. El mejor (10pts) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 262.1.8. ¾Por qué es el mejor (20pts) . . . . . . . . . . . . . . . . . . . . . . . . . . . 262.1.9. ¾Cómo funciona? (80pts) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 272.1.10. Ordenando cadenas (30pts) . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
3. Apéndice 273.1. Sobre la criba de Erastóstenes... . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 273.2. Sobre el triángulo de Pascal... . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 283.3. El código Prometido (ordenando caracteres) . . . . . . . . . . . . . . . . . . . . . . . 29
2
README.txt
Esta es la 2da parte, y contiene las secciones: 3.Vectores y Matrices y 4.Métodos de Ordenación.Los ejercicios l33t h4x0r, que pretendían ser una sección extra, están fuscionados con la primera secciónpor falta de tiempo.
La 1ra parte de esta práctica está disponible en la fotocopiadora de estadística y del CEFAC, ycontiene las instrucciones para resolver la práctica, es recomendable leer esas instrucciones antes decomenzar a resolver, de lo contrario trabajarás de más, en vano.
H4PPY C0D1N6
3
1. Vectores y Matrices
1.1. ½Bienvenido al mundo de los Vectores!
1.1.1. Leyendo vectores (1pt)
Haz un módulo que lea varios números, los almacene en un vector, y responda el vector que contienelos n números.
Se te dará un número n, seguido de n números. Debes almacenar los n números en un vector detamaño n, y devolverlo.
1.1.2. Mostrando vectores (1pt)
Haz un módulo que, dado un vector, lo muestre.
1.1.3. Leyendo matrices (1pt)
Haz un módulo que lea varios números, los almacene en un vector, y responda el vector que contienelos n números.
Se te dará un número n que indica las columnas que tu matriz tendrá, y otro número m que indicalas �las que tu matriz debería tener, seguido de n ∗m números. Debes almacenar los n ∗m númerosen una matriz de tamaño nxm, y devolverla.
1.1.4. Mostrando matrices (1pt)
Haz un módulo que, dado una matriz, la muestre.
1.1.5. Shush repetidos! (3pts)
Haz un módulo que, dado un vector X, devuelva un nuevo vector Y con los elementos de X, perosin repetir ninguno.
EJEMPLO:
PARAMETRO
{1, 5, 3, 7, 8, 3, 7, 3, 9, 0, 1, 6, 5}
RESPUESTA
{1, 5, 3, 7, 8, 9, 0, 6}
4
1.1.6. Conjunto Unión (3pts)
Haz un módulo que, dados dos vectores X y Y , devuelva un nuevo vector Z cuyo contenido sea elconjunto resultante de realizar una unión entre X y Y .
Nota: Un conjunto no tiene elementos repetidos
Nota2: Los elementos de los vectores podrían no estar ordenados
EJEMPLO:
PARAMETROS
X = {1, 2, 3, 3, 3, 4, 5, 6, 6, 7}
Y = {1, 2, 3, 9, 0}
RESPUESTA
Z = {1, 2, 3, 4, 5, 6, 7, 9, 0}
1.1.7. Cacería de Índices (3pts)
Haz un módulo que, dado un vector X y un número a, devuelva el índice del primer elemento deX que es igual a a.
NOTA: Debes asumir que el índice del primer elemento de un vector es 0
EJEMPLO:
INPUT
X = {3, 6, 2, 6, 1, 4}; a = 6
OUTPUT
1
1.1.8. La Diagonal (2pts)
Haz un módulo que, dada una matriz cuadrada M , devuelva un vector Z, cuyos elementos seanlos elementos de la diagonal principal de la matriz M .
La diagonal principal de una matriz, son todos aquellos elementos que están dentro de la grandiagonal que comienza en la esquina superior izquierda de la matriz, y termina en la esquina inferiorderecha.
EJEMPLO:
PARAMETROS
M = {{1, 4, 5, 8, 3},
{6, 3, 7, 9, 5},
{4, 7, 7, 4, 8},
{0, 0, 7, 0, 5},
{1, 3, 6, 3, 2}}
RESPUESTA
Z = {1, 3, 7, 0, 2}
5
1.1.9. Iésimo vector �la (2pts)
Haz un módulo que, dada una matriz M , y un número i, devuelva un vector hecho con los elementosde la �la con el índice i de la matriz.
NOTA: La primera �la de la matriz tiene el índice 0
EJEMPLO:
PARAMETROS
M = {{1, 4, 5, 8, 3},
{6, 3, 7, 9, 5},
{4, 7, 7, 4, 8},
{0, 0, 7, 0, 5},
{1, 3, 6, 3, 2}}
3
RESPUESTA
Z = {0, 0, 7, 0, 5}
1.1.10. Eliminar un elemento sin dejar rastro (3pts)
Haz un módulo que, dado un vector V , de tamaño n, y un índice i, elimine el elemento en el índice idel vector V , y recorra todos los elementos que están a la derecha de i, una posición hacia la izquierda.
El módulo debería devolver un nuevo vector X de tamaño n − 1, que es el resultado de habereliminado al elemento con el índice i del vector V .
EJEMPLO:
PARAMETROS
V = {1, 4, 7, 3, 7, 3, 2, 5, 3, 7, 0}
i = 4
RESPUESTA
X = {1, 4, 7, 3, 3, 2, 5, 3, 7, 0}
1.1.11. Eliminar un vector sin dejar rastro (3pts)
Haz un módulo que, dada una matriz M de tamaño nxm, seguida de un índice i, elimine la �lacon índice i de la matriz M .
EJEMPLO:
6
PARAMETROS
M = {{1, 3, 7, 3, 0},
{4, 2, 9, 2, 9}.
{1, 6, 3, 7, 2},
{4, 3, 8, 2, 1}} ;
0
RESPUESTA
M = {{4, 2, 9, 2, 9}.
{1, 6, 3, 7, 2},
{4, 3, 8, 2, 1}}
1.1.12. Insertando un elemento (Vector) (2pts)
Dado un vector V , un índice i y un número n, insertar el número n en el índice i del vector, yrecorrer todos los elementos, desde i en adelante, una posición hacia la izquierda.
EJEMPLO:
PARAMETROS
V = {1, 0, 5, 9, 4, 9, 8}
i = 2
n = 99
RESPUESTA
V = {1, 0, 99, 5, 9, 4, 9, 8}
1.1.13. Insertando un vector (Matriz) (2pts)
Dada una matriz M de tamaño mxn, un índice i, y un vector V de tamaño m, insertar el vector Ven la �la con índice i, y recorrer todas las �las que estén debajo de la iésima �la un lugar hacia abajo.
EJEMPLO:
PARAMETROS
M = {{1, 6, 4, 8},
{5, 7, 9, 0},
{3, 6, 4, 2}}
i = 1
V = {8, 8, 8, 8}
RESPUESTA
X = {{1, 6, 4, 8},
{8, 8, 8, 8},
{5, 7, 9, 0},
{3, 6, 4, 2}}
7
1.1.14. Agrandando vectores (10pts)
C++, Java, y muchos otros lenguajes de programación más, tienen en sus librerías estándar unalibrería que permite crear vectores de tamaño dinámico, es decir, el tamaño puede cambiar a medidaque se vaya necesitando más espacio.
Para conseguir esto, hay que hacer uso de un método conocido como �relocalización de datos�.Consiste en lo siguiente:
Se declara el vector con un tamaño �jo.
Se va llenando el vector con datos.
Cuando ya no hay espacio para más datos, el vector con el que se está trabajando se destruye,pero antes de ser destruido, todos sus datos son copiados a un nuevo vector, cuyo tamaño es elcuadrado del tamaño del vector antiguo.
Se repiten los pasos 2 y 3 cuantas veces sea necesario.
Haz un algoritmo que, dado un vector V , de tamaño n, devuelva un nuevo vector X de tamaño n2.Es evidente que solo las primeras n posiciones del vector X estarán llenas. Debes dejar las siguientesn2 − n posiciones de X intactas.
1.2. Problemas sencillos (Ad-Hoc)
En esta sección encontrarás ejercicios sencillos que se pueden resolver utilizando matrices y vectores.No está destinada para que pienses mucho, la solución es sencilla, solamente para que te familiaricescon el uso de los vectores y las matrices.
1.2.1. La criba de Erastóstenes (10pts)
Haz un módulo que, dado un número n, genere una criba de erastóstenes de tamaño n.
¾no sabes qué es la criba de Erastóstenes? ½lee el apéndice 3.1!
EJEMPLO
INPUT
50
OUTPUT
CRIBA = {F, F, V, V, F,
V, F, V, F, F,
F, V, F, V, F,
F, F, V, F, V,
F, F, F, V, F,
F, F, F, F, V,
F, V, F, F, F,
F, F, V, F, F,
F, V, F, V, F,
F, F, V, F, F}
8
1.2.2. y también el �bonacci? (8pts)
Sí, el algoritmo que conoces para encontrar números �bonaccis también es uno de los más lentos.
Haz un algoritmo que genere un vector de tamaño n que contenga la secuencia de números �bonaccisde forma rápida.
¾por qué el método tradicional es lento? Porque al hacer esto:
a = b
b = f
f = a + b
hacemos, por cada número en la serie �bonacci, 3 operaciones: asignar el valor de b a la variableea; asignar el valor de f a la variable b y asignar el valor de a+ b a f .
En cambio, en un vector: fi = V [i − 1] + V [i − 2], solamente se realiza una operación por cadatérmino de la serie �bonacci.
1.2.3. ¾Rapidez o Memoria? (5pts)
El algoritmo que hiciste para el ejercicio anterior (�y también el �bonacci?�) es más rápido peroocupa más memoria. En tu opinión, ¾cuál algoritmo es mejor? ¾el tradicional? ¾o el que utiliza vectores?
1.2.4. Suma Máxima (5pts)
Te dan un vector V de tamaño n con valores que oscilan entre −106 y 106. Imagina que estosvalores representan dinero, y que tú puedes decidir si tomar o no el valor de cualquier índice i. ¾Cuáles la mayor cantidad de dinero que podrías tomar?
EJEMPLO
PARAMETROS
V = {0, 34, -5, 100, -1000, -1, 3}
n RESPUESTA
137
1.2.5. Sumatoria del rango (5pts)
Dado un vector V de tamaño n, y dos números i < n y j < n. ¾Cuál es el resultado de sumarV [i] + V [i+ 1] + ...+ V [j]?
9
1.2.6. Suma de la pequeña Matriz (10pts)
Dada una matriz M , y dos pares de números: i, j, k y l, ¾cuál es la suma de la sub matriz quecomienza en Mi,j y que termina en Mk,l?
1.2.7. Rango con la sumatoria más grande (10pts)
Dado un vector V de tamaño n, encuentra los dos números i y j cuya sumatoria sea la más grande.
1.2.8. Submatriz con la suma más grande (10pts)
Dada una matriz M cuadrada, de tamaño nxn, cuyos números oscilan entre −106 y 106, encuentralos 4 números i, j, k, l, tal que la suma de todos los elementos de la submatriz que comienza en Mi,j
y termina en Mk,l, es más grande que la suma de cualquier otra submatriz.
1.2.9. Vector de primos (10pts)
Dado un vector V de tamaño 1 ≤ n ≤ 1000, cuyos valores oscilan entre 0 y 100, devolver otrovector X, que contenga todos los elementos primos de V .
Utiliza la Criba de Erastóstenes para resolver este problema
EJEMPLO
PARAMETROS
V = {3, 6, 8, 7, 9, 13, 7, 15, 6}
RESPUESTA
X = {3, 7, 13, 7}
1.2.10. ¾Cuántos primos? (10pts)
Dados dos números a y b, ¾Cuántos primos hay en el rango [a, b]?
Utiliza la Criba de Erastóstenes para resolver este problema
1.3. Dibujando en Matrices
Muchos de los ejercicios (si no son todos) que te plantearán en clases consisten en dibujar patronesen una matriz. La siguiente sección contiene ejercicios en los que deberás dibujar matrices con patrones.
10
1.3.1. X (1pt)
Haz un algoritmo que, dado un número n, genere una matriz cuadrada de tamaño n con una granX dibujada en su centro.
EJEMPLO
INPUT
5
6
OUTPUT
1 0 0 0 1
0 1 0 1 0
0 0 1 0 0
0 1 0 1 0
1 0 0 0 1
1 0 0 0 0 1
0 1 0 0 1 0
0 0 1 1 0 0
0 0 1 1 0 0
0 1 0 0 1 0
1 0 0 0 0 1
1.3.2. Y (2pts)
Dado un número n, dibuja una matriz cuadrada, de tamaño n× n, con una gran Y dibujada en elmedio.
EJEMPLO
INPUT
5
6
OUTPUT
1 0 0 0 1
0 1 0 1 0
0 0 1 0 0
0 0 1 0 0
0 0 1 0 0
1 0 0 0 0 1
0 1 0 0 1 0
0 0 1 1 0 0
0 0 1 1 0 0
0 0 1 1 0 0
0 0 1 1 0 0
11
1.3.3. Tablero de Ajedrez (5pts)
Dado un número n, generar una matriz M de tamaño n×n con el patrón de un tablero de ajedrez,representando el blanco con una 'O', y el negro con una 'X'
EJEMPLO
INPUT
5 7
OUTPUT
O X O X O X O
X O X O X O X
O X O X O X O
X O X O X O X
O X O X O X O
1.3.4. El triángulo de Pascal .(20pts)
Haz un algoritmo que, dado un número n, genere un triángulo de pascal con n niveles.
Si no sabes qué es un triángulo de pascal, te recomiendo que leas el apéndice 3.2.
EJEMPLO
INPUT
8
OUTPUT
0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0
0 0 0 0 0 0 1 0 2 0 1 0 0 0 0 0 0
0 0 0 0 0 1 0 3 0 3 0 1 0 0 0 0 0
0 0 0 0 1 0 4 0 6 0 4 0 1 0 0 0 0
0 0 0 1 0 5 0 10 0 10 0 5 0 1 0 0 0
0 0 1 0 6 0 15 0 20 0 15 0 6 0 1 0 0
0 1 0 7 0 21 0 35 0 35 0 21 0 7 0 1 0
1 0 8 0 28 0 56 0 70 0 56 0 28 0 8 0 1
12
1.3.5. Rectángulos Concéntricos (5pts)
Haz un algoritmo que, dado un número n y otro número m, dibuje una matriz de tamaño n ×mhecha de caracteres, que contenga rectángulos concéntricos, alternando los caracteres �X� y �O� entrerectángulos vecinos.
EJEMPLO:
INPUT
10, 5
OTPUT
X X X X X X X X X X
X O O O O O O O O X
X O X X X X X X O X
X O O O O O O O O X
X X X X X X X X X X
1.3.6. Espiral (5pts)
Haz un algoritmo que, dados dos números n y m, dibuje una matriz de n×m, con la secuencia denúmeros naturales.
EJEMPLO:
INPUT
4, 5
OUTPUT
1 2 3 4
14 15 16 5
13 20 17 6
12 19 18 7
11 10 9 8
13
1.3.7. Gusano (5pts)
Haz un algoritmo que, dado un número n y otro número m, dibuje un gusanito con la secuencia denúmeros naturales, dentro de una matriz de n×m.
EJEMPLO
INPUT
4 5
OUTPUT
1 2 3 4
8 7 6 5
9 10 11 12
16 15 14 13
17 18 19 20
1.3.8. Gusano Inclinado (10pts)
Haz un algoritmo que, dados dos números n y m, dibuje un gusanito inclinado con la secuencia denúmeros naturales, dentro de una matriz M de n×m.
Para dibujar el gusano inclinado dentro de la matriz, debes poner los números de la secuencia denúmeros naturales, en la matriz M , en el orden en el que el gusanito de la imagen toca los cuadrados.
14
EJEMPLO
INPUT
4 5
OUTPUT
1 2 6 7
3 5 8 14
4 9 13 15
10 12 16 19
11 17 18 20
1.3.9. Diamantes (5pts)
Dado un número n, dibuja un diamante dentro de una matriz de caracteres M de tamaño n × n.El diamante debe estar formado por el caracter �X�, y los espacios en blanco, con caracteres �O�.
INPUT
5
6
OUTPUT
O O X O O
O X X X O
X X X X X
O X X X O
O O X O O
O O X X O O
O X X X X O
X X X X X X
X X X X X X
O X X X X O
O O X X O O
NOTA: En caso de que el número sea par, los �picos� del diamante, deberían ser dos �X�s.
15
1.3.10. Triforce (30pts)
1
¾Jugaste Zelda? Link (el personaje principal) está en búsqueda de la mística Trifuerza.
Una trifuerza son tres triángulos equiláteros del mismo tamaño, repartidos de tal forma que, formanun tríangulo invertido en el centro (como se muestra en la imagen).
2
Haz un algoritmo que, dado un número n, dibuje una trifuerza, cuyos triángulos tengan la�altura� de n caracteres. Utiliza la �X� para dibujar los triángulos, y la �O� para representarespacios vacíos.
EJEMPLO:
INPUT
3
5
OUTPUT
O O O O O X O O O O O
O O O O X X X O O O O
O O O X X X X X O O O
O O X O O O O O X O O
O X X X O O O X X X O
X X X X X O X X X X X
OJO: los tres triángulos formados con las �X�s, tienen una altura de 3 �las.
1newfags can't...2Ten el Valor para buscar la Sabiduría que te concederá el Poder
16
1.3.11. I accidentally the whole city! (40pts)
½Ocurrió un accidente nuclear en una ciudad cuadrada! tenían garrafas de uranio en ciertos lugaresde la ciudad, y accidentalmente todas estallaron al mismo tiempo...
El equipo de bomberos ha decidido representar la ciudad como una matriz cuadrada, y tiene en subase de datos n tricas de números, que representan las coordenadas donde había una garrafa de uranio,y la cantidad de uranio almacenada en ese lugar.
El equipo de bomberos necesita saber qué lugares de la ciudad están irradiados3. Para ello, te hanenviado documentos ultrasecretos en los que te explican cómo funciona la radiación que despide unagarrafa de uranio al estallar:
La radiación que queda luego de estallar una garrafa con n kilos de uranio es un diamante cuadradode 2n+ 1 kilómetros de altura y anchura, cuyo centro es la zona en la que se encontraba la garrafa deuranio.
Imagina que la ciudad mide 5 × 5 kilómetros, y está representada por una matriz C, justo en elcentro (en C2,2 había una garrafa de uranio que pesaba 1 kilo. La zona irradiada, se representa con�X�s, y las zonas no afectadas con �O�s:
O O O O O
O O X O O
O X X X O
O O X O O
O O O O O
Se te dará un número entero l, que indica el alto y ancho (en kilómetros) de la ciudad. A contin-uación, se te dará un número n, seguido de n tricas de números, que representan: la �la y la columnaen la que se encontraba la garrafa, y la cantidad de uranio (en kilogramos) que había en la garrafa.
Debes imprimir un �mapa� de los lugares irradiados en la ciudad. El mapa consiste en una matrizde tamaño l× l, en la que cada cuadrito representa un kilómetro cuadrado de la ciudad. Los cuadritosque contengan una �X� son zonas irradiadas, y los cuadritos que contengan una �O�, representan zonasno afectadas.
3½No olvides que el Uranio es radioactivo!
17
EJEMPLO
10
4
0 0 5
9 9 2
5 5 2
7 4 3
X X X X X X O O O O
X X X X X O O X O O
X X X X O O X X X O
X X X O O X X X X X
X X X O X X X X X X
X X O X X X X X X X
X O O O X X X X X O
O O O O O X O X O X
O O O O O O O O X X
O O O O O O O X X X
1.4. Razonamiento y Lógica
Esta sección consiste en ejercicios que te harán pensar. Todos se resuelven utilizando vectores omatrices. Aquí encontrarás los primeros problemas l33t h4x0r!
ADVERTENCIA: Algunos de estos ejercicios podrían necesitar métodos de ordenación... los ejerci-cios l33t h4x0r podrían (deberían?) necesitar �algo más�
1.4.1. El Teleférico (10pts)
Se te dará un vector V de tamaño n que representa una super�cie. Cada dato de V , representa laaltura de la super�cie en ese punto, como en la imagen
18
Tu deber es indicar de qué punto a qué punto se podría construir el teleférico que abarque másextensión de terreno en el eje x. Ten en cuenta que no puedes construir un teleférico de un punto aotro, si existe algún punto de la super�cie que �choque� con su ruta.
NOTA: debes asumir que ∀i < n, se cumple que la distancia en el eje x entre Vi y Vi+1 es siemprela misma.
NOTA2: La respuesta al ejemplo del grá�co es: desde 1 hasta 6. Porque es el teleférico más largo(en extensión en eje x) que se puede formar
1.4.2. OVNI (10pts)
Con el mismo método que se utilizó en el problema 1.4.1, un extraterrestre te dará un vector O detamaño n, que representa la super�cie inferior de su nave espacial.
A continuación, te dará un vector T , que representa la super�cie superior del terreno en el quequiere aterrizar.
Debes indicarle al extraterrestre en qué punto del terreno puede aterrizar, indicándole el índice delvector terreno T en el que el primer índice del vector O tendría que posarse para que toda su navepueda aterrizar.
Ten en cuenta que el ovni puede aterrizar en un lugar, si y solo si, la �gura que forma la super�cieinferior de su nave �encaja� a la perfección con la super�cie en la que se posará. (como en la imagen).
19
NOTA: debes asumir que ∀i < n, se cumple que la distancia en el eje x entre Vi y Vi+1 es siemprela misma.
1.4.3. �Estoy a dieta� (20pts)
Harris Pilton está a dieta porque quiere participar en el concurso de belleza Las Anoréxicas másEsbeltas de Azeroth. Para participar en este concurso, el requisito principal, es pesar menos de n gramos.
A Harris Pilton le encantan los chocolates! pero cada vez que come un chocolate, su peso aumentala misma cantidad que el peso del chocolate. Su novio, Arthas le ha regalado una cajita de chocolates.
Harris Pilton quiere comer la mayor cantidad de chocolates posibles, pero que aún pueda participaren Las Anoréxicas más Esbeltas de Azeroth. Como nunca fue buena en matemática ni en razonamiento,no sabe qué chocolates comer, así que te ha pedido ayuda a tí, con la promesa de que, si la ayudas, teregalará un [agujero portable] ([Portable Hole])!
¾Le ayudas?
Se te dará un vector V , donde V [i] indica el peso en gramos del iésimo chocolate de la caja, acontinuación, se te dará un número n, que indica el peso máximo que pueden tener las postulantes alconcurso de belleza, y por último, un número p, que indica el peso actual de Harris Pilton.
Debes mostrar una serie de números, que indican la posición en la cajita de los chocolates queHarris Pilton va a comer. Ten en cuenta que el peso de Harris Pilton, después de comer los chocolates,no debe exceder n gramos.
EJEMPLO
20
PARAMETROS
indice: 0 1 2 3 4 5 6 7 8 9 10 11
V = {1 10 4 3 7 1 5 3 2 7 3 1}
n = 100
p = 90
RESPUESTA
0 5 11 8 7
NOTA: el orden en el que muestres la posición de los chocolates es irrelevante
1.4.4. Sembrando Semillas Mágicas (l33t h4x0r)
NOTA: Este problema ha sido adaptado de [MISSING]
Un cientí�co loco boliviano ha descubierto unas semillas mágicas que quitan el hambre! Las semillasson muy caprichosas, y para que crescan correctamente, tienen que crecer en el centro de La Paz, ynecesitan que el terreno cumpla con todos estos requisitos:
en toda la �la superior, no debe haber ninguna semilla.
en toda la �la inferior, tampoco debe haber ninguna semilla.
en la celda que está a su derecha, tampoco deben haber semillas.
en la celda que está a su izquierda, tampoco deben haber semillas.
Si estas 4 condiciones se cumplen, la semilla crecerá, de lo contrario, simplemente morirá.
21
El cientí�co ha estudiado el terreno, y tiene una matriz T de n×m llena con números que indicacuánto dinero va a ganar si siembra una semilla en ese lugar ADVERTENCIA: el número puede sernegativo, es decir, el cientí�co puede perder dinero al sembrar una semilla en esa posición!.
El cientí�co quiere saber cuál es la cantidad máxima de dinero que puede ganar, si decide utilizarese terreno para sembrar sus semillas. ¾le ayudas?
Se te dará un número n y otro número m, que indican la cantidad de �las y columnas que tiene lamatriz T , respectivamente.
A continuación, se te darán n �las, cada una con m números separados entre sí con un espacio,que indican la ganancia estudiada por el cientí�co, representada por la matriz M .
Debes indicar un número g que indica la ganancia máxima que el cientí�co podría obtener al sembrarsus semillas en ese terreno.
EJEMPLO
INPUT
5 7
2 5 6 7 5 4 7
1 2 7 0 8 6 -1
3 87 -3 4 -4 7 10
-87 1 3 65 3 7 2
-1 -3 -6 -8 -5 -3 1
OUTPUT
114
1.4.5. Mi amigo superticioso (10pts)
Mi amigo es muy superticioso, y cree que pisar las rallas del piso es mala suerte.
Me dijo que ha registrado en un vector el largo de las baldozas que hay desde mi casa hasta su casa,así que, si le digo cuál es la longitud de mi paso, él me va a decir cuántas rayas he pisado solo por ir avisitarlo.
Él cree que, diciéndome esto, hará que yo recapacite y deje de pisar las rallas del piso tan despre-ocupadamente.
Yo no creo en esas superticiones, pero me intriga saber cómo hizo un algoritmo capaz de encontrartal respuesta... ¾puedes hacer un algoritmo que haga lo mismo?
Se te dará un número p que representa la longitud de mi paso, seguido de un número n que indicala cantidad de baldozas que hay en el camino.
A continuación, se te darán n números, que indican las medidas de las n baldozas que hay en elcamino, ordenadas, de derecha a izquierda, según su aparición.
EJEMPLO
22
En el grá�co, es como si hubiera puesto tinta en mis zapatos. Mi longitud de paso es de 2, y lamedida de las baldozas está escrita debajo de cada baldoza. Con estas especi�caciones, pisaría 3 vecesraya.
PARAMETROS
p = 2
n = 7
2 4 1 2 1 1 1
RESPUESTA
3
1.4.6. Facebook (l33t h4x0r)
La persona a se ha enterado de un chisme! y se lo va a contar a todas las personas con las quehabitualmente habla. Todas estas personas, a su vez, se lo contarán a todas las personas con las quesuelen hablar.
Hay una persona b que no tiene que enterarse! pero con toda esa maraña de conexiones sociales, esdifícil predecir lo que pasará...
¾Se enterará la persona b?
Cada persona está identi�cada por un caracter. Una cadena de texto, representa lo siguiente:
El primer caracter (x) de la cadena, es una persona.
Todos los siguientes caracteres de la cadena, representan las personas con las que x suele hablar.
23
Se te dará un número n, que indica la cantidad de personas que debes considerar. Luego, se tedarán n cadenas de texto, que representan las relaciones de las n personas.
A continuación, se te dará un caracter a, que indica la persona que comienza el chisme, seguido deun caracter b.
Debes imprimir �OH NOES!� si la persona b se entera del chisme, y �KTHXBYE!� si la persona bno se entera del chisme.
EJEMPLO
INPUT:
6
adb
bcfe
cb
daf
eb
a
c
OUTPUT:
OH NOES!
en el ejemplo anterior, 'a' comienza el chisme, luego, 'a' le dice a 'b' y a 'd', y 'b' le dice a 'c', quees la persona que no debería enterarse del chisme.
OTRO EJEMPLO
24
INPUT:
6
abd
bade
ce
dabf
ebc
fd
a
c
OUTPUT
OH NOES!
En el ejemplo anterior, 'a' le dice a 'b', y 'b' le dice a 'a', y 'a' le dice a 'b' (...) 4 'b' le dice a 'e', y'e' le cuenta a 'c', que es la persona que no debería enterarse.
ÚLTIMO EJEMPLO
INPUT
6
abd
ba
cef
da
efc
fec
a
c
OUTPUT
KTHXBYE!
No hay forma de que 'c' se entere del chisme.
4looping forever and ever? cuidado con los ciclos in�nitos, necesitas llevar un �registro� de las conversaciones que ya
haz considerado para no enciclarte ;D�
25
2. Métodos de Ordenación
2.1. Repaso de Métodos de Ordenación
En esta sección, demostrarás que entiendes los métodos de ordenación más sencillos de entender.
2.1.1. Funcionamiento de Bubble Sort (Método Burbuja) (10pts)
Explica en palabras... ¾cómo funciona el método burbuja?
2.1.2. Algoritmo de Bubble Sort (10pts)
Dado un vector V , de n datos, haz un algoritmo para ordenarlo ascendentemente, mediante elmétodo burbuja.
2.1.3. Desventaja del método burbuja (10pts)
¾Qué desventaja puedes ver en el método burbuja?
2.1.4. Funcionamiento de Insertion Sort (por inserción) (10pts)
Explica con tus propias palabras cómo funciona el insertion sort.
2.1.5. Algoritmo de Insertion Sort (10pts)
Dado un vector V , con n elementos, ordénalo ascendentemente, utilizando el Insertion Sort.
2.1.6. Desventajas... (10pts)
Investiga: ¾Qué desventaja le ves al insertion sort?
2.1.7. El mejor (10pts)
Investiga: ¾Cuál es/son el/los mejor/es método/s de ordenación?
2.1.8. ¾Por qué es el mejor (20pts)
¾Por qué?
26
2.1.9. ¾Cómo funciona? (80pts)
Explica con tus palabras cómo funciona el mejor algoritmo de ordenación
Haz un algoritmo que, dado un vector V de n datos, lo ordene mediante el mejor algoritmo deordenación.
2.1.10. Ordenando cadenas (30pts)
Haz un algoritmo que, dada una cadena C, devuelva una cadena D, que contenga todos los carac-teres de C, pero ordenados.
3. Apéndice
3.1. Sobre la criba de Erastóstenes...
¾Cómo encuentras números primos? tomas un número y veri�cas, uno a uno, si el número es divisibleentre cualquier otro número que no sea él mismo o uno.
Esta forma de encontrar primos es una de las más ine�cientes de encontrar primos. Existe una formamejor, mediante la criba de Erastóstenes, en este método, en vez de enfocarnos en un solo número,encontramos todos los primos dentro de un rango.
Sin embargo, para recordar todos estos primos, necesitamos guardarlos en algún lugar: un vector.
Así que la criba de Erastóstenes se guarda en un vector de booleanos, en el que, si el lugar con elíndice i es verdadero, entonces el número i es primo; si el lugar con el índice i es falso, entonces elnúmero i es falso.
Construyendo la criba
Inicializas el vector de booleanos a un tamaño n + 1 (vector con índice basado en 0). Tachas el 1(E[1] = false), porque es un caso especial y no es primo. (También tachas el 0)
i: 0 1 2 3 4 5 6 7 8 9 10 11 12 13
E = {F, F, V, V, V, V, V, V, V, V, V, V, V, V}
Comienzas con el 2, no lo tachas pero tachas a todos sus múltiplos (4, 6, 8, ...) hasta que se acabeel vector.
i: 0 1 2 3 4 5 6 7 8 9 10 11 12 13
E = {F, F, V, V, F, V, F, V, F, V, F, V, F, V}
Partiendo del 2, buscas al siguiente número que no esté tachado (será el 3). No tachas al 3, perotachas a todos sus múltiplos
i: 0 1 2 3 4 5 6 7 8 9 10 11 12 13
E = {F, F, V, V, F, V, F, V, F, F, F, V, F, V}
27
Partiendo del 3, buscas al siguiente número que no esté tachado (será el 5). No tachas al 5, perotachas a todos sus múltiplos.
i: 0 1 2 3 4 5 6 7 8 9 10 11 12 13
E = {F, F, V, V, F, V, F, V, F, F, F, V, F, V}
Si te das cuenta, al enfocarnos en el 5 ya no tachamos nada. La raíz cuadrada de 13 es aproximada-mente 3. Y está demostrado que, después del 3, al seguir repitiendo el procedimiento, ningún númerotachará nada.
En este punto, en el vector booleano, todos los índices de E que están en verdadero son númerosprimos, y podría decirse que:
a es primo <=> E[a] = V erdadero
El algoritmo se reduce a lo siguiente:
Inicializas un vector de booleanos E de tamaño n.
Tachas el 1 y el 0 (caso especial).
Buscas la siguiente posición x que no esté tachada.
No tachas a x, pero sí al resto de sus múltiplos.
Buscas la siguiente posición y que no esté tachada.
Es y >sqrtn? Entonces la criba está completa! : de lo contrario, repetir repetir con y en vez dex desde el paso 4.
3.2. Sobre el triángulo de Pascal...
El triángulo de pascal es un tríangulo que comienza con tres unos:
0 1
1 1 1
La siguiente línea se genera de la siguiente forma: el 1er y último número son unos. El 2do número,se genera sumando a los dos números que están arriba de él:
0 1
1 1 1
2 1 2 1
Las siguientes líneas también se generan de la misma forma:
0 1
1 1 1
2 1 2 1
3 1 3 3 1
4 1 4 6 4 1
Esta última, es un triángulo de pascal de 4 niveles.
28
3.3. El código Prometido (ordenando caracteres)
En la 1ra parte de la guía de ejercicios, faltaba una porción de código en la que se muestre cómoordenar los caracteres de una cadena de texto en Java utilizando la librería estándar.
He aquí el código prometido... el poder está en tus manos! úsalo con prudencia... y no olvides quees muy importante entender cómo funcionan los métodos de ordenación, porque habrán problemas máscomplicados, que requerirán que tú entiendas estos principios!
import java.util.Arrays;
public class Sorting {
public static void main(String [] args) {
String x = "FIRST SOLVE THE PROBLEM! THEN WRITE THE CODE!! :P";
char[] y = x.toCharArray ();
Arrays.sort(y);
x = String.copyValueOf(y);
System.out.println(x);
}
}
29