En esta asignatura soy responsable de un grupo de teoría y de
dos de prácticas.
En mi grupo de teoría utilizo estos apuntes.
Además he preparado una colección de problemas cuyos
enunciados están disponibles aquí.
Dada la importante cantidad de ejercicios de examen de que se dispone,
se hará un uso marginal de este documento.
Para trabajar en casa puedes utilizar dev-cpp como
Entorno Integrado de Desarrollo. Es gratuito y ocupa menos de 20MB. He
preparado unos apuntes
que explican a nivel introductorio el funcionamiento de este programa.
No imprimir este documento, se ampliará a lo largo del curso.
Las capturas de pantalla se ven mucho mejor en la versión en html del mismo documento.
Aquí iré publicando los ejercicios que se hagan en clase
y cualquier otro material que vaya surgiendo a lo largo del curso.
Exámenes
de otros años.
Luis Junco tiene en su página
los exámenes de otros años recopilados en varios ficheros
comprimidos. en la misma página hay materiales interesantes en
la zona de descargas.
2003-2004.
2004-2005.
2005-2006.
Prácticas.
NUEVO: notas. Están
identificadas por las iniciales. Primero la del nombre.
Guión para la primera
práctica (es autoexplicativo). guion1.cpp
Guión para la segunda
práctica:
Consiste en la resolución de los siguientes ejercicios de
examen.
- ( Febrero 2004) Calcular una aproximación a PI mediante el
producto de Wallis:
Notas: Debe pensar como obtener cada
termino en función del anterior y un criterio de parada adecuado.
- (Julio 2004) Determinar mediante un programa el entero tal que su
raíz enésima se aproxime más a PI. El entero es
menor o igual
que 100 y el orden de la raíz menor o igual que 5.
NOTA: La función double pow(double x, double y) devuelve el
valor de x elevado a y. La raíz cúbica de 100
se puede calcular como pow(100,1.0/3)
Este ejercicio es de exploración exhaustiva, similar al que se
ha resuelto en clase de teoría, en el que se calculaba el
numerador y el denominador de una fracción cuyo cociente se
aproximaba a PI. PI1.cpp
- (Plan antiguo) Calcular una aproximación a PI mediante la
formula de François Viète:
Si siente curiosidad, en la Wikipedia
se puede encontrar más información sobre todo esto.
Guión para la tercera
práctica.
La ley electoral utiliza el sistema DONT para el cálculo del
número de candidatos electos de cada una de las candidaturas
presentadas.
En primer lugar se eliminan aquellas candidaturas que obtengan menos
del 5% del número total de votos.
Seguidamente se construye una tabla en la cual cada columna contiene el
número de votos de la candidatura dividido entre 1,2,3... y
así sucesivamente, hasta completar P columnas, siendo P el
número de candidatos electos. De entre todos estos
números se seleccionan los P mayores.
En un pueblo de Asturias con 11 concejales se presentaron 7
candidaturas y cada una de ellas obtuvo los votos reflejados en la
columna N de la tabla. Supongamos que no existen votos nulos o blancos.
El número total de votos fue pues de 9140, así que se
eliminan las candidaturas que obtuvieron menos de 457 votos, para ellos
se hacen cero sus votos.
Los 11 mayores números que aparecen en la tabla son: 3505
2692 1753 1465 1346 1168
897 876 733 701 693 con lo que la candidatura 0
obtuvo cinco concejales, la 2 uno, la 3 tres y
la 5 dos concejales.
NOTA:
En lugar de construir una tabla como la de arriba, es mejor utilizar un
vector en el que se almacenen los datos de la primera columna y en cada
iteración, se actualizan las casillas correspondientes, es
decir, se parte de lo siguiente (después de eliminar los votos
de las candidaturas que obtuvieron menos del 5% de los votos):
3505
|
0
|
693
|
2692
|
0
|
1465
|
492
|
El mayor es 3505, entonces se suma un concejal a la candidatura 0 y se
divide 3505 entre 2 (en la tabla aparece redondeado hacia arriba, en la
práctica divida entre 2 sin mas). La siguiente vez que se
dividan los votos de esta candidatura se hará entre 3. La tabla
ahora queda:
1753
|
104
|
693
|
2692
|
189
|
1465
|
492
|
El mayor ahora es 2692, se suma un concejal a la candidatura 3 y se
divide 2692 entre 2, 3505 entre 3 y asi sucesivamente.
En resumen:
Se pide el número de candidaturas y de concejales.
Se pide el número de votos de cada candidatura, se almacenan en
un vector.
Se calcula el número total de votos.
Se hace cero el número de votos de las candidaturas que obtienen
menos del 5% de votos.
Se repite P veces:
Incrementar en uno el número de
concejales de la candidatura con mayor número de votos.
Actualizar la cantidad entre la que se divide
Dividir los votos de cada candidatura entre la cantidad que corresponda.
Guión para la tercera
práctica.
Resolver este ejercicio, que ya se vio en clase, utilizando un vector
para almacenar los dígitos de cada número que se examina
para saber si cumple o no la condición.
- Buscar el mayor número entero (menor que 45000 por
cuestiones de rango) cuyo cuadrado se escriba con dígitos
distintos. (Ejercicio de examen)
- Alternativa I: contar cuantas veces se repite cada
dígito,
comprobar que no hay ninguno que se repita mas de 1 vez. Para contarlos
utilizar un vector de enteros de longitud 10. Cada vez que se encuentra
el dígito i, se incrementa el elemento i-ésimo de ese
vector.
- Alternativa II: utilizar un vector de booleanos de longitud 10.
Inicializar a false cada elemento. Si el dígito de valor i se
repite, poner a true el elemento correspondiente del vector. El
número cumple la condición si todos los elementos del
vector están a false.
- Tres posibles esquemas para resolver este ejercicio (uno
adicional a las alternativas propuestas):
Guión para la cuarta
práctica.
- Reescribir el ejercicio de la ley electoral utilizando funciones.
- Escribir la función de protipo int
suma(const vector<int>&); que recibe un vector de
enteros y que devuelve la suma de sus elementos.
- Escribir la
función de prototipo void
purga(vector<int>&); que recibe un vector de enteros
conteniendo el número de votos recibido por cada candidatura y
lo modifica de modo que hace cero los votos de las candidaturas que
reciben menos del 5% de los emitidos. Esta función llama a suma.
- Escribir la función de
prototipo int mayor(const
vector<int>&); que recibe el vector con los votos
dividitos entre los divisores correspondientes y devuelve el
índice del vector en donde está el mayor de sus
elementos.
- Escribir la función de prototipo void calcula_concejales(const
vector<int>&, vector<int>&, int); que recibe
los votos que ha recibido cada candidatura y el número de
concejales que se reparten. Devuelve los concejales que recibe cada
candidatura. Esta función llama a mayor.
De este modo el programa
podría quedar así (no se incluye la declaración y
definición de las funciones):
#include <iostream>
#include <vector>
using namespace std;
//declaraciones y definiciones de funciones
//...
//o bien (ver el final)
int main()
{
int i,ncand,P;
//pedir el numero de candidaturas y concejales
cout << "Numero candidaturas : ";
cin >> ncand;
cout << "Numero de concejales : ";
cin >> P;
vector<int> votos(ncand), concejales(ncand,0);
//pedir los votos de cada candidatura
for (i=0; i<ncand; i++)
{
cout << "Votos candidatura " << i << " : ";
cin >> votos[i];
}
//purgar las candidaturas que reciben menos del 5%
purga(votos);
//llamada a la funcion calcula_concejales
calcula_concejales(votos,concejales,P);
//mostrar resultados
for (i=0; i<ncand; i++)
cout << "Candidatura " << i << ": " << concejales[i]
<< " concejales" << endl;
}
//puede usar prototipos y poner las definiciones aqui
- Reescribir el ejercicio "mayor número entero menor que
45000 cuyo cuadrado se escriba con dígitos
distintos" utilizando funciones. En este caso estructurarlo como desee.
Guión para la quinta
práctica. El ejercicio de referencia es la función que
calculal la paridad de un vector de booleanos de forma recursiva.
- Escribir una función recursiva que devuelva la suma de los
elementos de un vector.
- Escribir una función recursiva que devuelva true si un
entero pertenece a un vector de enteros (ambos son parámetros),
false en caso contrario.
Guión para la sexta
práctica. Se basa en modificar el
ejercicio introductorio de clases visto en teoria, añadiendo
funciones y operadores. guion_practica_complejos_clases.cpp.
Guión para la
séptima y última práctica, a desarrollar a lo
largo de dos semanas. Se trata de un ejercicio de clases que
cayó en un examen. En este caso se realizará en su
versión completa y no la parte que se pedía en el examen.
Consiste en implementar una versión del juego Sokoban (o mueve
la caja) en modo texto, usando clases. guion_muevecaja.cpp.
Teoría.
Ejemplos de if, if else y switch. Por petición popular,
versión para imprimir con todos los ejercicios en una hoja, a
dos columnas. ejercicios_clase1.pdf
- Resolver un sistema lineal de ecuaciones de orden dos,
considerando todos los casos posibles. sistema2ecc.cpp
- Mostrar la hora siguiente a una dada, en hh:mm. hora_siguiente.cpp
- Implementar una calculadora de números reales con las
operaciones +,-,*,/. calculadorareales.cpp
- Pedir tres números por el teclado y ordenarlos. ordena3.cpp
- Resolver una ecuación de segundo grado, considerando todos
los casos posibles. segundogrado.cpp
- Mostrar el día siguiente a uno dado, considerando el caso
de los años bisiestos (problema de examen). diasiguiente.cpp
- Implementar una calculadora de números complejos con las
operaciones +,-,*,/. Cuidar la representación en pantalla de los
complejos, utilizar la notación cartesiana. calculadoracomplejos.cpp
Ejemplos iniciales de bucles.
- Sumar las cifras de un número entero. sumacifras.cpp
- Invertir el orden de las cifras de un número entero. reves.cpp
- Averiguar si un número es capicúa o no. capicua.cpp
- Calcular de forma iterativa la raíz cuadrada de un
número real. raizcuadrada_b.cpp
- Pedir 10 números por el teclado, mostrar el tercero mayor
(ejercicio de examen). tercero_mayor.cpp
Ejemplos con bucles anidados.
- Mostrar los n primeros capicúas, n se pide por el teclado.
ncapicua.cpp
- Determinar los números menores que 1000 tales que aparecen
al final de su cuadrado (ejercicio de examen). xy2xyz.cpp
- Determinar cual es la fracción que se aproxima más
a PI con el numerador y el denominador menores que 500 (ejercicio de
examen). PI1.cpp
Los dos grupos de ejercicios anteriores tal y como se llevaron a clase.
ejercicios_clase2.pdf
Por petición popular, entodavía más ejemplos de
bucles, todos en un pdf.ejercicios_clase3.pdf
- Convertir un número de decimal a
binario. d2b.cpp
- Descomponer un número en factores primos.factoresprimos.cpp
- Obtener los 20 primeros términos de la sucesión de
Fibonacci (fibo20.cpp). Alguien
me ha comentado que cada dos términos consecutivos guardan la
proporción 1.61803. Como curiosidad, comprobarlo usando un
programa.
- Aproximación de la cte. e por una serie. Efectuando un
número fijo de iteraciones (e_a.cpp),
mientras no se alcance una determinada precisión (e_b.cpp),
las dos anteriores combinadas, lo que suceda antes (e_c.cpp).
- Aproximación de e^x
por una serie, finaliza cuando se alcanza un máximo
número de iteraciones o una determinada precisión, lo que
suceda antes. Intentar realizar el mínimo número de
cálculos posible. ex.cpp
- Buscar el mayor número entero (menor que 45000 por
cuestiones de rango) cuyo cuadrado se escriba con dígitos
distintos. (Ejercicio de examen)
Ejemplos de cuadrados que cumplen esa condición : 13^2 = 169
286^2=81796 32043^2=1026753849. cuadrado_digitos_distintos.cpp
- Un número perfecto es aquel que coincide con la suma de
todos sus divisores, incluyendo el 1 pero no el propio número
(por ejemplo 6 = 1+2+3, 28 = 1+2+4+7+14). Escribir un programa
que muestre por la pantalla los números perfectos menores que
100. (Ejercicio de examen) perfectos.cpp
Ejemplos de vectores. Tal y como se llevaron a clase ejercicios_clase4.pdf
Varios métodos útiles para trabajar con vectores en un
ejemplo autoexplicativo. vectores1.cpp.
En pdf tal y como se llevó a clase vectores1.pdf.
Ejemplos introductorios de funciones. Tal y como se llevaron a clase ejercicios_clase5.pdf
- Mostrar los n primeros capicúas, n se pide por el teclado.
ncapicua_f.cpp
- Mostrar los n primeros números que contienen la cifra x. ncontienex_f.cpp
- Buscar el mayor número entero (menor que 45000 por
cuestiones de rango) cuyo cuadrado se escriba con dígitos
distintos. (Ejercicio de examen, versión con funciones)
Ejemplos de cuadrados que cumplen esa condición : 13^2 = 169
286^2=81796 32043^2=1026753849. cuadrado_digitos_distintos_f.cpp
Más ejemplos de funciones, relacionados con los temas de los
apuntes "Mecanismos de paso de argumentos" y "Semántica del paso
de argumentos". De alguna forma todos han caído en algún
examen. Ejercicios tal y como se llevaron a clase (había una
errata en el ejercicio de la paridad) ejercicios_clase6.pdf.
- Escribir una función que expurgue las repeticiones de los
elementos de un vector de enteros. Varias versiones, usando o no
push_back, devolviendo el resultado con return o a través de una
referencia no constante. unicos.cpp
- Sobrecarga de los operadores *, >> y << para
matrices. matop.cpp
- Mezcla (merge) de dos vectores ordenados produciendo un tercer
vector, también ordenado. mezcla.cpp
- Máximo de la suma de elementos contiguos de un vector. suma_maxima_segmento.cpp
- Función
que comprime
un vector de enteros "casi vacío" y su contrapartida,
descomprime un vector
"casi vacío" (ejercicio de examen). Un vector "casi
vacío" es aquel que contiene mayoritariamente elementos nulos.
Para ahorrar espacio se guarda el tamaño del vector y
(alternativamente) la posición y el contenido de los elementos
no nulos en un vector de enteros convencional. Por ejemplo el vector
{0,0,0,1,0,0,-7,0,0} se podría guardar como {9,3,1,6,-7}. La
función comprime se ha escrito usando push_back y sin usarla. comprime.cpp
- Función que devuelve true si la paridad de un vector de
booleanos es par, false en caso contrario. La paridad es par si el
número de elementos a true es par. vector_par.cpp
Explicación de la implementación recursiva del factorial.
recursividad.cpp
Ejemplo de enumeraciones y estructuras. Programa que muestra las 40
cartas de la baraja española en orden aleatorio (barajadas). Se
definen enumeraciones para la figura y para el palo y cada carta es una
estructura cuyos campos son enumeraciones de los tipos anteriores. barajaf.cpp. El ejercicio tal y
como se llevó a clase ejercicios_clase7.pdf.
Esquema general de implementación y uso de una clase, sin
utilizar y utilizando el operador de resolución de
ámbito, es decir definiendo las funciones miembro dentro de la
clase esquema_clase.pdf
y declarando las funciones dentro y definiéndolas fuera esquema_clase_scope.pdf.
Ejemplos de un problema resuelto sin funciones (complejos_pelado.cpp),
con funciones (complejos_con_funciones.cpp),
con estructuras (complejos_con_estructuras.cpp)
y con clases (complejos_con_clases.cpp).
Este último se irá refinando en clases sucesivas, a
medida que se impartan los conocimientos necesarios para ello.
El objetivo es comprender la ventaja que proporciona al programador/a
el uso de clases.
Los ejercicios tal y como se llevaron a clase ejercicios_clase8.pdf.
Ejemplo de clases para ilustrar la función del puntero oculto
this. clase_teoria_comentarios.cpp.
Ejemplos de clases para ilustrar el concepto de interfaz pública
de una clase, uso del constructor para convertir entre tipos,
operadores friend. Usaremos la clase complejo representados en
cartesianas (complejosc.cpp) y en polares (complejoscp.cpp).
Los ejemplos anteriores en pdf. ejercicios_clase9a.pdf
ejercicios_clase9b.pdf.
Problemas de clases sencillos que han caído en exámenes.
Enunciados enunciados_clases.pdf.
Soluciones ejercicios_clase10.pdf.
Ejemplos para ilustrar el tema de los destructores estructura_dinamica.cpp,
operación de asignación y constructor de copia estructura_dinamica2.cpp.
Ejemplos para ilustrar el tema de las acciones y tipos genéricos
(templates). unicosT.cpp, parT.cpp.
Ejemplos para ilustrar el tema "Objetos como miembros de otras clases",
además son ejercicios de examen.
Ejemplos de herencia.
- Jerarquía de clases "electrodoméstico". electro.cpp
- Jerarquía de clases "Fun". h.cpp
Ejemplos complementarios de distintos temas:
- Un ejemplo sencillo de ordenación, método de la
burbuja (no usar
en la vida real, es el peor método que hay). burbuja.cpp
- El ejemplo anterior convertido
en template y con un parámetro adicional de tipo puntero a
función, de modo que el mismo algoritmo ordena de mayor a menor
o al revés, según el criterio que se use. burbujaT.cpp
- Varios métodos útiles pare vectores. Borrado e
inserción de elementos, borrado total, consulta de estado
(vacío o no), introducción a iteradores y algoritmos de
STL (ordenación...). vectores2.cpp
- Ejercicio de examen, comprimir y descomprimir una imagen
binaria por el método "Run Length Code", incluye enunciado. rli.cpp