Download LENGUAJES DE PROGRAMACIÓN Trabajo Práctico

LENGUAJES DE PROGRAMACIÓN
Trabajo Práctico - Septiembre de 2016
INSTRUCCIONES
– El trabajo práctico debe realizarse de manera individual. No debe realizarse
en grupo. Se penalizará cualquier uso compartido de las soluciones propuestas y de los códigos programados.
– El trabajo debe entregarse a través del curso virtual de la asignatura en la
plataforma Alf.
– La fecha límite de entrega es el día 10 de septiembre.
– El alumno debe entregar un fichero comprimido, en formato zip o tar, que
contenga:
◦ Una memoria en la cual explique la solución a los ejercicios, incluyendo los listados documentados del código C++ desarrollado. Este
documento deberá estar en formato pdf.
◦ Los ficheros del código fuente C++ solución a los ejercicios.
No deben entregarse ficheros ejecutables.
El nombre del fichero comprimido debe ser la concatenación del nombre y
apellidos del alumno. Por ejemplo, LuisaGomezMartin.zip
LENGUAJES DE PROGRAMACIÓN
CRITERIOS DE EVALUACIÓN
– Para que el trabajo pueda ser corregido, es imprescindible que el alumno
entregue dentro del plazo establecido un fichero comprimido que contenga
la memoria en formato pdf y el código fuente C++ de los ejercicios que haya
realizado.
– El trabajo se compone de 4 ejercicios, cada uno de los cuales se valorará
sobre 2.5 puntos.
– Para aprobar el trabajo es necesario que la nota total obtenida en los ejercicios sea mayor o igual que 5.
– Si el código solución de un ejercicio tiene errores de compilación o no tiene
la funcionalidad pedida, dicho ejercicio se valorará con cero puntos.
– Si el código solución de un ejercicio compila sin errores y tiene la funcionalidad pedida, la puntuación en dicho ejercicio será al menos de 2 puntos.
– Se valorará positivamente la eficiencia y la adecuada documentación del
código, así como la presentación y calidad de las explicaciones proporcionadas en la memoria.
2
Dpto. de Informática y Automática, UNED
TRABAJO PRÁCTICO - SEPTIEMBRE DE 2016
EJERCICIO 1
El método del punto fijo es un método para resolver una ecuación de la forma
f (x) = x
El método consiste en elegir un valor inicial x0 y realizar la iteración
xi+1 = f (xi )
hasta que la diferencia |xi+1 − xi | sea inferior a una determinada tolerancia.
Escriba un programa en C++ que aplique el método del punto fijo a la resolución
de la ecuación


σ · 1.99 − 0.41 ·
x
w
+ 18.70 ·
K
x 2
w
2
− 38.48 ·
x 3
w
+ 53.85 ·
x 4
w
 = x
donde w = 2.5, σ = 24.89 y K = 52. Escoja como valor inicial para la iteración
x0 = 0.25 y un valor de la tolerancia igual a 1E − 3.
El programa debe ir escribiendo en la consola los valores xi y |f (xi ) − xi | para
i = 0, 1, . . . , en formato fijo y con 6 dígitos decimales.
Si el número de iteraciones alcanza un cierto valor maxIter = 50, el programa
debe finalizar indicando que el método ha excedido el número máximo de iteraciones.
Incluya en la memoria del trabajo dos capturas de pantalla de la salida por consola. En una de las capturas de pantalla deben mostrarse los resultados de las
primeras iteraciones. En la otra captura de pantalla deben mostrarse los resultados de las últimas iteraciones.
A continuación, modifique el valor del número máximo de iteraciones a maxIter =
200 y ejecute nuevamente el programa. Incluya en la memoria una captura de
pantalla donde se muestre en este caso el resultado obtenido en las últimas iteraciones.
Dpto. de Informática y Automática, UNED
3
LENGUAJES DE PROGRAMACIÓN
EJERCICIO 2
Escriba un programa en C++ que calcule y escriba en la consola el producto de
dos números naturales leídos de un fichero de texto. Cada número está escrito
en una línea diferente del fichero, por lo que éste contiene dos líneas de texto. El
programa debe realizar las acciones siguientes:
1. Solicitar y leer el nombre del fichero. Mediante un mensaje en la consola, solicitar al usuario que introduzca el nombre del fichero de texto donde están
escritos los dos números. Leer el nombre introducido por el usuario.
2. Leer el fichero. Abrir para lectura el fichero de texto. Si se produce error,
terminar. En caso contrario, leer el contenido del fichero.
Dado que los números escritos en el fichero pueden ser lo suficientemente
grandes como para estar fuera del rango de los tipos de datos de los números enteros, el programa almacenará cada uno de los dos números en un
string.
3. Comprobar que cada uno de los dos strings leídos contiene un número natural.
Para ello, debe comprobarse que todos los componentes de los strings son
dígitos. En caso contrario, mostrar un mensaje indicándolo y terminar.
4. Comprobar que los números naturales están dentro de los límites para las variables
de tipo unsigned long int. Si alguno de los números leídos está fuera del
rango de valores de este tipo de dato, mostrar un mensaje indicándolo y
terminar.
5. Conversión de tipo. Almacenar los números naturales escritos en los dos strings
en sendas variables del tipo unsigned long int.
6. Comprobar que el producto de los dos números está dentro de los límites para
las variables de tipo unsigned long int. Si no lo está, mostrar un mensaje
indicándolo y terminar.
7. Mostrar en la consola el resultado de la multiplicación de los dos números.
8. Terminar.
4
Dpto. de Informática y Automática, UNED
TRABAJO PRÁCTICO - SEPTIEMBRE DE 2016
EJERCICIO 3
El objetivo es nuevamente calcular el producto de dos números naturales escritos
en un fichero de texto, pero en esta ocasión la estrategia a seguir es diferente ya
que se pretende poder calcular el producto de números naturales arbitrariamente
largos. El programa debe realizar las acciones siguientes (obsérvese que las tres
primeras coinciden con las del ejercicio anterior):
1. Solicitar y leer el nombre del fichero. Mediante un mensaje en la consola, solicitar al usuario que introduzca el nombre del fichero de texto donde están
escritos los dos números. Leer el nombre introducido por el usuario.
2. Leer el fichero. Abrir para lectura el fichero de texto. Si se produce error,
terminar. En caso contrario, leer el contenido del fichero almacenando cada
uno de los dos números en un string.
3. Comprobar que cada uno de los dos strings leídos contiene un número natural.
Para ello, debe comprobarse que todos los componentes de los strings son
dígitos. En caso contrario, mostrar un mensaje indicándolo y terminar.
4. Conversión de tipo. Almacenar los números naturales escritos en los dos strings
en sendos vectores de int, de manera que cada dígito del número quede
almacenado en un componente del vector.
5. Multiplicación de los dos números naturales. La multiplicación debe realizarse
aplicando el procedimiento clásico empleado al operar con “lápiz y papel”.
El algoritmo de la multiplicación debe aplicarse operando los dos vectores
de dígitos, obteniéndose como resultado otro vector de dígitos.
El procedimiento clásico de multiplicación con lápiz y papel consiste en
ir multiplicando por el primer factor los dígitos del segundo factor, comenzando por el menos significativo. Los resultados obtenidos se suman
desplazados cada uno una posición hacia la izquierda respecto al anterior.
A continuación se muestra un ejemplo.
×
1
15
115
132
385474365678
3
927371828393
418974627150
642309703628
988656159172
76
45
80
4
20
6. Mostrar el resultado en la consola y terminar.
Dpto. de Informática y Automática, UNED
5
LENGUAJES DE PROGRAMACIÓN
EJERCICIO 4
El algoritmo de Karatsuba permite realizar la multiplicación de dos números
enteros grandes por medio de la multiplicación, suma y resta de números enteros
más pequeños. Un caso particular del algoritmo de Karatsuba permite calcular el
producto de dos números enteros x e y, expresados de la forma:
x = x1 · 103 + x0
y = y1 · 103 + y0
de la manera siguiente:
x · y = z2 · 106 + z1 · 103 + z0
donde z2 , z1 y z0 se calculan de la forma siguiente:
z2 = x1 · y1
z0 = x0 · y0
z1 = (x1 + x0 ) · (y1 + y0 ) − z2 − z0
En la Figura 1.1 se muestra un ejemplo de aplicación del algoritmo. Obsérvese
que las multiplicaciones necesarias para calcular z2 , z1 y z0 , pueden ser calculadas
aplicando este mismo algoritmo de forma recursiva si al menos uno de los dos
factores es mayor que 999. Si los dos factores son menores que 999, el producto se
realiza de la manera ordinaria.
Escribir un programa en C++ que realice las acciones siguientes:
1. Solicitar que el usuario introduzca por consola dos números enteros.
2. Comprobar que el producto de los dos números está dentro de los límites
para las variables del tipo long long int. Si no lo está, mostrar un mensaje
indicándolo y terminar.
3. Calcular el producto de los dos números aplicando el algoritmo de Karatsuba.
4. Mostrar el resultado en la consola.
5. Terminar.
6
Dpto. de Informática y Automática, UNED
TRABAJO PRÁCTICO - SEPTIEMBRE DE 2016
Figura 1.1: Ejemplo de aplicación del algoritmo de Karatsuba.
Dpto. de Informática y Automática, UNED
7