Problemas sobre estructuras de datosproblem-g.estad.ucm.es/FLOP/pdf/cs1_4.pdf · A. Traspuesta de una matriz 2 B. Cuadrado latino 3 C. Centro de un vector 4 D. Criterios de divisibilidad

Problemas sobre estructuras de datos(Desde trivial hasta muy difıcil)

15 de diciembre de 2008

IndiceA. Traspuesta de una matriz 2

B. Cuadrado latino 3

C. Centro de un vector 4

D. Criterios de divisibilidad 5

E. Tres en raya 7

F. Raıces complejas 8

G. Multiplica matrices 9

H. Derivada de un polinomio 10

I. Punto de silla 11

J. El solitario de los 15 12

K. La distancia mas corta: el algoritmo de Floyd-Warshall 14

L. Diferencias finitas 16

M. Multiplica polinomios 18

N. Determinante 19

N. Ordenacion por seleccion 20

O. Liga de futbol 21

P. Sopa de letras 22

Q. Traductor Morse 23

R. El juego de la vida 24

S. Lights out 26

T. Cuadrdados magicos 28

U. Implementacion de numeros grandes 29

V. Palındromos 30

W. Baldosas de jardın 31

Esta coleccion se ha desarrollado con la financiacion de la Universidad Complutense de Madrid,dentro del proyecto “Laboratorio virtual de programacion sin fronteras” (2008-33).

Se encuentra libremente disponible, y esta incluida en el laboratorio de programacion JOLmes(http://problem-g.estad.ucm.es/JOLmes/), junto con otras colecciones de problemas.

http://problem-g.estad.ucm.es/JOLmes/�

Problema ATraspuesta de una matriz

*.{pas,cpp,java}

Escriba un programa que permita calcular la traspuesta de una matriz cuadrada.

Descripcion de la entrada

La entrada esta formada por la dimension de la matriz, y las n2 entradas de la matriz, ordenadaspor filas y columnas.

Descripcion de la salida

La salida consiste en la traspuesta de la matriz introducida.

Ejemplo de entrada31 2 34 5 67 8 9

Salida para el ejemplo de entrada1 4 72 5 83 6 9

2

Problema BCuadrado latino*.{pas,cpp,java}

Un cuadrado latino de orden n es una tabla de numeros tales que La primera fila de la sucecio esla sucesion 1 2 3 ... n. Una fila cualquiera se obtiene a partir de la fila anterior, rotando una posicionhacia la derecha. Escribe un programa que lea el orden del cuadrado y lo escriba.


La entrada esta formada por el orden del cuadrado n.


La salida consiste en el cuadrado latino correspondiente.

Ejemplo de entrada4

Salida para el ejemplo de entrada1 2 3 44 1 2 33 4 1 22 3 4 1

3

Problema CCuadrado de un vector

*.{pas,cpp,java}

Consideremos un vector V = (v0, v1, ...,n ) con valores reales. Definimos el centro c del vector Vcomo el ındice entre 0 y n que verifica

c·v0 + (c− 1)·v1 + .... + i·vi = 1·vc+1 + 2·vc+2 + .... + (n− c)·vn

Esta propiedad no siempre se verifica. En ese caso, decimos que el vector no tiene centro. Escribe unprograma que dado un vector nos devuelva dos valores: el primero indica si existe el centro del vector,y el segundo, el ındice en el que se encuentra en caso de existir.

Ejemplo: Consideremos el vector (6, 2, 3, 0, 1) con ındices entre 0 y 4. En este caso, el centro delvector es el ındice 1, ya que 1·6 = 1·3 + 2·0 + 3·1. Por el contrario, el vector (1, 2, 1, 1) no tienecentro.


La entrada esta formada por las componentes del vector.


La salida en una respuesta booleana (TRUE/FALSE) y, en caso de que exista el centro, el ındicecorrespondiente.

Ejemplo de entrada6 2 3 0 1

Salida para el ejemplo de entradaTRUE 1

4

Problema DCriterios de divisibilidad

*.{pas,cpp,java}

Desde la antiguedad se conocen reglas que permiten saber si un numero es divisible por otrosimplemente con la inspeccion de las cifras que componen dicho numero. Quizas la mas famosa es laregla del 9, que dice que un numero es multiplo de 9 si y solo si la suma de sus dıgitos es tambienmultiplo de 9. De esta forma podemos saber con facilidad y rapidez si un numero grande es multiplo de9; por ejemplo, 8294527125 sı lo es, ya que la suma de sus cifras es 8+2+9+4+5+2+7+1+2+5=45y 4+5=9, que obviamente es multiplo de 9.

Blaise Pascal (1623–1662) se intereso por estos temas y encontro una generalizacion a la regla del9, que solo requiere sumar las cifras que componen el numero; en el caso general, para comprobarsi un numero n es multiplo de k, no basta con sumar las cifras que componen el numero n, sinoque antes hemos de multiplicar dichas cifras por coeficientes apropiados, que previamente se hancalculado segun el numero k. Por ejemplo, los coeficientes para comprobar si cierto numero es multiplode 7 son (5, 4, 6, 2, 3, 1). (Esta tabla de modulos se calcula de forma sencilla; posteriormente sedescribira como.)

Ahora, si queremos saber si un numero (pongamos 21756) es multiplo de 7, basta con que hagamosla siguiente operacion:

5 4 6 2 3 1X X X X X2 1 7 5 6|| || || || ||8 6 14 15 6

El numero 21756 es multiplo de 7 si y solo si el numero 8+6+14+15+6=49 lo es. Averig¨emoslo:para saber si 49 es multiplo de 7 repetimos el proceso,

5 4 6 2 3 1X X4 9|| ||

12 9

y resulta que ahora necesitamos saber si 21 lo es: damos un ultimo paso y obtenemos,

5 4 6 2 3 1X X2 1|| ||6 1

5

que suma 7, que es multiplo de 7 obviamente. Por tanto, 21756 es multiplo de 7. Si, por el contrario,al final del proceso hubiesemos obtenido un numero inferior a 10 diferente de 7, sabrıamos que elnumero inicial no era multiplo de 7.

Ası pues, teniendo la tabla de modulos del 7 es facil comprobar si un numero es o no multiplo de7. Veamos ahora como calcularlas para los numeros mayores o iguales a 2.

Sea cual sea la tabla que calculemos ponemos en el extremo derecho un 1. El mecanismo generalconsiste en tomar la ultima entrada multiplicarla por diez y calcular el modulo de la division por elnumero del que deseamos calcular la tabla; este resultado pasa a ser una nueva entrada.

Supongamos que queremos calcular la tabla de modulos del numero 7 que hemos utilizado antes.Comenzamos poniendo 1 en el extremo derecho. Para calcular el siguiente numero multiplicamos el 1por 10 y ponemos el resto del producto dividido entre 7 en la segunda posicion de la tabla, obteniendode esta manera el 3. Repetimos el mismo proceso comenzando con el ultimo numero de la tabla, esdecir, lo multiplicamos por diez y calculamos el resto de dividir por 7; este numero, el 2, ocupa lasiguiente casilla. Repitiendo el proceso obtenemos la tabla (5, 4, 6, 2, 3, 1).

Se termina de calcular la tabla de modulos cuando se obtiene el primer factor repetido. En el casode la tabla del 7, si realizamos el calculo de la siguiente entrada para el 5, obtenemos que 50 mod7=1 que es la primera entrada de la tabla. No es necesario continuar ya que el proceso entrara en unciclo y se repetira la secuencia de numeros que ya se tiene.

Escribe un programa que, dado un numero entre 2 y 9, calcule la tabla de modulos de dichonumero. Solo tienen que calcularse las entradas de la tabla necesarias.


La entrada esta formada por un numero entre 2 y 9.


La salida consiste en la tabla de modulos correspondiente al numero anterior.

Ejemplo de entrada7

Salida para el ejemplo de entrada5 4 6 2 3 1

6

Problema ETres en raya

*.{pas,cpp,java}

Escribe un programa que, dado el contenido de un tablero 3x3, determine si se ha formado tres enraya. Las fichas del tablero solo pueden ser cruces o cırculos. Deben detectarse tres en raya tanto paracruces como para cırculos y en horizontal, vertical o diagonal.


La entrada esta formada por las fichas colocadas en las posiciones del tablero.


La salida consiste en la palabra TRUE so se ha formado tres en raya, o FALSE en caso contrario.

Ejemplo de entradaO O XX X OX O O

Salida para el ejemplo de entradaTRUE

7

Problema FRaıces complejas*.{pas,cpp,java}

Escribe un programa que permita calcular las raı complejas de un polinomio con coeficientes reales

P (x) = Ax2 + Bx + C


La entrada esta formada por los coeficientes A, B, C del polinomio. Supondremos que A es distintode cero.


La salida consiste en las dos raıs complejas del polinomio, posiblemente coincidentes.

Ejemplo de entrada1 0 1

Salida para el ejemplo de entradaI, -I

8

Problema GMultiplica matrices

*.{pas,cpp,java}

Escribe un programa que permita multiplicar dos matrices de un tamano arbitrario.


La entrada esta formada las dimensiones de cada matriz y el valor de sus respectiva entradas.


La salida consiste en la matriz producto.

Ejemplo de entrada231 2 34 5 6321 23 45 6

Salida para el ejemplo de entrada22 2849 64

9

Problema HDerivada de un polinomio

*.{pas,cpp,java}

Escribe un programa que, dado un polinomio de grado n, calcule la derivada de este polinomio.


La entrada esta formada por el grado del polinomio y por sus correspondientes coeficientes.


La salida consiste en el grado del polinomio derivada y sus coeficientes.

Ejemplo de entrada31 2 -1 1

Salida para el ejemplo de entrada23 4 -1

10

Problema IPunto de silla*.{pas,cpp,java}

Si consideramos una matriz cuadrada 4x4. se dice que un elemento es un punto de silla si esmaximo estricto de su fila y mınimo estricto de su columna. Puede demostrarse que dada una matrizde estas caracterısticas, o bien no tiene punto de silla, o bien este es unico. Escribe un programa que,dada una matriz de este tipo, decida si tiene o no punto de silla. En caso afirmativo, el programa debemostrar la posicion (fila, columna) del punto de silla, y su valor.


La entrada es una matriz 4x4.


La salida consiste en la palabra NO si la matriz no tiene un punto de silla. Si existe un (unico)punto de silla, se mostrara la posicion y su valor.

Ejemplo de entrada1 2 3 45 2 7 80 1 0 013 14 11 2

Salida para el ejemplo de entrada3 2 1

11

Problema JEl solitario de los 15

*.{pas,cpp,java}

En 1878, Samuel Loyd (1841–1911) presento un juego llamado simplemente los quince. Los quin-ce es un solitario que se juega en un tablero de 4x4 en el que los numeros del 1 al 15 son colocados alazar en las casillas. Al haber dieciseis casillas, siempre una queda libre. Por ejemplo:

10 2 15 36 7 5 119 1 8 1213 14 4

El objetivo del juego es ordenar completamente los numeros del tablero. El unico movimientoposible en el juego es deslizar, sin levantar, un numero al unico hueco libre que en cada momentotiene el tablero. Por ejemplo, partiendo de la posicion anterior, el 12 puede pasar abajo, luego el 8a la derecha, el 4 arriba ... hasta que se llegue a la solucion, es decir, a un tablero con los numerosordenados:

1 2 3 45 6 7 89 10 11 1213 14 15

Cuando Sam Loyd propuso el juego, dio una configuracion inicial muy sencilla: todos los numerosestaban ya ordenados salvo el 1 y el 15 que tenıan intercambiadas sus posiciones.

15 2 3 45 6 7 89 10 11 1213 14 1

Loyd ofrecio una enorme recompensa (1000 dolares de 1878) al primero que le presentase unasolucion al juego que proponıa. El juego hizo furor rapidamente y se puso de moda en Estados Unidosy en Europa. Es claro que no siempre hay solucion, y para comprobarlo podemos hacer una pruebade paridad sencilla. Escribe un programa que, dado un tablero del juego, nos diga si este tablero tienesolucion.

12


La entrada es un tablero del juego de los quince.


La salida consiste en RESOLUBLE si el tablero tiene solucion, o NO RESOLUBLE en caso contrario.

Ejemplo de entrada1 2 3 45 6 7 89 10 12 1513 14 11

Salida para el ejemplo de entradaRESOLUBLE

13

Problema KLa distancia mas corta: el algoritmo de Floyd-Warshall

*.{pas,cpp,java}

Un problema clasico de la Teorıa de Grafos es el de encontrar la distancia mas corta entre unaserie de lugares, separados por caminos de longitud variable. Por ejemplo, si tenemos n ciudades,Ciudad1...Ciudadn, definimos aij como la distancia de un camino directo entre la Ciudadi y laCiudadj . Podemos guardar estos datos en una matriz (aij) de tamano nxn. Sin embargo, los da-tos que tenemos que manejar no son n2, ya que aii = 0 para todo i, y aij = aji para todo i, j. ¿Cuantosdatos tenemos que manejar entonces?. Es decir, toda la informacion necesaria se puede guardar enuna matriz simetrica. Por ejemplo, si tenemos 3 ciudades, un ejemplo de matriz con informacion acercade los caminos que las unen es:

0 1 11 0 41 4 0

Encontrar la distancia mınima entre dos ciudades (posiblemente pasando por otras) no es unproblema trivial, sobre todo si el numero de datos es grande. Para resolver este problema podemosutilizar el Algoritmo de Floyd-Warshall. El algoritmo consiste en lo siguiente: sea A0 la matriz de laslongitudes de los caminos entre las n ciudades. Calculamos entonces las matrices A1, ..., An donde

Ak(i, j)= mınimo(Ak−1(i, j), Ak−1(i, k) + Ak−1(k, j))

para k = 1, ..., n. Las distancias mınimas son las entradas de An. En el ejemplo anterior,

A0 =0 1 11 0 41 4 0

A1 =0 1 11 0 21 2 0

=A2 = A3.

(Observa que, aunque hay un camino directo entre Ciudad2 y Ciudad3, de longitud 4, podemos llegarde una ciudad a otra utilizando un camino de longitud 2 que pasa por Ciudad1).

Escribe un programa que implemente el algoritmo de Floyd-Warshall, es decir, que reciba unamatriz con las longitudes de los caminos y devuelva una matriz con las distancias mınimas. Introduci-remos como dato el numero de ciudades.

14


La entrada es el numero de ciudades y la matriz simetrica de distancias.


La salida consiste en la matriz de distancias mınimas.

Ejemplo de entrada30 1 11 0 41 4 0

Salida para el ejemplo de entrada0 1 11 0 21 2 0

15

Problema LDiferencias finitas*.{pas,cpp,java}

Un problema que se presenta a menudo en multitud de areas (fısica, matematicas, ...) es encontrarla expresion general de una funcion de la que solo se conoce el valor en unos pocos puntos. Suponga-mos que se conocen los valores que toma una determinada funcion f en algunos puntos, por ejemploen 0, 1, 2, 3 y 4, y se desea encontrar una expresion de la funcion para poder estimar el valor en otrospuntos, por ejemplo en 3.25 o en -2. Dados n puntos en los que se conoce el valor de una funcion, elmetodo de las diferencias finitas se utiliza para buscar un polinomio de grado menor que n que pasepor dichos puntos. Veamos como funciona. Sea

P [0, 0], P [0, 1], P [0, 2], ...P [0, n− 1], P [0, n]

la secuencia conocida de valores de f(x). La primera secuencia de diferencias esta formada por losvalores P [1, i] = P [0, i]− P [0, i− 1], i = 1..n, dando lugar a

P [1, 1] = P [0, 1]− P [0, 0], P [1, 2] = P [0, 2]− P [0, 1], ..., P [1, n− 1] = P [0, n− 1]− P [0, n− 2], P [1, n] = P [0, n]− P [0, n− 1]

En general, calculamos las secuencias de diferencias con la formula

P [k, i] = P [k − 1, i]− P [k − 1, i− 1], i = k..n

que da como resultado la tabla:

P [0, 0] P [0, 1] P [0, 2] ... P [0, n− 1] P [0, n]P [1, 1] = P [0, 1]− P [0, 0] P [1, 2] = P [0, 2]− P [0, 1] ... P [1, n− 1] = P [0, n− 1]− P [0, n− 2] P [1, n] = P [0, n]− P [0, n− 1]

P [2, 2] = P [1, 2]− P [1, 1] ... P [2, n− 1] = P [1, n− 1]− P [1, n− 2] P [2, n] = P [1, n]− P [1, n− 1]... ... ...

P [n− 1, n− 1] = P [n− 2, n− 1]− P [n− 2, n− 2] P [n− 1, n] = P [n− 2, n]− P [n− 2, n− 1]P [n, n] = P [n− 1, n]− P [n− 1, n− 1]

A partir de la tabla de diferencias finitas se puede construir un polinomio que tiene el mismovalor que la funcion en los puntos conocidos. Si los puntos en que se ha calculado la funcion son losnaturales 0, 1, 2, 3, ... se puede utilizar la formula de Newton:

P [0, 0] + P [1, 1]x + (1/2)P [2, 2]x(x− 1) + ( 12∗3)P [3, 3]x(x− 1)(x− 2) + ...

Escribe un programa que, dados n valores, calcule la tabla de diferencias correspondiente.

16


La entrada es una sucesion de n valores.


La salida consiste en la tabla de diferencia correspondiente.

Ejemplo de entrada1, 2, 4, 7, 11

Salida para el ejemplo de entrada1 2 4 7 111 2 3 41 1 1

0 00

17

Problema MMultiplica polinomios

*.{pas,cpp,java}

Para describir un polinomio basta dar la lista de sus coeficientes. Por ejemplo, el polinomio 3x2 + 3x− 2se puede ver como la lista 3 3 -2

Escribe un programa que permita multiplicar dos polinomios.


La entrada esta formada por dos listas, correspondientes a los dos polinomios. En primer lugar seintroduce el coeficiente del monomio de mayor grado.


La salida consiste en la lista correspondiente al polinomio producto.

Ejemplo de entrada3 3 -21 0

Salida para el ejemplo de entrada3 3 -2 0

18

Problema NDeterminante*.{pas,cpp,java}

Calcula del determinante de una matriz cuadrada, procurando utilizar un algoritmo efectivo.


La entrada esta formada por el taman de la matriz y el valor de sus componentes.


La salida consiste en el valor del determinante.


Salida para el ejemplo de entrada-53.0

19

Problema NOrdenacion por seleccion

*.{pas,cpp,java}

Se desea observar como funciona el metodo de ordenacion por seleccion al trabajar con un array.El algoritmo de seleccion consiste en seleccionar en cada etapa la compomente mınima (o maxima) eintercambiarla con la que esta en la posicion que deberıa ocupar dicha componente.

Una manera de seguir el algoritmo de seleccion, consisteen ver en cada etapa la componente seleccionada y lacomponente con la que va a intercambiar posiciones. Porejemplo, podemos considerar una traza como :

Vector inicial: MURCIELAGOEtapa 1: A MEtapa 2: C UEtapa 3: E REtapa 4: G UEtapa 5: IEtapa 6: L REtapa 7: M REtapa 8: O REtapa 9: R U

Vector final: ACEGILMORU

Escribe un programa que lea una secuencia de caracteres y los ordene mediante el algoritmo deordenacion por seleccion, mostrasdo la traza correspondiente.


La entrada es una secuencia de caracteres.


La salida es la secuencia anterior, ordenada alfabeticamente, y la secuencia de pasos en la ordena-cion.

Ejemplo de entradaMURCIELAGO

Salida para el ejemplo de entradaVector inicial: M U R C I E L A G O

Etapa 1: A M

Etapa 2: C U

Etapa 3: E R

Etapa 4: G U

Etapa 5: I

Etapa 6: L R

Etapa 7: M R

Etapa 8: O R

Etapa 9: R U

Vector final: A C E G I L M O R U

20

Problema OLiga de futbol*.{pas,cpp,java}

Estamos interesados en gestionar un liga de futbol. En particular, queremos pasar de una formaautomatizada de los resultados de la jornada a la quiniela resultante. Para cada partido se considerael equipo que juega en casa, el visitante, los goles que marca cada uno y el resultado en la casillacorrespondiente de la quiniela (1 si gana el de casa, X si hay empate y 2 si gana el visitante). Escribeun programa que permita pasar de los resultados de la jornada a la quiniela resultante, considerandouna liga de 6 equipos.


La entrada es una lista donde en cada fila tenemos el nombre del equipo que juega en casa, losgoles que ha metido en el partido, el nombre del equipo visitante y sus correspondientes goles.


La salida consiste en una lista donde figura el nombre del equipo que juega en casa, el nombre delequipo visitante y el signo de la quiniela correspondiente al partido.

Ejemplo de entradaLinux 2 Mac 0Emacs 6 Kate 1Firefox 8 MSIE 0OpenOffice 2 LaTeX 3

Salida para el ejemplo de entradaLinux Mac 1Emacs Kate 1Firefox MSIE 1OpenOffice LaTeX 2

21

Problema PSopa de letras*.{pas,cpp,java}

Uno de los pasatiempor mas conocidos es la sopa de letras. Una sopa es un retangulo de N filas yM columnas en el que hay letras, en principio, complentamente desordenadas. El pasatiempo consisteen encontrar, entre dichas letras, palabras relacionadas con un tema. Las palabras pueden leerse en lasopa de izquierda a derecha o de derecha a izquierda, en direccion vertical, horizontal o diagonal. Porejemplo, la siguiente sopa contienen la palabra LINUX.

Z X C V B NA L I N U XS D F G H JW E R P T Y

Realiza un programa que, dada una sopa de letras y una palabra, averig¨e si dicha palabra esta enla sopa, indicando ademas, en caso afirmativo, la posicion en que empieza y su direccion de lectura.


La entrada es una sopa de letras, especificada por su tamano y por las letras que la componen, yla palabra a buscar.


La salida es la palabra NO si la palabra buscada no esta en la sopa, o SI en caso contrario. En estesegundo caso, se indicaran las coordenadas donde la palabra empieza, y la direccion de lectura.

Ejemplo de entrada46

Z X C V B NA L I N U XS D F G H JT N I N E L

LINUX

Salida para el ejemplo de entradaSI 2 2 derecha

22

Problema QTraductor Morse*.{pas,cpp,java}

Se desea confeccionar un programa traductor de textos entre el alfabeto sajon y el de Morse:

A .- B -... C -.-. D -..E . F ..-. G –. H ....I .. J .— K -.- L .-..M – N -. O — P .–.Q –.- R .-. S ... T -U ..- V ...- W .– X -..-Y -.– Z –..

Desarrolla un programa que lea unas lıneas de la entrada estandar y traduzca a Morse las letrasmayusculas, ignorando los demas caracteres y separando los codigos de las letras en Morse con unespacio.


La entrada esta formada por una secuencia de caracteres.


La salida consiste en la traduccion de las letras mayusculas, ignorando los demas caracteres yseparando los codigos de las letras en Morse con un espacio.

Ejemplo de entradaALFABETO MORSE

Salida para el ejemplo de entrada.- .-.. ..-. .- -... . - --- -- --- .-. --- .

23

Problema REl juego de la vida*.{pas,cpp,java}

Vamos a desarrollar un programa de simulacion, que juega a un bonito solitario inventado en 1970por John H. Conway. Dicho juego simula la evolucion de una colonia de bichos que vive en un mundocuadriculado cuyas casillas, en un momento dado, pueden estar vacıas o habitadas por un solo ser. Laevolucion de nuestra poblacion de un instante a otro esta sujeta a las siguientes reglas:

NACIMIENTO. En una casilla vacıa que tenga exactamente 3 casillas vecinas habitadas, nace unnuevo bicho. Consideramos vecinas a las 8 casillas circundantes a una dada.

SUPERVIVENCIA. Cada bicho que tenga dos o tres bichos vecinos sobrevive y pasa a la genera-cion siguiente.

MUERTE. Cada bicho que solo tenga un bicho vecino, o no tenga ninguno, muere de soledad.Cada bicho con cuatro bichos vecinos o maa, muere por superpoblacion.

Es importante observar que todos los nacimientos o muertes ocurren simultaneamente.

Dependiendo de la configuracion de partida, la poblacion va experimentando cambios curiososque, en ciertos aspectos, remedan a menudo el comportamiento de la vida real: a veces se extingue,otras crece sin cesar, ... Desarrolla un programa que, a partir del mundo en un instante dado, halle elestado del mundo en la siguiente generacion.


La entrada es un tablero N por N en el que estan marcadas casillas vacıs (O) y ocupadas por unbicho (X).


La salida es un tablero N por N en el que estan marcadas casillas vacıas (O) y ocupadas por unbicho (X), resultante de la evolucion del mundo a partir de la configuracion anterior.

24

Ejemplo de entrada6O O O O O OX X X X O OO O O O O XO O O O O XX X O O X OX X O O O O

Salida para el ejemplo de entradaO X X O O OO X X 0 O OO X X O X OO O O O X XX X O O O OX X O O O O

25

Problema SLights out

*.{pas,cpp,java}

Mostramos el juego llamado lights out (luces fuera). El juego se desarrolla en una matriz de M porN casillas. Durante el juego, cada una de esas casillas puede estar apagada o encendida. Cuando sepulsa una de ellas, cambia de estado (se enciendo si estaba apagada, o se apaga si estaba encendida),y al mismo tiempo cambia el de sus cuatro casillas vecinas (encima, debajo, izquierda, derecha). Elobjetivo del juego es apagar todas las casillas.

Por ejemplo, si denotamos las casillas encendidas con X y las apagadas con O, y partimos deltablero:

X X O O OX O O X OO O X X XO O O X OO O O O O

al pulsar consecutivamente las casillas (1,1), (2,5) y (4,5) se llega a la siguiente situacion:

O O O O XO O O O XO O X X XO O O O XO O O O X

Observa que la casilla (3,5) ha quedado como al principio, debido a que ha cambiado su estadodos veces.

Escribe un programa que, dado un tablero del juego (digamos de tamano 5 por 5), con su corres-pondiente combinacion de luces encendidas y apagadas, y una casilla, nos devuelva la configuracionobtenida a pulsar esta casilla.


La entrada es un tablero del juego (5 por 5), con su correspondiente combinacion de luces encen-didas y apagadas, y las coordenadas de una casilla.


La salida consiste en un tablero del juego, con la combinacion de luces encendidas y apagadas,obtenida al pulsar la casilla indicada.

26

Ejemplo de entradaX X O O OX O O X OO O X X XO O O X OO O O O O1 1

Salida para el ejemplo de entradaO O O O OO O O X OO O X X XO O O X OO O O O O

27

Problema TCuadrados magicos

*.{pas,cpp,java}

Se denomina cuadrado magico a una colocacion de n2 numeros en filas y columnas formando uncuadrado, con n numeros en cada fila y en cada columna, de tal forma que la suma de los elementosde cada fila, cada columna y las dos diagonales de cuadrado de el mismo valor. Habitualmente losnumeros utilizados para colocar en un cuadrado de lado n son aquellos comprendidos entre el 1 y eln2. Escribe un programa que permita comprobar que un cuadrado relleno de numeros es en efecto uncuadrado magico.


La entrada es un entero n y los n2 numeros correspondientes. La salida consiste en SI si el cuadradoes magico, y NO en caso contrario.


La salida consiste en SI si el cuadrado es magico, y NO en caso contrario.


Salida para el ejemplo de entradaSI

28

Problema UImplementacion de numeros grandes

*.{pas,cpp,java}

Los enteros en cualquier lenguaje de programacion estan limitados en su tamano. Te proponemosdefinir un nuevo tipo de entero que no tenga dicha limitacion. Para ello se elegira una BASE suficien-temente grande y se representaran los numeros como listas de cifras en esta base. Si BASE=100, elnumero 10567991238934 (expresado en base 10) se puede representar como

934 228 991 567 10 ...

puesto que

10567991238934 = 10x10004 + 567x10003 + 991x10002 + 238x10001 + 934x10000.

Escribe un programa que dados dos enteros grandes, calcule su suma y su resta. Para ello tendrasque implementar un tipo de datos adecuado.


La entrada es un par de enteros grandes.


La salida consiste la suma y la resta de los enteros anteriores

Ejemplo de entrada39209281921284392019

Salida para el ejemplo de entrada52053202112636536173

29

Problema VPalındromos

*.{pas,cpp,java}

Un palındromo es una cadena de caracteres que se lee igual de izquierda a derecha que de derechaa izquierda. Por ejemplo, Ana o radar. Tambien se dice que una frase es un palındromo si se lee igualde izquierda a derecha que de derecha a izquierda, sin considerar espacios en blanco ni signos depuntuacion. Por ejemplo, Atale, demonıaco Caın, o me delata (Julio Cortazar). Escribe un programaque lea una frase y decida si es o no un palındromo, sin tener en cuenta espacios en blanco ni signosde puntuacion.


La entrada es una secuencia de caracteres.


La salida consiste en PALINDROMO si la secuencia es un palıdromo, NO PALINDROMO en casocontrario.

Ejemplo de entradaLa ruta nos aporto otro paso natural

Salida para el ejemplo de entrada

PALINDROMO

30

http://es.wikipedia.org/wiki/Julio_Cort%C3%A1zar�

Problema WBaldosas de jardın

*.{pas,cpp,java}

Los padres de Carmencita quieren embaldosar el jardın de su casa y para ello han comprado dostipos de baldosas: las negras, que son cuadradas, y las blancas, que son el doble de largas que lasbaldosas negras.

La idea es utilizar las baldosas negras para hacer disenos y las baldosas blancas para completar loshuecos. Despue de algunos bocetos para dar con un diseno que les gustase, los padres de Carmencita sedan cuenta de que el trabajo no es tan sencillo como parecıa: algunos disenos hechos con las baldosasnegras dejan huecos que no se pueden cubrir con baldosas blancas! Viendo que sus padres estabanmuy preocupados, Carmencita se puso a pensar en el problema y les prometio hacer un programa quelos pudiese ayudar. Por ejemlo, si consideramos la siguiente configuracio de baldosas negras:

Tenemos que el hueco dejado para las baldosas blancas tieneun numero de casillas insuficientes. Pero aquı no se acabanlos problemas. En la configuracion el hueco dejado por lascasillas negras tiene un numero para de casillas, pero tampo-co se puede rellenar por las casillas blancas.


La entrada es una configuracion de baldosas negras.


La salida consiste en SI si podemos cubrir el hueco con baldosas blancas, NO en caso contrario.

31

Ejemplo de entradaX X

X XX X

X X

Salida para el ejemplo de entradaSI

32

Documents

Problemas sobre estructuras de datosproblem-g.estad.ucm.es/FLOP/pdf/cs1_4.pdf · A. Traspuesta de una matriz 2 B. Cuadrado latino 3 C. Centro de un vector 4 D. Criterios de divisibilidad