Ejercicios Programacion h1i4r

<*I2 <6) HH ;)69+9(,.-()969+,2 JJH C<*;+76K+ (7 )L/(1I 9( ;)69+9(, -()969+, 9( 7+ ,;<;1,+7 7(69+ Guión de Prácticas. Fundamentos de Programación

RP-III.14

RELACIÓN DE PROBLEMAS III. Funciones y Clases

!"!#$% ! &# "'(%$% $) *)#(!+,)"-.)+! 4

/0# 11 0$)#(02,+&/&.+! 3

551 67()#). ) 0$)#(020/!$%. 8 ) #9").% $) *)#(!+ $) ! +&/&.+! :!#!$%.! !"!#$% ! &# "'(%$% $) *)#(!+,)"-.)+! Finalidad: Diseño de una clase. Dificultad Media. 28. Implementar los métodos de la clase ;)#(!+ del ejercicio anterior. Finalidad: Diseño de una clase. Dificultad Media. 29. Definid una función para que calcule la distancia euclídea entre dos puntos. Cada punto será un dato de tipo +(.&/(. Finalidad: Trabajar con struct. Dificultad Baja. 30. Implemente una clase para representar un número complejo. Un complejo se define como un par ordenado de números reales (a, b), donde a representa la parte real y b la parte imaginaria. Construya un programa principal que lea la parte real e imaginaria, cree el objeto e imprima el complejo en la forma ! < 70. Por ahora no podemos implementar métodos para sumar, por ejemplo, dos complejos. Lo veremos en el último tema. 31. Una empresa quiere gestionar las nóminas de sus empleados. El cómputo de la nómina se realiza en base a los siguientes criterios: a) Hay cuatro tipos de categorías laborales: Operario, Base, istrativo y Directivo. b) Se parte de un salario base que depende de la antigüedad del trabajador y de su categoría laboral. Para la categoría Operario, el salario base es de 900 euros, 1100 el puesto Base, 1200 los istrativos y 2000 los Directivos. Dicho salario base se incrementa con un tanto por ciento igual al número de años trabajados. c) Los trabajadores tienen complementos en su nómina por el número de horas extraordinarias trabajadas. La hora se paga distinta según la categoría: 16 euros por hora para los operarios, 23 para el puesto Base, 25 los istrativos y 30 los Directivos. Además, al complemento que sale al computar el número de horas extraordinarias, se le aplica una subida con un tanto por ciento igual al número de años trabajados. Se pide diseñar la interfaz de una clase (también hay que incluir los datos miembro privados) para poder trabajar con esta información. No se pide implementar la clase, únicamente determinar la interfaz.

Guión de Prácticas. Fundamentos de Programación

RP-III.15

RELACIÓN DE PROBLEMAS III. Funciones y Clases Finalidad: Diseñar la interfaz de una clase. Dificultad Media. 32. Implementad la clase del ejercicio 31 de esta relación de problemas. Dificultad Media. 33. Definid una clase !"#$% para poder trabajar de forma precisa con datos monetarios. La clase tendrá dos datos miembro, #&$%' y (#")!*%' y cuando se modifiquen éstos, la clase debe permitir que se introduzca un número de céntimos mayor de 100. Por ejemplo, si asignamos 20 euros y 115 céntimos, el objeto debe almacenar 21 en #&$%' y +, en (#")!*%'. En el último tema veremos cómo sumar o restar dos objetos de la clase !"#$%. Incluid un sencillo programa principal que llame a los métodos. Finalidad: Trabajar con una clase como una abstracción de un concepto. Dificultad Baja. 34. Recuperad la solución del ejercicio 28 (Empresa) y modificadlo convenientemente para que los datos que referencia los identificadores de las sucursales sean constantes. Finalidad: Trabajar con datos constantes. Dificultad Baja. 35. La sonda Mars Climate Orbiter fue lanzada por la NASA en 1998 y llegó a Marte el 23 de septiembre de 1999. Lamentablemente se estrelló contra el planeta ya que se acercó demasiado. El error principal fue que los equipos que desarrollaron los distintos módulos de la sonda usaron sistemas de medida distintos (el anglosajón y el métrico). Cuando un componente software mandaba unos datos en millas (o libras), otro componente software los interpretaba como si fuesen kilómetros (o Newtons). El problema se habría arreglado si todos hubiesen acordado usar el mismo sistema. En cualquier caso, cada equipo se encuentra más a gusto trabajando en su propio sistema de medida. Por tanto, la solución podría haber pasado por que todos utilizasen una misma clase para representar distancias (idem para fuerzas, presión, etc), utilizando los métodos que les resultasen más cómodos. Para ello, se pide construir la clase !')-"(!- que contendrá métodos como .#)/!0%*#)$%', .#)1!00-', etc. Internamente se usará un único dato miembro privado llamado 2!0%*#)$%' al que se le asignará un valor a través de los métodos anteriores, realizando la conversión oportuna (una milla es 1,609344 kilómetros). La clase también proporcionará métodos como 3#)/!0%*#)$%' y 3#)1!00-' para lo que tendrá que realizar la conversión oportuna (un kilómetro es 0,621371192 millas). Observad que la implementación de la clase podría haber utilizado como dato miembro privado, una variable *!00-', en vez de 2!04*#)$%'. Esto se oculta a los s de la clase, que sólo ven los métodos .#)/!0%*#)$%', .#)1!00-', 3#)/!0%*#)$%' y 3#)1!00-'. Cread un programa principal que pida algunos datos y muestre los valores convertidos. Nota. Otro de los fallos del proyecto fue que no se hicieron suficientes pruebas del software antes de su puesta en marcha, lo que podría haber detectado el error. Esto


RP-III.16

RELACIÓN DE PROBLEMAS III. Funciones y Clases pone de manifiesto la importancia de realizar una batería de pruebas para comprobar el correcto funcionamiento del software en todas las situaciones posibles. Esta parte en el desarrollo de un proyecto se le conoce como pruebas de unidad (unit testing) Finalidad: Trabajar con una clase como una abstracción de un concepto. Dificultad Baja. 36. Construid una clase llamada !"#"$%&'()* que represente una medida de un ángulo. Al igual que se hizo en el ejercicio 35, la clase aceptará datos que vengan de alguna de las siguientes formas: número de grados con decimales (real); número de radianes (entero); número de segundos (entero); número de grados, minutos y segundos (en un struct que represente estos tres valores) Dificultad Baja. 37. Cread un +,-(., llamado /**-"!&$"$+0(&,*12 para representar un par de valores reales correspondientes a un punto en R2 . Cread ahora una clase llamada /#-.(&3!-!&.#$. Para establecer el centro, se usará un dato miembro del tipo /**-"!&$"$+0(&,*12. Añadid métodos para obtener la longitud de la circunferencia y el área del círculo interior. Añadid también un método para saber si la circunferencia contiene a un punto. Recordemos que un punto (x1 , y1 ) está dentro de una circunferencia con centro (x0 , y0 ) y radio r si se verifica que: (x0 − x1 )2 + (y0 − y1 )2 <= r 2 Observad que el valor de π debe ser constante, y el mismo para todos los objetos de la clase /#-.(&3!-!&.#$. Finalidad: Trabajar con constantes estáticas de tipo "*(4)!. Dificultad Baja.


RP-III.17

RELACIÓN DE PROBLEMAS IV. Vectores

RELACIÓN DE PROBLEMAS IV. Vectores En los ejercicios que pida trabajar sobre la clase definición:

!"#!$"%&'&(&")!(!*, use la siguiente

"+&** !"#!$"%&'&(&")!(!* , -(%.&)!/ *)&)%" "0$*) %$) 1232456 7 89: ";&( .!")0(<-(%.&=0>1232456?: %$) )0)&+<#)%+%@&=0*: -#A+%"/ !"#!$"%&'&(&")!(!*BC /)0)&+<#)%+%@&=0*B9C, D %$) 10)&+E)%+%@&=0*BC, (!)#($ )0)&+<#)%+%@&=0*: D %$) '&-&"%=&=BC, (!)#($ 1232456: D .0%= 2$%&=!B";&( $#!.0C, %F B)0)&+<#)%+%@&=0* G 1232456C, .!")0(<-(%.&=0>)0)&+<#)%+%@&=0*? 7 $#!.0: )0)&+<#)%+%@&=0*HH: D D ";&( I+!J!$)0B%$) %$=%"!C, (!)#($ .!")0(<-(%.&=0>%$=%"!?: D .0%= I+%J%$& B%$) -0*%"%0$C, %F B-0*%"%0$ K7 9 LL -0*%"%0$ G )0)&+<#)%+%@&=0*C, %$) )0-! 7 )0)&+<#)%+%@&=0*MN: F0( B%$) % 7 -0*%"%0$ : % G )0-! : %HHC .!")0(<-(%.&=0>%? 7 .!")0(<-(%.&=0>%HN?:

D

D

)0)&+<#)%+%@&=0*MM:

*)(%$O 10 )(%$OBC, *)(%$O "&=!$&:


RP-IV.1


!" #$%& $'() $*&!&+,-.&$,$/+0!1) $223 4+05%+ ' 4+05%+ 2 654&!"-7"$6+0!8$9)

:)

:

"5&."% 4+05%+)

Importante: • Para todos los ejercicios, se ha de diseñar una batería de pruebas. • Recuerde lo visto en las transparencias del primer tema: para poder leer un espacio en blanco no puede emplear 4$% ;; 4+"+4&5", sino 4+"+4&5" ' 4$%<=5. Cada vez que se ejecute 4$%<=5 el compilador lee un carácter (incluido el espacio en blanco, el tabulador y el retorno de carro >?%>) desde la entrada de datos por defecto. En definitiva, el bucle de lectura de datos será del tipo:

4+"+4&5" ' 4$%<=5) @A$,5 #4+"+4&5" B' CDEFGHIJKE3L <<<<<< 4+"+4&5" ' 4$%<=5) : Supondremos que la entrada de datos es desde un fichero de texto. De esta forma, cada ejecución de 4$%<=5 lee directamente un carácter (incluidos los espacios en blanco, tabuladores y retornos de carro) y el programa pasa a la siguiente sentencia. Si fuese desde el teclado, habría que esperar a que el introdujese el retorno de carro para que los datos pasasen al buffer y una vez ahí, se ejecutarían automáticamente todos los 4$%<=5 (recordad lo visto al final del primer tema) En el caso de que, por ejemplo, quisiéramos parar la lectura cuando se hubiesen introducido más de un número tope de caracteres, no podríamos hacerlo con la lectura desde teclado ya que los datos no pasan al buffer hasta que no se pulse el retorno de carro.


RP-IV.2

RELACIÓN DE PROBLEMAS IV. Vectores 1. Tenga en cuenta la observación al inicio de esta relación de problemas sobre la lectura de los caracteres. Para poder leer caracteres, incluyendo los espacios en blanco, hay 62 que usar !"! #$" % &'()$#*+, en vez de &' ,, !"! #$". En este ejercicio trabajaremos con un vector directamente en el clases.

-!&', sin utilizar

Declare un vector de caracteres de tamaño 100. Lea las componentes considerando como terminador el carácter . (éste no forma parte de la secuencia) y que no se introduzcan más de 100 caracteres. Las componentes leídas ocuparán las primeras posiciones contiguas del vector. El resto de las posiciones se quedarán con el valor indeterminado (basura) que el compilador le asignase al principio. Para conocer cuántas componentes se están utilizando, utilice una variable #/#!012#&0&3!4/5 (que, obviamente, deberá ser menor de 100 en todo momento) Implemente algoritmos para realizar las siguientes tareas: a) Comprobar si el vector es un palíndromo, es decir, que se lee igual de izquierda a derecha que de derecha a izquierda. Por ejemplo, 67!78797879787!7: sería un palíndromo, pero 67!787 7879787!7: no lo sería. Si la secuencia tiene un número impar de componentes, la que ocupa la posición central es descartada, por lo que 67!7879787;7879787!7: sería un palíndromo. b) Invertir

el

vector.

Si

éste contenía, por ejemplo, los caracteres 67-7872787'7874787/7:, después de llamar al método se quedará con 67/7874787'7872787-7:.

c) Contar el número de mayúsculas que contiene. Finalidad: Recorrer las componentes de un vector. Dificultad Baja. 2. Construya la función con cabecera: 63

5#"&') <&)&#/5 *&'# '+ para que extraiga en un 5#"&') los dígitos del número ejercicio 27 de la relación de problemas II.

' tal y como se indica en el

Finalidad: Trabajar con la clase 5#"&'). Dificultad Baja. 3. Recupere la solución del ejercicio 28 (ventas de empresa) de la relación de problemas III. Resuelva el problema pedido (calcular la sucursal con mayor número de ventas) pero ahora considere que no conoce a priori el número de sucursales que hay, aunque sabe que los códigos de éstas siempre son números entre 1 y 100 y que en total no hay más de 100 sucursales. Por lo tanto, tendrá que añadir como dato miembro de la clase, un vector con un tamaño máximo de 100. Cree un programa principal de prueba. Finalidad: Trabajar con vectores como datos miembro de una clase. Dificultad Baja.


RP-IV.3


!"#$%&'()*), +&,%-(.- y /0*-()1#20!30$#! a la clase 4-30-&3%#5#(#3.-(-! que implementen las tareas descritas en el ejercicio 1 de

4. Añada los métodos

64 esta relación de problemas.

Incluya un programa principal de prueba similar al del ejercicio 1. Finalidad: Diseñar las cabeceras de los métodos que acceden a las componentes del vector. Dificultad Baja. la clase 4-30-&3%#5#(#3.-(-!, añada el método +&.-(3#*6%#5)*7)&-&.-! para intercambiar dos componentes de la secuencia. Por ejemplo, si la secuencia contiene 89:9;9)9;9$9;9#9<, después de intercambiar las componentes 1 y 3, se quedaría con 89:9;9#9;9$9;9)9<.

5. Sobre

¿Qué debería hacer este método si los índices no son correctos? Modifique la implementación del método +&,%-(.- del ejercicio 4, para que lo haga llamando a +&.-(3#*6%#5)*7)&-&.-! . Imprima las componentes de la secuencia desde el *#%&, antes y después de llamar a dicho método. Para ello, use el método =)4.(%&>?@ de la clase 4-30-&3%#5#(#3.-(-!. Finalidad: Ejemplo de método que modifica el estado del objeto. Gestión de precondiciones. Dificultad Baja. 6. Sobre la clase 4-30-&3%#5#(#3.-(-! , añada el método $%*%#20!30$#! para eliminar todas las mayúsculas. Por ejemplo, después de aplicar dicho método al vector 8949;9)9;9A9;9 9;929;9B9< , éste debe quedarse con 89)9;9 9;929<. Un primer algoritmo para resolver este problema sería el siguiente (en ejercicios posteriores se verán métodos más eficientes):

C-3)((-( .)'#! $#! 3)*7)&-&.-! '- $# !-30-&3%# 4% $# 3)*7)&-&.- -! 0&# *#2D!30$#; 6)((#($# Queremos implementarlo llamando al método $%*%&# (que borra un único carácter):. La implementación de este método se ha visto en clase de teoría.

3$#!! 4-30-&3%#5#(#3.-(-!8 EEEEEEEEE ,)%' $%*%#20!30$#! (()(?@8 F)( ?%&. %GHI %J.).#$K0.%$%L#')!I %MM@ %F ?%!077-(?,-3.)(K7(%,#')N%O@@ $%*%&#?%@I <


RP-IV.4

RELACIÓN DE PROBLEMAS IV. Vectores El anterior código tiene un fallo. ¿Cuál? Pruébelo con cualquier secuencia que tenga dos mayúsculas consecutivas, proponer una solución e implementarla. Finalidad: Recorrido sencillo de un vector con dos bucles anidados. Dificultad Baja. 7. El algoritmo del ejercicio 6 es muy ineficiente ya que requiere trasladar muchas veces muchas posiciones (usa dos bucles anidados). Para comprobarlo, ejecute el método sobre el texto del Quijote, disponible en decsai. Para ello, lea los caracteres hasta encontrar el terminador . Para que el texto quepa en la pila, debe hacer los siguientes cambios: • Dentro de la clase !"#$"%#&'(')'#*")"+ cambie el tamaño del vector privado a ,-..... (dos millones y medio de bytes, unos 2.4 MB) • Aumente el tamaño de la pila asignada por el sistema operativo al programa generado por el compilador. Para ello, debe seleccionar desde DevC++:

/"))'0&"%*'+ 12 34#&5%"+ 6"7 (504&7'65) 12 Señale la opción

89'6&) 75+ +&:$&"%*"+ #50'%65+ '7 77'0') '7 #504&7'65) y en la caja de texto introduzca lo siguiente:

1;7<11+*'#=<,>..... Para resolver eficientemente este problema se propone utilizar dos variables, 45+&#&5%?7"#*$)' y 45+&#&5%?"+#)&*$)' que nos vayan indicando, en cada momento, la componente que se está leyendo y el sitio dónde tiene que escribirse. Por ejemplo, supongamos que en un determinado momento la variable 45+&#&5%?7"#*$)' vale 6 y 45+&#&5%?"+#)&*$)' 3. Si la componente en la posición 6 es una mayúscula, simplemente avanzaremos 45+&#&5%?7"#*$)'. Por el contrario, si fuese una minúscula, la colocaremos en la posición 3 y avanzaremos una posición ambas variables. Implemente este algoritmo y observe la diferencia de tiempo al ejecutarlo sobre el Quijote. Mientras que el algoritmo eficiente tarda unos 8 milisegundos, el ineficiente puede tardar un minuto o más, dependiendo de la potencia del ordenador. Como ampliación: si quiere saber con exactitud el tiempo de ejecución, puede utlizar un objeto #)5%5?0'@$+#$7'+ de la clase ()5%50"*)5 descrita más abajo. Antes de ejecutar el método cuyo tiempo de ejecución quiere analizar debe poner #)5%5?0'@$+#$7'+AB"+"*CD y justo después de que termine el método, debe ejecutar el método #)5%5?0'@$+#$7'+AE&7&!":$%65+F)'%+#$))&65+CD .

&%#7$6" G#H)5%52 #7'++ ()5%50"*)5I 4)&J'*"K Guión de Prácticas. Fundamentos de Programación

RP-IV.5


!"#$#% & $''()*+,+'' -.#/"+-, 0& $''()*+,+''& #1$!/(2+(34 56, +/#,/#2/7-#."+8 !"#$#% ()*+,+''$6*1 -+, 0$+692#: ,1,+4 ;, #*<12+7-#."+8 56, +/#,/#2/7-#."+ -,-(-+8 56, +/#,/#2/7-#."+ %-,128 "692-(' <+-$ =#&# >?@ -,-(-+ A ()*+,+''& #1$!/(2+(3'',+B>?8 C $+692# D-2-E#F6,$+&7*1,&(6**-$+&>?@ %-,12 A ()*+,+''& #1$!/(2+(3'',+B>?8 ;, #*<12+7-#."+ $-%#*#,(-1 A %-,12 G -,-(-+8

C8

C

*# 6*, $-%#*#,(-1H(+6, >? I J#KL8

Finalidad: Modificar un vector a través de dos apuntadores. Dificultad Media. 8. Sobre la clase E#(6#,(-1M1*1( #*#& , añada un método N2-.-,1=#"# -$+& que quite los elementos repetidos, de forma que cada componente sólo aparezca una 69 única vez. Se mantendrá la primera aparición, de izquierda a derecha. Por ejemplo, si la secuencia contiene

@O9O:O1O:O1O:O)O:O1O:O1O:O1O:O1O:O(O:O1O:O1O:O1O:OFOC después de quitar los repetidos, se quedaría como sigue:

@O9O:O1O:O)O:O(O:OFOC

Implemente los siguientes algoritmos para resolver ester problema: a) Usando un vector local &-,/*#"# aparición de cada componente:

-$+& en el que almacenamos una única

=#(+**#* +$1& 21& (+."+,#, #& $# 21 &#(6#,(-1 +*-F-,12 E- 21 (+."+,#, # PQ #& R #, S&-,/*#"# -$+&S: 1T1$-*21 >12 <#( +* S&-,/*#"# -$+&S? U&-F,1* 21& (+."+,#, #& $# S&-,/*#"# -$+&S 1 21 &#(6#,(-1 b) El problema del algoritmo anterior es que usa un vector local, lo que podría suponer una carga importante de memoria si trabajásemos con vectores grandes. Por lo tanto, vamos a resolver el problema sin usar vectores locales. Si una componente está repetida, se borrará de la secuencia. Para borrar una componente, llamamos al método N2-.-,1. c) El anterior algoritmo nos obliga a desplazar muchas componentes cada vez que encontremos una repetida. Proponga una alternativa (sin usar vectores locales) para que el número de desplazamientos sea el menor posible e impleméntela.


RP-IV.6

RELACIÓN DE PROBLEMAS IV. Vectores Consejo: Use la misma técnica que se indicó en el ejercicio 7 de eliminar las mayúsculas. Finalidad: Usar un vector local. Modificar un vector a través de dos apuntadores. Dificultad Media. la clase !"#!$"%&'&(&")!(!*, añada un método +,%-%$&+."!*/0,&$"/* para eliminar el exceso de caracteres en blanco, es

9. Sobre

decir, que sustituya todas las secuencias de espacios en blanco por un sólo espacio. Por ejemplo, si la secuencia original es 12 232&2324232 232 232 232"25 , que contiene una secuencia de tres espacios consecutivos, la secuencia resultante debe ser 12 232&2324232 232"25 . Nota: Debe hacerse lo más eficiente posible. Finalidad: Recorrido de las componentes de un vector, en el que hay que recordar lo que ha pasado en la iteración anterior. Dificultad Media. 10. En este ejercicio no hay que definir ninguna clase. Todas las operaciones se realizan directamente en el -&%$. 67

Construya un programa que vaya leyendo caracteres hasta que se encuentre un punto 262 y cuente el número de veces que aparece cada una de las letras mayúsculas. Imprimir el resultado. Una posibilidad sería declarar un vector "/$)&7/(8-&9#*"#,&* con tantas componentes como letras mayúsculas hay (2:2;2<2=>) y conforme se va leyendo cada carácter, ejecutar lo siguiente:

"%$ ?? ,!)(&@ %A 1,!)(& BB 2<25 "/$)&7/(8-&9#*"#,&*CDE B "/$)&7/(8-&9#*"#,&*CDE = >@ !,*! %A 1,!)(& BB 2025 "/$)&7/(8-&9#*"#,&*C>E B "/$)&7/(8-&9#*"#,&*C>E = >@ !,*! %A 1,!)(& BB 2'25 "/$)&7/(8-&9#*"#,&*CFE B "/$)&7/(8-&9#*"#,&*CFE = >@ !,*! 6666 Sin embargo, este código es muy redundante. Como solución se propone calcular de forma directa el índice entero que le corresponde a cada mayúscula, de forma que todos los %A;!,*! anteriores los podamos resumir en una única sentencia del tipo:

"/$)&7/(8-&9#*"#,&*C%$7%"!E B "/$)&7/(8-&9#*"#,&*C%$7%"!E = >@ Hacedlo, declarando el vector directamente dentro del -&%$. Finalidad: Acceder a las componentes de un vector con unos índices que representen algo. Dificultad Baja.


RP-IV.7

RELACIÓN DE PROBLEMAS IV. Vectores 11. Sobre el ejercicio 10, construya una clase específica !"#$%!&'$()*+),$* que implemente los métodos necesarios para llevar el contador de las mayúsculas. Lo que 71 se pretende es que la clase proporcione los métodos siguientes:

-!.% /"+&010"#$ !"#0! 2+3$& 1$()*+),$4 ."# )$"#$*5$( 2+3$& 1$()*+),$4 El primer método aumentará en uno el contador de la correspondiente mayúscula y el segundo indicará cuántas hay. Modifique el programa principal para que cree un objeto de esta clase y llame a sus métodos para realizar los conteos de las mayúsculas. Finalmente, hay que imprimir en pantalla cuántas veces aparece cada mayúscula. Dificultad Media. 12. Construya una clase $1."! !10 !+!* para representar el camino seguido por el en el juego del ComeCocos (Pac-Man). Internamente debe usar un vector de +3$& como dato miembro privado. Tendrá métodos para subir, bajar, ir a la izquierda e ir a la derecha. Dichos métodos únicamente añadirán el carácter correspondiente 6*67 6867 6.67 6%6 al vector privado. Añada a la clase un método 9!*.+.!"'!-.1.0"#!* !"*0+)#.-!* que calcule la posición donde se encuentre la primera secuencia de al menos n movimientos consecutivos iguales a uno dado (que pasaremos como parámetro al método). Por ejemplo, en el camino de abajo, si n = 3 y el movimiento buscado es 6*6, entonces dicha posición es la 6.

:686768676.676*676*6768676*676*676*676*676.676.676%6;

Cree un programa principal que lea desde un fichero los caracteres que representan las posiciones hasta llegar a un punto (6<6), lea un carácter c y un entero n e imprima en pantalla la posición de inicio de los n movimientos iguales a c. Dificultad Baja. 13. Cread una clase 90&1)#$+.!" para representar una permutación de enteros. Para almacenar los valores enteros usaremos como dato miembro privado un vector clásico de enteros. La clase debe proporcionar, al menos, los siguientes métodos:

=".$%0 para añadir un número a la permutación. • >* !&&0+#$ para indicar si los valores forman una permutación correcta, es

•

decir, que contiene todos los enteros sin repetir entre el mínimo y el máximo de dichos valores. Por ejemplo, 2?7@7A7B7C4 es una permutación correcta pero no lo es 2D7D7A7B4 (tiene el D como valor repetido) ni tampoco 2D7A7C4 (le falta el B).

•

E)1F0+#)&$* para saber el número de lecturas de la permutación. Una permu-

tación de un conjunto de enteros tiene k lecturas, si para leer sus elementos en orden creciente (de izquierda a derecha) tenemos que recorrer la permutación k


RP-IV.8

RELACIÓN DE PROBLEMAS IV. Vectores veces. Por ejemplo, la siguiente permutación del conjunto {0, . . . , 8}: 408125367 necesita 3 lecturas. En la primera obtendríamos 0, 1, 2 y 3. En la segunda 4, 5, 6 y 7 y finalmente, en la tercera, 8. Cread un programa principal que lea desde un fichero los valores de la permutación e imprima el número de lecturas de dicha permutación. Dificultad Media. 14. La sucesión de Fibonacci de orden n es una secuencia de números en la que los dos primeros son el 0 y el 1. A partir del tercero, los elementos se calculan como la suma de los n anteriores, si ya hay n elementos disponibles, o la suma de todos los anteriores si hay menos de n elementos disponibles. Por ejemplo, la sucesión de Fibonacci de orden 4 sería la siguiente: 0, 1, 1, 2, 4, 8, 15, 29, . . . Definid una clase llamada !"#$%&&!. Para almacenar los enteros, se usará un vector de enteros. Al constructor se le pasará como parámetro el valor de n. Definid los siguientes métodos:

!$' ()'*%+),- para obtener el valor de n. • .#!/ 0%1&21%34!5)4#+,!$' '#6)- para que calcule los '#6) primeros •

elementos de la sucesión.

!$' 7#'%10%1&21%/#+,- que devuelva cuántos elementos hay actualmente almacenados (el valor '#6) del método anterior) • !$' 89)+!5#,!$' 8- para que devuelva el elemento 8-ésimo de la sucesión.

•

Escribid un programa que lea los valores de dos enteros, n y k y calcule, almacene y muestre por pantalla los k primeros términos de la sucesión de Fibonacci de orden n:

:::::: !"#$%&&! ;!"#$%&&!,$-< ;!"#$%&&!:0%1&21%34!5)4#+,8-< '#6) = ;!"#$%&&!:7#'%10%1&21%/#+,-<

>> '#6) = 8

;#4 ,!$' !="#$%&&!:89)+!5#,!- @@ B B< Dificultad Media.


RP-IV.9

RELACIÓN DE PROBLEMAS IV. Vectores 15. (Examen Septiembre 2012) La criba de Eratóstenes (Cirene, 276 a. C. Alejandría, 194 a. C.) es un algoritmo que permite hallar todos los números primos menores que un número natural dado n. El procedimiento consiste en escribir todos los números naturales comprendidos entre 2 y n y tachar los números que no son primos de la siguiente manera: el primero (el 2) se declara primo y se tachan todos sus múltiplos; se busca el siguiente número entero que no ha sido tachado, se declara primo y se procede a tachar todos sus múltiplos, y así sucesivamente. El proceso para cuando el cuadrado del número entero es mayor o igual que el valor de n. El programa debe definir una clase llamada

!"#$%#&'&% que contendrá:

• Como dato miembro debe declarar un vector privado (!)*$% tal que en la componente k se almacenará el primo k−ésimo (+,-.-/-0-1112). El cómputo de los primos se hará en el siguiente método. • El método 3$)4 5"6786"9"%#":)'# '; calcula los primos menores que '. Cuando se ejecute el método, se calcularán todos los primos menores que ', según el método de Eratóstenes descrito anteriormente. Para realizar esta tarea, tendrá que definir un vector local al método con todos los números menores que ' y procederá a tachar los no primos según el algoritmo de Eratostenes. Los números no tachados serán los primos y serán los que almacene en el dato miembro (!)*$%. • El método )'# <$#"65"6786"4$%:; devuelva cuántos primos hay actualmente almacenados. •

)'# =>&%)*$:)'# =; para que devuelva el =-ésimo primo.

El programa principal quedaría de la forma:

!"#$%#&'&% (!)*$%? )'# ' @ ABB? )'# '8*>(!)*$%? (!)*$%15"6786"9"%#":';? '8*>(!)*$% @ (!)*$%1<$#"65"6786"4$%:;? C$! :)'# )@B? )D'8*>(!)*$%? )EE; 7$8# DD (!)*$%1=>&%)*$:); DD F F? Dificultad Media. 16. Se van a gestionar las calificaciones de una clase formada por un número indeterminado de alumnos, aunque no superior a cien. Se pretende calcular la nota media final de cada alumno en base a cuatro calificaciones parciales con diferente peso.


RP-IV.10

RELACIÓN DE PROBLEMAS IV. Vectores El programa leerá, en primer lugar, los pesos que se asignan a las calificaciones parciales (se esperan expresados en tantos por cien). Comprobad que las asignaciones son correctas y en el caso de que no lo fueran, abortad la ejecución del programa. A continuación leerá para cada alumno: apellidos y nombre (todo junto, separando apellidos y nombre por una coma, leedlos en un dato de tipo !"#$%) y las cuatro calificaciones (números reales entre 0.0 y 10.0 separados por espacios en blanco u otros separadores). La lectura finaliza cuando se introduce el caracter & en la lectura de los apellidos y nombre de un alumno. Una vez almacenados todos los datos leidos se mostrará un listado de: apellidos y nombre y nota media para cada alumno. El listado estará ordenado según la nota media final de cada alumno. Reflexión: Piense cómo podría modificar el programa para que pueda considerar un número indeterminado de calificaciones (máximo 10). a) El número de calificaciones será el primer dato que se lea, seguido de los pesos asignados a cada calificación. b) A continuación del nombre de cada alumno aparecerán tantas calificaciones como indica el primer dato (número de pesos = número de calificaciones por alumno). Recomendaciones: a) Leer los datos usando la redirección de la entrada. Usad para ello un fichero de texto como el disponible en la página de la asignatura. b) Es muy importante, por simplificar el problema aunque sin restarle generalidad, que los apellidos y nombres de cada alumno ocupen una sóla línea, sin más datos. Las calificaciones, no obstante, podrían estar separados en varias líneas y por un número indeterminado de separadores. Dificultad Media. 17. (Examen Febrero 2013) Se está diseñando un sistema web que recolecta datos personales de un y, en un momento dado, debe sugerirle un nombre de 73 (). Dicho estará basado en el nombre y los apellidos; en concreto estará formado por los N primeros caracteres de cada nombre y apellido (en minúsculas, unidos y sin espacios en blanco). Por ejemplo, si el nombre es '($!)$#) *"+$,# ,) -).#$+ /"!0%+' y N=2, el nombre de sugerido será '+$1"2))"'. Debe tener en cuenta que el número de palabras que forman el nombre y los apellidos puede ser cualquiera. Además, si N es mayor que alguna de las palabras que aparecen en el nombre, se incluirá la palabra completa. Por ejemplo, si el nombre es '($+ 3(-4/5 60 .+ 7.+$,+' y N=4, entonces la sugerencia será


RP-IV.11


!"!#!$%&'(!)(!" (observe que se pueden utilizar varios espacios en blanco

para separar palabras).

Implemente la clase *+,-" que tendrá como único dato miembro el tamaño .. Hay que definir el método /+&-0-#! que recibirá una cadena de caracteres (tipo 123-",) formada por el nombre y apellidos (separados por uno o más espacios en blanco) y devuelva otra cadena con la sugerencia de .

#(!11 *+,-"4 %3-5!2'6 -"2 "7$8#!3!#2'3'18!8#+,'39 %7)(-#6 *+,-" :-"2 "7$'3+8#!3!#2'3'18!8#+,'3; 6"7$8#!3!#2'3'18!8#+,'3:"7$'3+8#!3!#2'3'18!8#+,'3; 4 < 123-", /+&-0-#!:123-", "+$)3'8#+$%('2+;4 ====== < <9 Los únicos métodos que necesita usar de la clase 123-", son 1->' y %71?8)!#@. Para probar el programa lea los caracteres de la cadena uno a uno con #-"=,'2:;, hasta que el introduzca el carácter A. Dificultad Media. 18. (Examen Septiembre Doble Grado 2013) Defina una clase B3!1' para almacenar un conjunto de caracteres (similar a la clase C'#7'"#-!/!3!#2'3'1 ). Defina un método para localizar la k-ésima palabra. Una palabra es toda secuencia de caracteres delimitada por espacios en blanco a izquierda y derecha. La primera palabra no tiene por qué tener espacios a su izquierda y la última no tiene por qué tener espacios a su derecha. Puede haber varios caracteres en blanco consecutivos. Si k es mayor que el número de palabras, se considera que no existe tal palabra. Por ejemplo, si la frase es 4D DED DED?DED-DED DED DED)DED-DED 1, la posición es 2. Si k = 2 la posición es 6. Si k = 3 la posición es -1.

D< . Si k =

Si la frase fuese 4D?DED-DED DED)DED-DED D< , entonces si k = 1, la posición es 0. Si k = 2 la posición es 3. Si k = 3 la posición es -1. 19. Sobre el ejercicio 18, añadid los siguientes métodos:

5+-& F(-$-"!G(!"#+1H"-#-!('1:; para borrar todos los blancos iniciales. • 5+-& F(-$-"!G(!"#+1B-"!('1:; para borrar todos los blancos finales. •


RP-IV.12


!" #$%&'()*+*,'*-./ que indique cuántas palabras hay en la frase. • 0( 1 2(''*)*+*,'*. !" 34&- %*/ para que borre la palabra 3-ésima. • 0( 1 5(0&')*+*,'*6 !*+. !" 34&- %*/ para desplazar la palabra 3•

ésima al final de la frase.

Dificultad Media. 20. (Examen Septiembre Doble Grado 2013) Defina la clase 7&8$&!8 *9!"&'(- análoga a 7&8$&!8 *:*'*8"&'&- . Defina lo que sea necesario para calcular el número de secuencias ascendentes del vector. Por ejemplo, el vector ;<=>=?=?=@=<=?A tie70 ne 4 secuencias que son ;<=>A= ;?=?=@A= ;
D(- − B1* ,$-8*1( − 0E B1*F = 18C* − B1* 0E18C*F − 0E B1*F

22. Escriba un programa que rellene una matriz de dimension 5GH46IJ K 5GH4:LJ con números pares, lea del una posición . =M/ y muestre por pantalla el valor de dicha posición. Nótese que es necesario controlar la posición introducida por el . Finalidad: Manejar matrices. Dificultad Baja. 23. En este ejercicio, no hay que construir ninguna clase ni función. Es un ejercicio sobre recorridos de una matriz declarada directamente en el %* !. Leed desde teclado dos variables $" +4N +*- y de una matriz de enteros de tamaño $" +4N +*matriz, se pide lo siguiente:

$" +48(+$%!*- y leed los datos K $" +48(+$%!*- . Sobre dicha

a) Calcular la traspuesta de la matriz, almacenando el resultado en otra matriz.


RP-IV.13

RELACIÓN DE PROBLEMAS IV. Vectores b) (Examen Septiembre 2011) La posición de aquel elemento que sea el mayor de entre los mínimos de cada fila. Por ejemplo, dada la matriz M (3 × 4), 9 2 7

7 18 9

4 2 1

5 12 5

el máximo entre 4, 2 y 1 (los mínimos de cada fila) es 4 y se encuentra en la posición (0, 2). c) Ver si existe un valor MaxiMin, es decir, que sea a la vez, máximo de su fila y mínimo de su columna. d) Leer los datos de otra matriz y multiplicar ambas matrices (las dimensiones de la segunda matriz han de ser compatibles con las de la primera para poder hacer la multiplicación) 24. En este ejercicio, no hay que construir ninguna clase ni función. Es un ejercicio sobre recorridos de una matriz. Para ahorrar espacio en el almacenamiento de matrices cuadradas simétricas de tamaño k × k se puede usar un vector con los valores de la diagonal principal y los que están por debajo de ella. Por ejemplo, para una matriz M = {mij } el vector correspondiente sería: {m11 , m21 , m22 , m31 , m32 , m33 , m41 , · · · , mkk } Declarar una matriz clásica !"#$% &'()*+,-./,-./ en el &'*0, asignarle valores de forma que sea cuadrada simétrica y construid el vector pedido. Haced lo mismo pero a la inversa, es decir, construir la matriz a partir del vector. Dificultad Media. 25. Se quiere construir un programa para realizar estadísticas sobre datos meteorológicos. Para ello, se dispone del registro de un conjunto de medidas tomadas en el aeropuerto de Granada a lo largo de los 3 últimos meses. Para simplificar el problema, supondremos que todos los meses tienen treinta días, por lo que el número de días sobre los que se tienen datos es 90. Las medidas vienen organizadas de la siguiente forma: temperatura a las 07h de la mañana, temperatura a las 13h (ambas en grados centígrados) y precipitaciones en mm, todas ellas enteras. Para facilitar la prueba del programa, se ha preparado un fichero de datos llamado &%(%!1234, que puede descargarse desde %23'*. Se pide hallar el valor medio, el máximo y el mínimo mensual de cada una de las tres medidas. También debe calcular el valor medio, valor máximo y el mínimo mensual de la amplitud de las temperaturas esto es, la diferencia de temperatura que hay entre las 13h y las 07h.


RP-IV.14

RELACIÓN DE PROBLEMAS IV. Vectores Defina la clase !"!# que contendrá como dato miembro una matriz de enteros con los datos metereológicos. Defina un método para añadir los cuatro datos correspondientes a un día. 26. Escribir un programa que permita a dos jugadores jugar al tres-en-raya. El programa preguntará por los movimientos alternativamente al jugador $ y al jugador %. El programa mostrará las posiciones del juego como sigue: 1 2 3 4 5 6 7 8 9 Los jugadores introducen sus movimientos insertando los números de posición que desean marcar. Después de cada movimiento, el programa mostrará el tablero cambiado. Un tablero de ejemplo se muestra a continuación.

$ $ % 4 5 6 % 8 9 El programa detectará al final de la partida si hay o no empate y en caso contrario, qué jugador ha ganado. Además, pedirá empezar una nueva partida y reiniciar el proceso. Finalidad: Practicar con el uso de matrices sencillas en una aplicación. Dificultad Media. 27. Escribir un programa para asignar asientos de pasajeros en un avión. Asumimos un avión pequeño con la numeración de asientos como sigue: 1 2 3 4 5 6 7

A A A A A A A

B B B B B B B

C C C C C C C

D D D D D D D

El programa mostrará con una $ el asiento que está ya asignado. Por ejemplo, después de asignar los asientos 1A, 2B, y 4C, lo que se mostrará en pantalla tendrá un aspecto como este:


RP-IV.15


1 2 3 4 5 6 7

A A A A A A

B C C B C B B C B C B C

D D D D D D D

Después de mostrar los asientos disponibles, el programa pregunta por el asiento deseado, el teclea un asiento y el programa actualiza la asignación mostrando el esquema anterior. Primero se pide el número de fila y después la letra de asiento. Esto continua hasta que todos los asientos se asignen o hasta que el indique que no quiere asignar más asientos (introduciendo el valor −1 en el número de la fila). Si el introduce un asiento ya asignado, el programa mostrará un mensaje indicando que el asiento está ocupado y volverá a solicitarlo. Finalidad: Practicar con el uso de matrices sencillas en una aplicación. Dificultad Baja. 28. (Examen Febrero 2015) En este ejercicio no hay que construir ninguna función o clase. Todo se programará en el !"#$. Defina dos matrices de reales %&#'#$"( 76 y )*"+#,"-" de tamaño ./ 0 1/. Lea desde teclado los valores de la matriz %&#'#$"(, obligando a que sea simétrica. Para ello, lea el número de filas n y a continuación introduzca los n × n datos de la matriz. Construya la matriz )*"+#,"-" acorde a las siguientes indicaciones: a) La tabla resultante será simétrica. b) Los valores de la diagonal principal de la tabla resultante serán iguales a los de la tabla original. c) Los valores del triángulo superior de la tabla resultante se calculan de la siguiente manera: si (i, j) es una posición en el triángulo superior de la tabla resultante, su valor es el valor medio de los valores que ocupan las posiciones de las columnas j, j + 1, . . . , n − 1 en la fila i de la tabla original. Dificultad Baja. 29. (Examen Septiembre 2015) Buscaminas es un juego muy conocido cuyo objetivo es encontrar todas las minas existentes en un tablero rectangular, sin abrir ninguna. Si el 77 jugador abre una mina, pierde la partida. Se pide definir la clase 2"3(4&%5*)6"7#$") conteniendo lo siguiente: a) Para representar el tablero se trabajará con una matriz de datos 50×30 en la que todas las filas tienen el mismo número de columnas y los datos son de tipo 3%%(. Contendrá un valor 8&*4 en caso de haber una mina en la casilla especificada


RP-IV.16

RELACIÓN DE PROBLEMAS IV. Vectores y !"#$ en caso contrario. Esta matriz será un dato miembro de la clase y al principio, todos los valores estarán a !"#$. b) Un método para incluir una mina en una determinada casilla. c) Un método que reciba las coordenadas (i, j) de una casilla y devuelva un valor entero que indique el número de minas que rodean a la misma (será un número entre 0 y 8). En caso de que la casilla contenga una mina, se devolverá el valor −1. Hay que tener especial cuidado con las casillas que hay en los bordes de la matriz ya que la casilla en la posición %&'%&', por ejemplo, sólo tiene tres vecinos rodeándola. Incluya un pequeño programa de prueba para asignar algunas minas y obtener las minas que hay alrededor de algunas casillas. Dificultad Baja. 30. (Examen Febrero 2009) Sgeún un etsduio de una uivenrsdiad ignlsea, no ipmotra el odren en el que las ltears etsan ersciats, la úicna csoa ipormtnate es que la pmrirea y 78 la útlima ltera etsén ecsritas en la psioción cocrrtea. El rsteo peuden estar ttaolmntee mal y aún pordás lerelo sin pobrleams. Etso es pquore no lemeos cada ltera por sí msima snio la paalbra cmoo un tdoo. Diremos que dos palabras son similares si la primera letra de ambas palabras es igual, la última letra de ambas palabras también es igual y el resto de las letras son las mismas pero no están necesariamente en las mismas posiciones. De esta forma, las palabras ((!")*+($$ y ()(!"*$+($ son similares. Declare en el *!,+ dos objetos de la clase -$./$+.,!0!1!.($1$# y asígneles algunos caracteres de prueba. Implemente en el *!,+ un algoritmo que compruebe si los dos objetos son similares según el criterio anterior. Si lo necesita, puede añadir los métodos que estime oportunos a la clase -$./$+.,!0!1!.($1$#. Si le sirve de ayuda, utilice como base la descripción del siguiente algoritmo:

2#!1$*)# /+! #$./$+.,! 3$ "$(1!# 4! 51).$#!3!# 0)*5!1!1 "!# 51,*$1!# 4 6"(,*!# "$(1!# 3$ .!3! 5!"!71! -, #)+ ,8/!"$#9 :$.)11$1 $" 1$#() 3$ "$(1!#9 -, "! "$(1! +) $#(; $+ "! #$./$+.,! 3$ 51).$#!3!#9 <=!3,1"! ! 51).$#!3!# 0)+(!1 $" +6*$1) 3$ !5!1,.,)+$# 3$ "! "$(1! $+ .!3! 5!"!71! -, $" +6*$1) 3$ !5!1,.,)+$# $# 3,#(,+() rel="nofollow"> +) #)+ #,*,"!1$# Dificultad Media.


RP-IV.17

RELACIÓN DE PROBLEMAS IV. Vectores 31. Defina la clase !"#!$"%&'$(!)*+ análoga a !"#!$"%&,&)&"(!)!+ pero para que trabaje sobre enteros. Defina en el -&%$ un vector clásico de corchetes de tipo de 79 dato ".&). Lea desde el main varios caracteres y asígnelos al vector de ".&). Lea también varios enteros y asígnelos a un objeto de la clase !"#!$"%&'$(!)*+. Implemente ahora directamente en el -&%$ un algoritmo para que elimine eficientemente todas las posiciones indicadas en la secuencia de enteros. Por ejemplo, si el vector de caracteres contiene /#$0&-!$(*+, después de eliminar el conjunto de posiciones dado por 1 2 3, el vector se quedará como /#&!$(*+. Observe que una posibilidad sería sustituir los caracteres a borrar por un carácter especial, por ejemplo 4 y luego pasarle un algoritmo que eliminase todas las ocurrencias de 4. Sin embargo, nunca debemos recurrir a esta técnica ya que no podemos presuponer que tenemos la posibilidad de elegir tal carácter especial, ya que puede ser un carácter válido de la secuencia. Se recomienda implementar el siguiente algoritmo:

5(%6%7&) 0*+ 8$0%"!+9 :*+;!+")%(#)& < :*+;6!"(#)& =#! -&)=#!$ 6&+ :*+%"%*$!+ 0! 6!"(#)& < !+")%(#)& !$ !6 >!"(*) 0! ".&) ?)0!$&) 6& +!"#!$"%& 0! !$(!)*+ @!"*))!) "*$ :*+;6!"(#)& 6*+ "&)&"(!)!+ 0!6 >!"(*) 0! ".&) % !6 "&)A"(!) &"(#&6 $* !+(A !$ #$& :*+%"%B$ & C*))&)D "*6*"&)6* !$ :*+;!+")%(#)&E Dificultad Media. 32. (Examen Septiembre 2014) Existe un método para la clase +()%$F de C++, denominado )!:6&"!, que cambia $ caracteres de una cadena "&0G, empezando en 80 una determinada posición :*+, por los caracteres presentes en una segunda cadena "&01. La llamada al método es "&0GE)!:6&"!H:*+D $D "&01I . Ejemplos del funcionamiento de )!:6&"! son:

+()%$F "&0GJK/#$0&-!$(&6 L)*F)&-&"%B$KM "&0GE)!:6&"!HND1DK*+ 0! 6&KIM OO K&6K PQ K*+ 0! 6&K OO R.*)& "&0G (%!$! K/#$0&-!$(*+ 0! 6& L)*F)&-&"%B$K "&0GE)!:6&"!HG1D2DK!$KIM OO K0! 6&K PQ K!$K OO R.*)& "&0G (%!$! K/#$0&-!$(*+ !$ L)*F)&-&"%B$K Puede observar que, dependiendo de la cadena a insertar y de las posiciones especificadas, la secuencia final puede ser más grande o más pequeña que la original. Se quiere realizar esta tarea pero directamente en el -&%$, trabajando sobre dos vectores de corchetes y sin ninguna clase. Se pide construir un programa que leerá caracteres hasta el terminador 4 y los almacenará en el primer vector y de nuevo leerá


RP-IV.18

RELACIÓN DE PROBLEMAS IV. Vectores caracteres hasta llegar a un segundo y almacenará los datos en el segundo vector. A continuación, el programa leerá dos enteros !"# y $ y procederá a reemplazar los $ caracteres que hay a partir de la posición !"# del primer vector, con los caracteres del segundo vector. Restricciones para este ejercicio: No se puede utilizar la clase #%&'$( en ninguna parte del programa, debe hacerse lo más eficiente posible y no puede utilizarse un tercer vector en el que se vaya almacenando el resultado, es decir, las modificaciones deben hacerse directamente sobre el primer vector. Dificultad Media.


RP-IV.19

RELACIÓN DE PROBLEMAS V. Clases (Segunda parte)

RELACIÓN DE PROBLEMAS V. Clases (Segunda parte) 1. Recuperad las implementaciones de las clases !"#$%&, '()*("#$&+,+)+-$, .+,/!"0(,("/+1 y .!1-,1-$, disponibles en el fichero 81 2+)!,134($*(#,+/135/66 disponible en -(/31+. Las tres primeras se han visto en clase de teoría. Con respecto al cuadrado, éste viene determinado por el punto correspondiente a la esquina inferior izquierda y por la longitud de cualquiera de sus lados (estos serán sus datos ). Supondremos que sólo representamos cuadrados cuya base es paralela al eje de las abscisas.

/7133 !"#$%&8 6,+91#(: -$!;7( 1;3/+31< -$!;7( $,-("1-1< 6!;7+/: 555555 =< /7133 '()*("#$&+,+)+-$8 6,+91#(: -$!;7( >?@A B?@A >?%A B?%< 6!;7+/: 555555 =< /7133 .+,/!"0(,("/+18 6,+91#(: -$!;7( /("#,$")+#!-< 6!;7+/: 555555 =< Definid sobre la clase .!1-,1-$ los siguientes métodos:


RP-V.1

RELACIÓN DE PROBLEMAS V. Clases (Segunda parte) • Métodos para calcular el área y el perímetro del cuadrado. • Obtener el punto central interior al cuadrado:

!"#$%& '("#)$*+

Para calcular las coordenadas basta sumar la mitad de la longitud del cuadrado a las coordenadas de la esquina inferior izquierda. • Obtener la circunferencia inscrita al cuadrado (la que está por dentro):

',)-!".()("-,/ ',)-!".()("-,/0"1-),#/*+

Esta circunferencia es la que tiene como centro el centro del cuadrado y como radio la mitad de la longitud del cuadrado. • Obtener la circunferencia circunscrita al cuadrado (la que está por fuera):

',)-!".()("-,/ ',)-!".()("-,/',)-!"1-),#/*+

Esta circunferencia es la que tiene como centro el centro del cuadrado y como radio, la longitud del segmento que une el centro con la esquina inferior izquierda. Obtened la longitud creando el objeto de la clase 2(34("#$&,),3,5$ y a continuación llamad al método 6$"3,#!5. • Determinar si un cuadrado tiene mayor área que otro. Complete el programa principal de prueba que se encuentra en el fichero

7,3!)/18($4(#),-/19-::

Finalidad: Trabajar con el constructor de copia y con métodos que devuelven objetos. Dificultad Baja. 2. (Examen Febrero 2012) Sobre el ejercicio anterior, implemente un método para determinar si un cuadrado contiene a otro. Un cuadrado C1 determinado por la esquina (x1 , y1 ) y la longitud l1 contiene a otro cuadrado C2 dado por (x2 , y2 ) y l2 si se cumple que x2 >= x1 y x2 + l2 <= x1 + l1 y y2 >= y1 y y2 + l2 <= y1 + l1 Finalidad: Pasar a un método de una clase un parámetro de la misma clase. Dificultad Baja. 3. Recupere la solución del ejercicio 28 de la Relación de Problemas IV. En este ejercicio se pedía construir una matriz suavizada promedio. Se quiere hacer lo mismo pero 83 sobre una clase ;/#),<'!/5)/5/=(/>(1 , por lo que debe implementar el siguiente método:

;/#),<'!/5)/5/=(/>(1 2!/?,(1 y el programa principal. Complete el código implementando el método 2!/?,

RP-V.2

RELACIÓN DE PROBLEMAS V. Clases (Segunda parte) 4. (Examen Febrero 2009) Recupere la solución del ejercicio 30 de la Relación de Problemas IV (palabras similares). 84 Sobre la clase !"#!$"%&'&(&")!(!* , definid un método que compruebe si la secuencia es similar a otra. Finalidad: Trabajar con métodos a los que se les pasa como parámetros objetos de la misma clase. Dificultad Baja. 5. (Examen Septiembre 2014) Recupere la solución del ejercicio 32 de la Relación de Problemas IV (Replace). Defina sobre la clase !"#!$"%&'&(&")!(!* el método +!,-&"! para que haga la tarea pedida. Tendrá que pasarle al método la posición inicial, el número de caracteres a eliminar y el objeto de la clase !"#!$"%&'&(&")!(!* conteniendo la secuencia de caracteres de reemplazo. Finalidad: Trabajar con métodos a los que se les pasa como parámetro y definen objetos locales de la MISMA clase. Dificultad Baja. 6. Recupere la solución del ejercicio 31 de la Relación de Problemas IV (elimina varios caracteres de una secuencia). Defina el método .-%/%$&0&(%1* sobre la clase !"#!$"%&'&(&")!(!* para que haga la tarea pedida. Tendrá que pasarle al método un objeto de la clase !"#!$"%&.$)!(1* con los índices de las posiciones a eliminar. Finalidad: Pasar como parámetro a un método un objeto de otra clase. Dificultad Media. 7. Se quiere calcular la moda de una secuencia de caracteres, es decir, el carácter que más veces se repite. Por ejemplo, si la secuencia fuese

23-3431343*343 34353431343*343 343"34313436343(343!343*37 los caracteres que más se repiten son 313 y 3*3 con un total de 3 apariciones. La moda sería cualquiera de ellos, por ejemplo, el primero encontrado 313. Sobre la clase !"#!$"%&'&(&")!(!* , se pide construir el método 815& que devuelva un *)(#") del tipo:

*)(#") 9(!"#!$"%&'&(&")!(2 ":&( "&(&")!(; %$) 6(!"#!$"%&; 7 en el que el campo "&(&")!( contendrá el carácter en cuestión (313) y en el campo 6(!"#!$"%& el conteo de la moda (3). Finalidad: Usar como dato local de un método un vector y devolver un cultad Baja.


*)(#"). Difi-

RP-V.3

RELACIÓN DE PROBLEMAS V. Clases (Segunda parte) 8. En el primer apartado del ejercicio 8 de la relación de problemas III se pedía eliminar los repetidos de un objeto de la clase !"#!$"%&'&(&")!(!* usando como dato auxiliar local un vector clásico con los elementos que no estuviesen repetidos. Recuperad la solución vista en clase y resolved este mismo apartado usando como dato auxiliar local un objeto de la propia clase !"#!$"%&'&(&")!(!* 9. (Examen Septiembre 2014) Sobre la clase !"#!$"%&'&(&")!(!* implemente el algoritmo Counting Sort para ordenar sus valores. El método no modificará las componentes del vector privado sino que debe construir una secuencia nueva y devolverla. El algoritmo funciona de la siguiente forma: • Calculad los caracteres mínimo y máximo del vector. Por ejemplo, si el vector contiene

" + + & + " " & , " + , " el mínimo es -&- y el máximo -,-. • Construid un vector auxiliar de frecuencias con los conteos de todos los caracteres que hay entre el mínimo y el máximo. Con el ejemplo anterior, el vector de conteos será

. / 0 1 1 1 . que corresponden a las frecuencias de las letras que hay entre -&- y -,-. • Recorrer el vector de frecuencias almacenando cada carácter tantas veces como indique su frecuencia (2 veces el -&-, cuatro veces el -+-, etc)

& & + + + + " " " " " , , Haced lo mismo pero parametrizando el método '2#$)%$, 2() para que ordene sólo los valores de la secuencia que hay entre un carácter %34#%!(5& y otro carácter 5!(!"6&. Por ejemplo, si %34#%!(5& 7 -+- y 5!(!"6& 7 -,- el resultado sería:

+ + + + " " " " " , , Finalidad: Trabajar con métodos con vectores locales y devolviendo un objeto de la misma clase. Dificultad Media. 10. Definid la clase 8&)(%39!")&$,#:&(;$)!(2* usando una matriz de doble corchete como dato miembro privado.

%$) <&)(%3=>(%?&5&@8ABC8D=ECFA G@8ABC8D='DFH8IA GJ Definid métodos para: a) Obtener el número de filas y columnas utilizadas, así como el dato que haya en una fila y columna.


RP-V.4


!"#!$"%&'$(!)*+. c) Añadir una fila entera. La fila será un objeto de la clase !"#!$"%&'$(!)*+.

b) Devolver una fila completa como un objeto de la clase d) Comprobar si es igual a otra matriz. e) Obtener la traspuesta.

f ) Comprobar si es simétrica. Hacedlo primero calculando la traspuesta de la matriz y viendo si es igual a su simétrica, usando los métodos anteriores. Hacedlo también comprobando directamente si cada componente es igual a su simétrica y parando el recorrido en cuanto encuentre una componente que no lo verifique. g) Multiplicar dos matrices. Finalidad: Trabajar con matrices. Dificultad Baja. 11. Sobre el ejercicio anterior, construid un método que busque la fila de la matriz que más se parezca a una secuencia de enteros, a la que llamaremos )!,!)!$"%&. La similitud entre dos secuencias x = (x1 · · · xp ) e y = (y1 · · · yp ) vendrá dada por la distancia euclídea entre ambas: q dist(x, y) = (x1 − y1 )2 + · · · + (xp − yp )2 Además, la búsqueda solo se hará sobre las filas de la matriz enumeradas en una segunda secuencia llamada ,%-&+.&."*/0&)&). Por ejemplo, dada la matriz M (7 × 4), → → → →

3 4 5 7 4 2 7

1 5 7 9 9 8 3

0 1 1 6 5 2 2

8 5 7 1 5 2 5

y las secuencias )!,!)!$"%& = 2, 8, 1, 1 y ,%-&+.&."*/0&)&) = 0, 2, 4, 5, el programa deberá encontrar 5 como la fila más cercana a )!,!)!$"%&. En el dibujo anterior se han marcado con una flecha las filas indicadas por ,%-&+.&."*/0&)&). Finalidad: Trabajar con matrices. Dificultad Media. 12. (Examen Septiembre 2013) Sudoku es un juego muy popular que consiste en rellenar una cuadrícula de 9 × 9 celdas que está dividida en subcuadrículas de 3 × 3 (denominadas regiones) con cifras del 1 al 9. Un sudoku se considera resuelto si verifica que:


RP-V.5

RELACIÓN DE PROBLEMAS V. Clases (Segunda parte) • En cada fila aparecen todos los números del 1 al 9 (sin repetir)

• En cada columna aparecen todos los números del 1 al 9 (sin repetir) • En cada región aparecen todos los números del 1 al 9 (sin repetir)

Realizar un programa que lea todos los elementos de un sudoku y determine si está resuelto o no. Un ejemplo de sudoku resuelto es el siguiente:

Implemente la solución con una clase !"#$! con un dato miembro matriz de doble corchete y añada un programa principal de prueba. Finalidad: Trabajar con matrices. Dificultad Media. 13. (Examen Febrero 2013) Se quiere trabajar con una tabla de datos en el que todas las filas tienen el mismo número de columnas y los datos son de tipo %&'. Esta clase se llamará ()*+,&-.*&/#0,+1# y contendrá valores enteros que representan un nivel de gris (0 sería negro y 255 blanco). Se supone que todos los valores deben ser positivos aunque por problemas de captación y registro algunos de ellos son negativos. Es preciso corregir estos valores erróneos y se propone sustituirlos por el valor promedio de sus ocho vecinos más cercanos espacialmente (arriba, abajo, izquierda, derecha y esquinas). Debe considerar que entre estos vecinos pudiera haber valores negativos, y en este caso no intervendrán en el cálculo del valor promedio: Si hubiera un sólo valor negativo en la vecindad, se sumarán los valores de los 7 vecinos válidos y la suma se dividirá entre 7. Si hubiera dos valores negativos en la vecindad, se sumarán los valores de los 6 vecinos válidos y la suma se dividirá entre 6. . . . Si no hubiera ningún valor válido, se sustituirá por un cero. Implemente un método para que dada una imagen, devuelva otra imagen corregida. La imagen original no se modifica. Para la implementación debe considerar: a) El algoritmo debe ser simple y claro.


RP-V.6

RELACIÓN DE PROBLEMAS V. Clases (Segunda parte) b) Para simplificar el problema, las casillas de los bordes no se modifican, aunque sí se usan para efectuar las correcciones oportunas. En definitiva, la primera y la última fila así como la primera y la última columna son iguales entre la matriz original y la corregida. Cread un programa principal de prueba. Finalidad: Trabajar con matrices. Dificultad Media. 14. (Examen Septiembre 2012) Definid la clase !"#$%&'%!(')*'%'"#!%+,#!%$ que permite almacenar un conjunto de parejas de la forma -"'%."#!%/ !,#!%$0. Cada pareja será un struct &'%!('*'%'"#!%+,#!%$ con un campo de tipo carácter y otro campo de tipo entero.

)#%1"# &'%!('*'%'"#!%+,#!%$2 "3'% "'%'"#!%4 5,# 6!"!)4 7 Se pide crear un método de la clase 8!"1!,"5'*'%'"#!%!) al que se le pasará como parámetro un objeto de la clase !"#$%&'%!(')*'%'"#!%+,#!%$ para que borre cada uno de los caracteres que aparecen en el vector de parejas, tantas veces como indique el entero correspondiente. Por ejemplo:

9$%%'% -2-'/:0/-;/<070 !, 2'/;/'/;/"/'/;/=/'7 >? 2'/"/'/;/=/'7 Finalidad: Trabajar con vectores de struct. Dificultad Media. 15. (Examen Septiembre 2013) Se quiere almacenar el nombre de un alumno junto con las notas que ha sacado en varias asignaturas. El número de asignaturas puede variar de un alumno a otro y las notas son de tipo de dato entero. Con estos datos, se quiere construir un conjunto de alumnos

@,' =! A$;!%/ -B/C/D/B0 8!%E5$ A'%"F'/ -G/H/<0 I'65= J$=%5E1!K/ -L/H0 Defina la clase @M1N,$) que contendrá los siguientes datos miembro:

8!"1!,"5'*'%'"#!%!) con los nombres de los alumnos: O 2@,' =! A$;!%7 / 28!%E5$ A'%"F'7 / 2I'65= J$=%5E1!K7 P • Un vector de 8!"1!,"5'+,#!%$) con las notas de cada alumno: O 2B/C/D/B7 / 2G/H/<7 / 2L/H7 P

• Un vector de

Añada métodos para:


RP-V.7

RELACIÓN DE PROBLEMAS V. Clases (Segunda parte) • Obtener el número total de alumnos

• Obtener el nombre de un alumno. Al método se le pasará un índice de componente y devolverá un objeto !"#!$"%&'&(&")!(!* . • Obtener todas las notas de un alumno. Al método se le pasará un índice de componente y devolverá un objeto !"#!$"%&+$)!(,*. • Obtener los alumnos cuyo nombre contenga una determinada cadena de caracteres. Al método se le pasará un objeto !"#!$"%&'&(&")!(!* y devolverá un objeto !"#!$"%&+$)!(,* con las posiciones correspondientes. • Ordenar los datos de menor a mayor según la media aritmética de sus calificaciones. Con los datos del anterior ejemplo, la nota media de -$& .! /,0!( sería 8.25, la de !1%, /&("2& 3 y la de 3&4%. 5,.(%1#!6 4.5 , por lo que los datos ordenados quedarían como sigue:

!(1%, /&("2&7 897:7;< 3&4%. 5,.(%1#!67 8=7:< -$& .! /,0!(7 8>7?7@7>< • Cread un programa principal sencillo de prueba. Finalidad: Trabajar con vectores de objetos. Dificultad Media. 16. En las transparencias se enfatiza que las tareas necesarias para realizar las operaciones de E/S de los datos de un objeto, se realizarán en clases específicas que implementen dichas responsabilidades. Vamos a aplicarlo sobre la clase sendas clases:

!"#!$"%&'&(&")!(!*. Para ello, vamos a crear

• La clase ABC(!*,( !"#!$"%&'&(&")!(!* servirá para imprimir los caracteres de un objeto de la clase !"#!$"%&'&(&")!(!* . Si la secuencia contiene los caracteres D , E &, por ejemplo, en pantalla saldrá lo siguiente:

FD7,7E7&G En general, se dará la posibilidad de delimitar los caracteres con otros símbolos que no sean F G 7 La clase ABC(!*,( !"#!$"%&'&(&")!(!* contendrá el siguiente método:

4,%. ABC(%B! 8 !"#!$"%&'&(&")!(!* *!"#!$"%&H&H%BC(%B%(< • La clase I!"),( !"#!$"%&'&(&")!(!* para leer los datos de un objeto de la clase !"#!$"%&'&(&")!(!* . La lectura de datos parará cuando se llegue a un terminador, que será un carácter especial. La clase I!"),( !"#!$"%&'&(&")!(!* contendrá al menos el siguiente método:

!"#!$"%&'&(&")!(!* I!!8< Guión de Prácticas. Fundamentos de Programación

RP-V.8

RELACIÓN DE PROBLEMAS V. Clases (Segunda parte) que será el encargado de hacer la lectura de los datos y construir un objeto de la clase !"#!$"%&'&(&")!(!* . Cread un programa principal que vaya leyendo datos de un fichero. El fichero contendrá al principio el número de filas de caracteres que hay y a continuación las filas. Cada fila será una serie de caracteres con un punto al final (éste es el terminador de la fila).

+ ,*)- !* #$& .%/&0 ,*)& !* -)(&0 1!("!(& 2 3/)%4& .%/&0 Para

realizar

la

lectura

se

usará

un

único

objeto

de

la

clase

de

la

clase

5!")-( !"#!$"%&'&(&")!(!* . Cada fila se almacenará en un objeto de la clase !"#!$"%&'&(&")!(!* . Cada vez que leamos una fila la añadiremos a un objeto de la clase 1!6)-. Utilizad la implementación incluida en las transparencias en el apartado Tabla dentada usando un vector de objetos, bajo el nombre 1!6)-78*9. Este objeto 1!6)- habrá que definirlo en la función 4&%$. Una

vez

leídas

todas

las

filas,

crearemos

un

objeto

:4;(!*-( !"#!$"%&'&(&")!(!* y lo usaremos para imprimir por pantalla

todas las filas.

Finalidad: Trabajar con clases cuya responsabilidad es realizar las tareas de E/S. Dificultad Media. 17. Sobre la base del ejercicio 16, construid una clase :4;(!*-(1!6)- para que imprima un objeto de la clase 1!6)-. Finalidad: Trabajar con clases cuya responsabilidad es realizar las tareas de E/S. Dificultad Baja. 18. Sobre la base del ejercicio 15 (conjunto de alumnos), definid una clase :4;(!*-(

RP-V.9

RELACIÓN DE PROBLEMAS V. Clases (Segunda parte) • Debe incluir la definición de los datos y la implementación del constructor de todas las clases que necesite. • Debe incluir las cabeceras de los métodos necesarios para resolver el problema, pero no tiene que incluir la implementación de dichos métodos. • Debe incluir la implementación del método que comprueba la intersección, pero no tiene que incluir la implementación de los métodos invocados dentro de él. 20. (Examen Septiembre 2012) Definid la clase !"#$"%!&'()"*(! para que permita almacenar una secuencia ordenada de números enteros sin repetidos. Definid métodos para: • Añadir un entero (de forma ordenada y sin almacenar repetidos).

• Calcular la unión con otro conjunto. En la unión se deben incluir los elementos que estén en cualquiera de ellos. • Calcular la intersección con otro conjunto. En la intersección se deben incluir los elementos que sean comunes a ambos conjuntos. Cread un programa principal de prueba. Finalidad: Trabajar con métodos a los que se les pasa como parámetro y devuelven objetos de la misma clase. Dificultad Media. 21. Recuperad la solución al problema 12 del ComeCocos de la Relación de Problemas IV. Sobre la clase *+,"! !+) !-!., añadidle un método que compruebe si el conjunto de movimientos de un camino contiene a los movimientos de un segundo camino que se pasará como parámetro al método. Debe respetarse el orden en el que aparecen los movimientos, pero no tienen por qué estar consecutivos. Por ejemplo, el camino /0.010.0102010,010(010(03 contiene al camino /0.010,03 pero no al camino /0,010.03. Puede usarse la sobrecarga del método 4,"( de la clase .%',"5 a la que se le pasa como parámetro la posición inicial desde la que se realiza la búsqueda:

.%',"5 -*()"* 6 78!9*1 .!: :!7; ,"% 0!01?@; AA B CD E',+)'* !-$'')"-,* () 0!0 AA * <*'%,' () 9* 0!01G@; AA G 0801G@; AA CG H! )"-!"%'*(!= Finalidad: Pasar a un método de una clase un parámetro de la propia clase. Dificultad Baja. 22. (Examen Septiembre 2012) Se quiere desarrollar una aplicación para automatizar la realización de exámenes tipo test. El software incluirá una clase IJ*+)" que debe almacenar: el nombre de la asignatura, la lista de enunciados de las preguntas (cada


RP-V.10

RELACIÓN DE PROBLEMAS V. Clases (Segunda parte) enunciado es una cadena de caracteres de tipo !"#$%) y la lista de respuestas correctas para cada pregunta (cada respuesta es un carácter). Implementa la clase junto con los siguientes métodos: • Un constructor que inicialice un objeto de tipo asignatura y con la lista de preguntas vacía.

&'()*$ dando el nombre de la

• Un método +,*-(."*%,$!( que reciba un enunciado y la respuesta correcta y que los añada a la lista de preguntas del examen. Cada nueva pregunta siempre se añade al final de la lista. • Un método +,)."*%,$!( que devuelva el número de preguntas de que consta el examen. • Un método &$,$/#(01 que devuelva el enunciado de la pregunta i-ésima. • Un método 2*

3,* !( que devuelva la respuesta de la pregunta i-ésima.

A continuación, se pide realizar un programa que permita evaluar a una serie de alumnos utilizando la clase &'()*$. El programa comenzará creando un objeto de tipo &'()*$ y dándole contenido, es decir, leyendo las preguntas y respuestas correctas desde la entrada estándar y almacenándolas. Una vez leído el examen se procederá a la evaluación de un número de alumnos dado desde la entrada estándar. Para ello el programa le mostrará las preguntas del examen a cada alumno y leerá sus respuestas. Al finalizar cada alumno la prueba, el programa le dirá su nota de acuerdo a los siguientes criterios: • Por cada pregunta sin responder se suman 0 puntos. • Por cada respuesta correcta se suma 1 punto.

• Por cada respuesta incorrecta se resta 1 punto.

• La nota final estará en el intervalo [0, 10]. Un 10 significa que ha respondido y acertado todas las preguntas. Si la calificación es negativa se sustituye por cero. No es necesario almacenar las notas de los alumnos ya que se pueden ir mostrando al terminar cada uno de ellos la prueba. Además, se pueden añadir nuevos métodos a la clase &'()*$ si lo considera oportuno. 23. (Examen Septiembre 2009) Sobre la clase 4*/,*$/#(5("(/!*"* , añadid un método que determine si dicha secuencia de caracteres C1 contiene a otra secuencia C2 en el mismo orden (no tienen que estar consecutivos) y de forma cíclica. Para que se cumpla este criterio se deben satisfacer las siguientes condiciones • Todos los caracteres de C2 deben estar en C1

• Deben estar en el mismo orden aunque no de forma consecutiva

• Si durante la búsqueda se ha llegado al final de la secuencia C1, se debe proseguir la búsqueda por el inicio de C1, pero sin sobrepasar la posición en la que hubo la primera concordancia.


RP-V.11

RELACIÓN DE PROBLEMAS V. Clases (Segunda parte) Se muestran algunos ejemplos en los que la secuencia C1 contiene a C2: • C1 = xzayobnmwqdfg

• C1 = ftkxqdhjzaxqoblki

C2 = abcd C2 = abcd

• C1 = tzsbluyclpygdmngrafvc

C2 = abcd

Hay que destacar que la primera letra de C2 a buscar en C1 podría estar en cualquier sitio. Por ejemplo, para el siguiente caso: • C1 = bghcjadxak

C2 = abcd

podemos ver que a partir de la primera a de C1 no podemos encontrar C2 de forma cíclica, aunque sí lo podemos hacer a partir de la segunda a de C1. También puede darse el caso de que C1 no contenga a C2 de forma cíclica aunque incluya todas sus letras, como muestra el siguiente ejemplo: • C1 = tzsbluyclpcaygdmxngrfvc

C2 = abcd

24. Recuperad la clase !"#$%&'("!)*+,!#-)"'#./ (ejercicio 10 de esta relación). Definid un método que ordene las columnas en función de la media aritmética de cada una de ellas. Así pues, después de aplicar el método, la media de la columna $ será menor o igual que la media de la columna 0 para cualquier $ 1 0. 25. (Examen Septiembre 2005) Recuperad la clase !"#$%&'("!)*+,!#-)"'#./ (ejercicio 10 de esta relación). Supongamos que cada casilla representa un enlace a una casilla de la siguiente fila. Dicho enlace es únicamente un entero que indica un índice de columna de la siguiente fila, de forma que una casilla de la última fila enlaza con otra casilla de la primera fila. Suponiendo que la matriz tiene datos correctos (no hay valores imposibles de columnas y todos los valores de una fila son distintos), se pide construir un método que calcule cuantos ciclos hay, es decir, cuantos caminos hay que empiecen en un valor de la primera fila y siguiendo los enlaces, se llegue de nuevo al mismo valor de la primera fila. Por ejemplo, en la matriz de abajo hay un total de dos ciclos (uno pintado con flechas y otro más sin pintar).


RP-V.12

RELACIÓN DE PROBLEMAS V. Clases (Segunda parte) 26. (Examen Febrero 2009) Recuperad la clase !"#$%&'#( vista en clase de teoría en el apartado Tabla rectangular usando una matriz. Queremos definir una medida de similitud entre dos sopas de letras M1 y M2 cuadradas n × n de la siguiente forma: S(M1 , M2 ) = |M1 ∩ M2 | + np donde np es el número de posiciones (i, j) (i = 1, · · · , n y j = 1, · · · , n) en las que M1 y M2 tienen el mismo elemento. Por ejemplo, dadas las siguientes sopas de letras: M1 =

x n

i k

M2 =

n q

i p

entonces S(M1 , M2 ) = 2 + 1 = 3, ya que tienen dos caracteres en común (i y n) y una posición (i = 1 y j = 2) en la que ambas sopas tienen el mismo carácter. Definid un método que implemente el cómputo de esta medida de similitud. 27. (Examen Febrero 2013) Queremos representar un conjunto de equipos de tenis de mesa participantes en un torneo. Únicamente queremos almacenar el nombre de cada uno de ellos en un (&')*+. Se desea construir el conjunto de todos los emparejamientos posibles. Por ejemplo, si se parte del conjunto { Albolote, Motril, Baza, La Zubia } quiere construirse el siguiente conjunto de emparejamientos: {{Albolote, Motril} , {Albolote, Baza} , {Albolote, La Zubia} , {Motril, Baza} , {Motril, La Zubia} , {Baza, La Zubia}} Para resolver este problema definiremos la clase %,-%*,)# &')*+ para representar una secuencia de datos de tipo (&')*+ y crearemos en el programa principal un objeto %.-)"!( de esta clase. Debe definir también la clase %,-%*,)#/#'%0#( &')*+ para poder representar un conjunto arbitrario de parejas de (&')*+. Lo más fácil es utilizar como dato miembro privado un vector clásico de corchetes en el que cada componente es un registro del siguiente tipo:

(&'-,& /#'%0# &')*+1 (&')*+ ,#2%*#3)42#5 (&')*+ ,#2%*#32,6#5 75 Tenga en cuenta que el número de equipos puede ser cualquiera (no sólo 4 como en el ejemplo) Finalidad: Trabajar con un vector de struct. Dificultad Baja. 28. (Examen Febrero 2013) Para gestionar un campeonato de n equipos se utiliza una matriz de tamaño n × n (el máximo número de equipos que se permite es 20, pero Guión de Prácticas. Fundamentos de Programación

RP-V.13

RELACIÓN DE PROBLEMAS V. Clases (Segunda parte) podría haber menos de 20). En cada posición de esta matriz se pueden almacenar tres posibles valores !"!# !$!# !%!&. La fila f y columna c contendrá un valor correspondiente al partido que enfrenta al equipo f con el c, de forma que si vale !"! indica que ha ganado f , si vale !$! han empatado y si vale !%! ha ganado c. 0 0

1

2

3

4

1

1

1

2

X

X

1

1

2

1

2

2

1

X

3

2

X

1

4

1

2

X

X 2

Liga de 5 equipos: 1: Gana fila 2: Gana columna X: Empate Partido 2 contra 4: Gana 4 Partido 3 contra 4: Empate Partido 4 contra 2: Empate Diagonal principal no se usa

Observe que dados dos equipos (m, n) habrá dos partidos: uno en el que se enfrentan m y n y el recíproco, de n con m. Además, el valor de la diagonal no se usa, ya que no existe el partido n contra n. Se pide crear una clase '()* para manejar esta información. La clase debe contener un método que construya una secuencia de enteros con los resultados finales de la liga. Estos resultados contabilizan, para cada equipo, los puntos obtenidos: la componente 0 contendrá los puntos del primer equipo, la componente 1 los del segundo y así sucesivamente. Tened en cuenta que una victoria implica 3 puntos, un empate 1 punto, y una derrota 0 puntos. • Para representar la matriz de datos, utilice el tipo de tabla que considere más adecuado (según lo visto en las transparencias) • Cread también la clase +,-,.*/0.'()* con un método que permita leer los datos de los resultados de los equipos desde un fichero y construya el objeto '()*.

12*33 +,-,.*/0.'()*4 5672(18 '()* ',, &4 999999 : :; • Cread un programa principal que lea los datos de la liga, obtenga los puntos y los imprima por pantalla.


RP-V.14

RELACIÓN DE PROBLEMAS V. Clases (Segunda parte) 29. Vamos a usar una clase para generar números enteros aleatorios entre un mínimo y un máximo con la siguiente interfaz pública:

!"#$%&' ( !"#$%&')*$+ '*$*'&, *$+ '#-*'&. ( *$+ /0-+). ( *$+ *$). ( *$+ #-). Puede usarse cualquiera de las implementaciones que vienen a partir de la página RPV.16 (copie y pegue el código de dicha clase en su programa). Para generar 10 números aleatorios entre 4 y 7, por ejemplo, bastaría hacer lo siguiente:

!"#$%&' 10$02#%&23#40#+&2*&)5, 6.7 8&2 )*$+ *9:7 *;<:7 *((. =&>+ ;; 10$02#%&23#40#+&2*&?/0-+).7 Hay que destacar lo siguiente: • Cada llamada a 10$02#%&23#40#+&2*&?/0-+). genera un valor aleatorio (entre 4 y 7 en el ejemplo) • Los valores generados pueden repetirse antes de que se hayan generado todos los posibles valores. Por lo tanto, una posible secuencia de números generados podría ser la siguiente: @ 5 @ A 5 6 5 @ Se pide crear la clase B0$02#%&2C02'>+#=*&$0D para generar permutaciones aleatorias de un conjunto de enteros entre un valor mínimo y un valor máximo. La clase tendrá un único método con la siguiente cabecera:

C02'>+#=*&$ B0$02#)*$+ E2*'02&, *$+ >4+*'&. dónde la clase C02'>+#=*&$ es la vista en el problema 13 de la relación de problemas IV. Por ejemplo, si mínimo = 1 y máximo = 6, una permutación válida sería FG,<,A,5,@,H,GI. Como puede observarse, no pueden aparecer elementos repetidos y deben estar todos los valores entre 1 y 6.


RP-V.15


Apéndice: Clase MyRandom Proporcionamos dos posibles implementaciones de la clase meros enteros aleatorios entre un mínimo y un máximo.

!"#$%&' para generar nú-

Opción 1. Siguiendo el nuevo estándar de C++ 11.

()$*+,%- ./#$%&'0 ()$*+,%- .*8/&$&0

11 2#/# +# 3-$-/#*)4$ %- $5'-/&6 26-,%&#+-#7&/)&6 11 2#/# +# 6-')++#

*+#66 9-$-/#%&/:+-#7&/)&;$7-/&6< 2/)=#7-> '7?@@AB 3-$-/#%&/C'-/6-$$-D 11 -/6-$$- 7E)67-/ ,$)F&/'C)$7C%)67/)G,7)&$.)$70 %)67/)G,*)&$C,$)F&/'-D 2,G+)*> 9-$-/#%&/:+-#7&/)&;$7-/&6HI >9-$-/#%&/:+-#7&/)&;$7-/&6HJK ?I< L 9-$-/#%&/:+-#7&/)&;$7-/&6H)$7 ')$K )$7 '#MI< #,7& 6-')++# N *8/&$&>>8)38C/-6&+,7)&$C*+&*O>>$&EHIP7)'-C6)$*-C-2&*8HIP*&,$7HID 3-$-/#%&/C'-/6-$$-P6--%H6-')++#ID %)67/)G,*)&$C,$)F&/'- N ,$)F&/'C)$7C%)67/)G,7)&$.)$70 H')$K '#MID L )$7 Q)3,)-$7-HI< /-7,/$ %)67/)G,*)&$C,$)F&/'-H3-$-/#%&/C'-/6-$$-ID L LD


RP-V.16

RELACIÓN DE PROBLEMAS V. Clases (Segunda parte) Opción 2. A la antigua usanza, para aquellos compiladores que no proporcionen la biblioteca !"#$%.

&'"()*#+ ,(-.#)'/0 &'"()*#+ ,(.'%+0

11 2!3 4*+ '"()*'

+-.!- /'/)'$.+(!-

()!-- 536!"#$% 7 8 '9!.+: '". %'";!)< '". %!=;!)< 9$'# >"'.536!"#$% ?9$'#@ 7 .'%+A. .< - !"# ??'".@ .'%+?B.@@<

11 >"'('!)'C! +) D+"+ !#$ 11 ($" +) +)$E #+) -'-.+%!

F 8*/)'(: 536!"#$% ?'". +)A%'"'%$G '". +)A%!='%$@ : %'";!)?+)A%'"'%$@G %!=;!)?+)A%!='%$@ 7 >"'.536!"#$%?@<

'". "$A)$A*-$ H I+=.?@< 11 #+-+(J$ +) 8 '%+ $ F '". I+=.?@ 7 '". !"D$ H ?%!=;!) K %'";!)@LM< '". 9M H !"D$ N ? !"#?@ 1 ?6OIPA5OQNMRS@@< '". 9T H %'";!) L ?9M U !"D$@< +.* " 9T<

F '". 5'"?@ 7 +.* " %'";!)< F '". 5!=?@ 7 +.* " %!=;!)< F


RP-V.17

Ejercicios Programacion h1i4r

Overview 26281t

More details 6y5l6z

Related Documents 3h463d

Ejercicios Programacion h1i4r

Ejercicios De Programacion Lineal 4c3r17

Ejercicios Resueltos Programacion Dinamica 5i4c39

Ejercicios Resueltos Programacion Lineal 6q1f3z

Programacion Lineal Ejercicios Resueltos 74w1f

Ejercicios Programacion Lineal 37163c