English
Português
中文 (中国)
العربية
हिन्दी
Русский
Français
Deutsch
Ελληνικά
Italiano
日本語
한국어
LatineResumen
Esta clase abre la sexta unidad del curso, dedicada a los datos compuestos. Explica para qué sirve la unidad: enseñar a representar colecciones de datos (secuencias de tamaño fijo y variable, tablas y registros) y a procesarlas con los algoritmos básicos, escritos a mano y tomados de la biblioteca, estimando cuánto cuestan; presenta sus seis clases y el hilo que las une; recuerda lo que la unidad da por sabido, sobre todo los bucles con invariante y el paso por referencia constante; formula el problema que la unidad resuelve, el de un programa que debe guardar datos cuya cantidad no conoce y que, escrito con variables sueltas, calla en silencio los que le sobran; anticipa el costo como segunda medida de un algoritmo, junto a su corrección; y muestra adónde conduce, en las unidades siguientes y en el curso Programación en C++ II.
Objetivos de aprendizaje
- Describir la secuencia de contenidos de la unidad y explicar qué aporta cada clase a la siguiente.
- Recordar los bucles, sus invariantes y el paso de parámetros (por valor, por referencia y por referencia constante), y repasarlos si hace falta.
- Anticipar, con un ejemplo, el costo de un algoritmo como segunda medida de su calidad, junto a su corrección.
- Reconocer qué se espera saber hacer al terminar la unidad, y distinguirlo de lo que se aprenderá en las unidades siguientes.
Evaluación de entrada
Antes de recorrer la unidad conviene medir el punto de partida. Esta evaluación es una autoevaluación: no se califica, y su único propósito es orientar el estudio. Las cuatro primeras preguntas comprueban lo que la unidad da por sabido: el invariante del bucle que busca un máximo, el modo de paso de un parámetro grande, el número de vueltas de dos bucles anidados y la aritmética sin signo. Las seis siguientes tocan, en el orden de las clases, las ideas centrales de la unidad: los índices válidos de una secuencia, la creación de un vector, el número de veces que puede dividirse un tamaño por la mitad, la búsqueda en datos ordenados, el doble índice de una tabla y el peligro de guardar en colecciones separadas los datos de una misma entidad. Nadie está obligado a acertarlas todavía, y en algunas «todavía no lo sé» es una respuesta honesta: cada respuesta, acertada o no, explica el punto y nombra la clase que lo trata. Las mismas destrezas se vuelven a medir al final, en la clase de síntesis.
Antes de comenzar la unidad, mide tu punto de partida. Es una autoevaluación breve: no se califica y su resultado se guarda solo en tu navegador.
Pregunta 1De unidades anterioresEl fragmento
int largest{0}; int t{}; while (std::cin >> t) { if (t > largest) { largest = t; } }debe dejar enlargestla mayor de las temperaturas leídas. ¿Con qué entrada falla?La primera vuelta compara el dato con 0 y lo guarda si es positivo: con un solo dato positivo el resultado es correcto. Conviene seguir la traza antes de responder.Con>un dato igual al máximo no lo reemplaza, pero el máximo es el mismo número: la repetición no altera el resultado.Delata no revisar la inicialización con el invariante: un bucle correcto exige que el invariante valga antes de la primera vuelta.El invariante deseado, «largestes el máximo de lo leído hasta ahora», no vale al comenzar, porque antes de leer nada no hay máximo, y el 0 inicial gana a todo dato negativo. Se corrige inicializando con el primer dato, después de comprobar que existe. La clase Vectores hace lo mismo sobre una secuencia guardada, y la biblioteca lo expresa constd::ranges::max, cuya precondición es que la secuencia no esté vacía.Repasar: Diseñar bucles correctos
Pregunta 2De unidades anterioresUna función calcula cuántas vocales tiene un texto de un millón de caracteres, guardado en un
std::string, y no lo modifica. ¿Cómo conviene declarar su parámetro?El paso por valor copia el millón de caracteres en cada llamada: es correcto, pero paga un costo que no aporta nada.No copia, pero permite modificar el texto sin necesidad y no acepta un literal ni un temporal: confunde «no copiar» con «permitir modificar».El modo de paso forma parte de la interfaz: el paso por valor promete a la función una copia propia, y el programa debe hacerla.La referencia constante lee el texto sin copiarlo y sin permiso para modificarlo, y admite además un temporal. En la unidad 6 esta elección se vuelve la regla: una función que lee un vector de un millón de datos lo recibe comoconst std::vector<int>&, y la copia innecesaria se convierte en el error de costo más frecuente.Repasar: Parámetros y alcance
Pregunta 3De unidades anteriores¿Cuántas veces se ejecuta
++countenfor (int i{0}; i < 6; ++i) { for (int j{0}; j < i; ++j) { ++count; } }?Respuesta correcta:
El bucle interior da 0 vueltas con , una con , y así hasta 5 con : en total , que es . La clase El costo de un algoritmo generaliza la cuenta: dos bucles que recorren todos los pares de datos dan vueltas, y ese número decide si un algoritmo sirve para un millón de datos.Repasar: Bucles
Pregunta 4De unidades anteriores¿Qué escribe
std::println("{}", 0u - 1);en un sistema conunsigned intde 32 bits?Cree que un tipo sin signo admite negativos.Cree que la resta se detiene en el menor valor del tipo; la aritmética sin signo da la vuelta, no se satura.Confunde un aviso posible con un error: la expresión es válida y su valor está definido.La aritmética sin signo es modular: restar 1 a 0 da la vuelta al mayor valor del tipo, . La unidad 6 mide los tamaños constd::size_t, que también es sin signo, de modo quev.size() - 1con un vector vacío no da , sino un número enorme; las clases Arreglos y Vectores muestran el bucle que por eso se sale de los límites.Repasar: Los enteros y su representación
Pregunta 5En una secuencia de elementos numerados como en C++, ¿qué índices designan un elemento?
Numera desde uno, como en el lenguaje común; en C++,a[n]está ya fuera de la secuencia.Es el error por uno más frecuente: cuenta índices para elementos.Es una respuesta honesta: la clase 6.1 lo explica, con la razón por la que se cuenta desde cero.El índice de C++ cuenta desde cero, porque es el desplazamiento desde el primer elemento: el primero esa[0]y el últimoa[n - 1]. Acceder con[]a un índice fuera de ese intervalo es comportamiento indefinido, y la clase Arreglos enseña a demostrar, con el invariante del bucle, que cada acceso es válido.Repasar: Arreglos
Pregunta 6¿Qué contiene
vdespués destd::vector<int> v(3, 7);?Lee los paréntesis como si fueran llaves.Invierte el papel de los dos números.Es una respuesta honesta: la clase 6.2 presenta el vector y sus formas de creación.Con paréntesis, el primer número es la cantidad y el segundo el valor de cada elemento; con llaves,std::vector<int> v{3, 7};es la lista de los elementos, el 3 y el 7. El vector es el primer tipo del curso en que las llaves y los paréntesis dicen cosas distintas, y la clase Vectores lo muestra con un programa.Repasar: Vectores
Pregunta 7¿Cuántas vueltas da
for (int m{1024}; m > 1; m /= 2) { ... }?Respuesta correcta:
Los valores demal comenzar cada vuelta son 1024, 512, 256, 128, 64, 32, 16, 8, 4 y 2: diez vueltas, porque , y diez es . Un algoritmo que reduce su problema a la mitad en cada paso hace del orden de pasos, y la clase El costo de un algoritmo lo llama logarítmico: con mil millones de datos le bastan unos treinta.Repasar: El costo de un algoritmo
Pregunta 8Una guía tiene un millón de nombres en orden alfabético. Para encontrar uno, se la abre por la mitad, se descarta la mitad donde el nombre no puede estar, y se repite con la otra. ¿Cuántas veces, como máximo, hay que abrirla?
Es la cuenta de la búsqueda que examina los nombres uno por uno: sin aprovechar el orden, en promedio se recorre la mitad de la guía.Es la raíz cuadrada de un millón: confunde dividir el tramo por la mitad con dividirlo en bloques.Usa el logaritmo decimal: cada apertura descarta la mitad, no nueve décimas partes.Cada apertura reduce a la mitad el tramo donde puede estar el nombre, y supera el millón: tras veinte mitades queda un solo nombre. Es la búsqueda binaria de la clase Buscar y ordenar, que solo funciona si los datos están ordenados y que se justifica con un invariante.Repasar: Buscar y ordenar
Pregunta 9Con
std::vector<std::vector<int>> t{{1, 2, 3}, {4, 5, 6}};, ¿cuánto valent[1][0]yt.size()?Lee el primer índice como columna y cuenta las columnas en lugar de las filas.Cree quesize()cuenta todas las casillas de la tabla.Es una respuesta honesta: la clase 6.5 presenta las tablas como vectores de vectores.Pregunta 10Un programa guarda los nombres de un grupo en un vector y sus notas en otro, de modo que la nota
grades[i]es la denames[i]. Si ordena solo el vector de las notas, ¿qué ocurre?Para el compilador los dos vectores son independientes: la relación existe solo en la mente de quien escribió el programa.El algoritmo recibe un solo vector y no sabe de la existencia del otro.Todo acceso es válido y todo resultado está definido: el defecto es de lógica, y por eso ningún detector lo señala.
Cargando el contenido…