1º Bach Matemáticas Generales · CyL Decreto 40/2022 · D.5 Algoritmos, programas y herramientas offline
Objetivos
Leer un diagrama de flujo y distinguir secuencia, decisión y bucle.
Ejecutar el algoritmo de Euclides con números concretos y justificar el último resto no nulo.
Detectar un algoritmo que no termina o que falla al iniciar el acumulador.
Preciso, finito y escrito en pasos
Un algoritmo es una lista de instrucciones tan cerrada que otra persona, sin conocer el problema, llega al mismo resultado. No vale «haz la cuenta» ni «busca el máximo si se ve». Hacen falta una entrada, un proceso con operaciones permitidas y una salida, y hace falta que el proceso se detenga.
secuencia = pasos uno detrás de otro · decisión = una pregunta con dos salidas (sí / no) · bucle = volver atrás mientras una condición siga siendo verdadera · resto = lo que sobra en la división entera, a módulo b · mcd = mayor entero que divide a los dos números
El diagrama de la izquierda es el de Euclides para el par del ejemplo. El rombo pregunta si b ya es 0. Si no lo es, la caja verde sustituye el par: el divisor pasa a ser el nuevo a, y el resto pasa a ser el nuevo b. La flecha vuelve al rombo. Si b es 0, se sale y la respuesta es el a que queda. A la derecha está la traza concreta, no un esquema vacío: (48, 18), (18, 12), (12, 6) y (6, 0).
Esa misma disciplina sirve para un bucle que suma o para uno que busca un máximo. El fallo típico no es «no se me dan los algoritmos»: o falta la actualización que acerca el proceso al final, o el valor inicial no pertenece al conjunto de datos. Las dos cosas se ven al ejecutar tres vueltas con números, que es lo que pide esta lección.
Pieza
En el ejemplo
Si falta
Entrada
a = 48, b = 18
No hay caso que ejecutar
Condición
¿b = 0?
No se sabe cuándo salir
Actualización
(a, b) ← (b, a mod b)
El rombo no cambia nunca
Salida
6
El proceso no devuelve el mcd
Gráfico del ejemplo
La figura no es decoración: los trazos corresponden a los números del ejemplo 1.
Ejemplo resuelto 1 — Euclides con 48 y 18
Ejecuta el algoritmo de la figura con a = 48 y b = 18. Escribe cada división, el par nuevo y el motivo para parar. Comprueba que 6 divide a los dos.
Primera vuelta: 48 = 2 · 18 + 12. El cociente es 2 y el resto es 12, así que el par pasa a ser (18, 12).Glosa: 2 · 18 = 36 y 48 − 36 = 12. El resto tiene que ser menor que el divisor.
Segunda vuelta: 18 = 1 · 12 + 6. El par pasa a ser (12, 6). El mcd todavía no es 12: el resto no es cero.Glosa: se para solo cuando el resto es 0, no cuando el resto «ya es pequeño».
Tercera vuelta: 12 = 2 · 6 + 0. El par pasa a ser (6, 0). La condición del rombo ya es sí, y la salida es 6.Glosa: el último divisor no nulo, que ahora está en a, es el máximo común divisor.
Comprobación: 48 = 6 · 8 y 18 = 6 · 3. No hay un entero mayor que divida a los dos, porque el algoritmo agota los restos.Glosa: 8 y 3 son coprimos; si hubiera un divisor común mayor que 6, también dividiría al resto 0 de forma contradictoria con los pasos.
Ejemplo resuelto 2 — Suma de 1 a 5, bucle y atajo
Un algoritmo hace s = 0 y, para i desde 1 hasta 5, s = s + i. Ejecútalo vuelta a vuelta y compáralo con la fórmula n(n+1)/2.
Estado inicial: s = 0 e i = 1. La primera suma deja s = 1. No se empieza en el resultado.Glosa: el acumulador tiene que nacer en el elemento neutro de la suma, que es 0.
Siguientes vueltas: i = 2 deja s = 3; i = 3 deja s = 6; i = 4 deja s = 10; i = 5 deja s = 15. Ahí el bucle corta.Glosa: el límite superior es 5 inclusive. Parar en 4 olvidaría el último sumando.
La fórmula con n = 5 da 5 · 6 = 30
30 / 2 = 15. Coincide con el bucle, así que el atajo no cambia el problema.Glosa: la fórmula es otro algoritmo para la misma salida; si no coincidiera, habría un límite mal puesto.
Si el bucle llegara hasta 6, saldría 21, y la fórmula de n = 5 seguiría diciendo 15. El desajuste delata el error de límite, no «que la fórmula falle».Glosa: se depura comparando dos procedimientos sobre el mismo n, no discutiendo en abstracto.
Ejemplo resuelto 3 — El máximo no puede nacer en cero
Lista: −3, −1, −8. Algoritmo A inicia m en el primer dato. Algoritmo B inicia m en 0 y solo actualiza si el dato es mayor. Ejecuta los dos.
Algoritmo A: m = −3. El −1 es mayor, así que m = −1. El −8 no lo supera. Salida −1, que sí está en la lista.Glosa: empezar en el primer dato garantiza que m siempre es uno de los valores leídos.
Algoritmo B: m = 0. Ningún dato es mayor que 0, así que m no se mueve. La salida es 0, y 0 no está en la lista.Glosa: el fallo es la inicialización, no la comparación. Con números positivos el mismo B habría parecido correcto.
La decisión «dato mayor que m» está bien escrita en los dos. Lo que cambia el resultado es el valor de entrada del acumulador.Glosa: un ejemplo con negativos es una prueba de escritorio: busca el caso que rompe el algoritmo, no el caso cómodo.
Corrección de B: o se inicia m con el primer elemento, o se declara que la lista es de números no negativos. Sin esa hipótesis, B es incorrecto.Glosa: un algoritmo correcto necesita decir para qué entradas promete funcionar.
Ejercicios
Escribe el razonamiento completo en el editor, no solo la cifra. Si el enunciado pide figura, dibújala en el lienzo de esta misma página.
1. Euclides con 30 y 21
Calcula mcd(30, 21) con el mismo algoritmo. Escribe los tres restos y di por qué la salida no es el último cociente.
Por qué (abre cuando hayas escrito)
El paso que hay que escribir es la división entera, no un «se ve que es 3».1 · 21 = 21
21 + 9 = 30
30 = 30, así que el par pasa a (21, 9). Después 21 = 2 · 9 + 3 y el par pasa a (9, 3). Después 9 = 3 · 3 + 0 y se para: el mcd es 3, el último resto no nulo. El último cociente es también 3, pero eso es casualidad de este ejemplo; en 48 y 18 el último cociente era 2 y el mcd era 6. Por eso la regla es leer a cuando b llega a 0, no leer el cociente. Comprobación: 30 = 3 · 10 y 21 = 3 · 7.
2. Un mientras que no se mueve
Pseudocódigo: x = 3; mientras x sea mayor que 0, escribir x. No hay ninguna otra línea. ¿Qué ocurre en las tres primeras vueltas y qué propiedad del algoritmo falta?
Por qué (abre cuando hayas escrito)
El paso ausente es la actualización de x. Primera vuelta: x = 3, la condición es verdadera y se escribe 3. Segunda vuelta: x sigue siendo 3, porque nadie lo ha restado, y se vuelve a escribir 3. La tercera es idéntica. La condición no se acerca a ser falsa, así que el algoritmo no termina. En la definición que usamos en esta lección, terminar forma parte del algoritmo: un bucle solo es válido si cada vuelta cambia el estado hacia la salida, como el resto de Euclides, que es siempre menor que el divisor anterior y no puede bajar indefinidamente en los enteros no negativos.
3. Contar aprobados
Notas 4, 7, 5, 3, 9. Escribe un algoritmo que cuente cuántas son mayores o iguales que 5 y ejecútalo. Di qué pasa si la condición se escribe mal como «mayor que 5».
Por qué (abre cuando hayas escrito)
El paso es un contador que nace en 0 y solo suma 1 cuando la condición es verdadera, no sumar la propia nota. Con el umbral bien puesto: 4 no; 7 sí (c = 1); 5 sí (c = 2); 3 no; 9 sí (c = 3). Salida 3. Si la condición se cambia a «mayor que 5», el 5 deja de contarse y la salida es 2. El algoritmo no está «casi bien»: el borde del aprobado, que el Decreto y la evaluación colocan en 5, hay que copiarlo con el igual. Por eso se prueba el caso frontera, no solo un 9 y un 3.
Dibuja en el lienzo
Reproduce a mano el gráfico del ejemplo: ejes o nodos, los datos numéricos y una frase con la conclusión. El botón borra el lienzo sin salir de la lección.
Tres preguntas. Responde mentalmente antes de abrir el porqué.
¿Por qué en la figura se para al llegar al par (6, 0)?
Porque b ya es 0 y el rombo sale hacia el círculo de la respuesta. Por qué: el resto 0 significa que 6 divide exactamente a 12, y los restos anteriores garantizan que 6 también divide a 18 y a 48. Seguir no tiene sentido: el módulo con divisor 0 no está definido.
¿Qué dato de la lista −3, −1, −8 delata al algoritmo que empieza en 0?
Que la salida 0 no pertenece a la lista. Por qué: un máximo de la lista tiene que ser uno de sus elementos. Si todas las pruebas se hacen con números positivos, el 0 inicial se sustituye enseguida y el error queda escondido. El caso negativo es el que obliga a corregir el inicio.
¿La fórmula n(n+1)/2 sustituye al bucle o lo comprueba?
Lo comprueba y, cuando ya se sabe que coinciden, también lo abrevia. Por qué: con n = 5 los dos dan 15. Si en otro n no dieran lo mismo, no se «elige el que guste»: se revisa el límite del bucle o el uso de la fórmula. Dos algoritmos de la misma función tienen que devolver la misma salida.
Reto Profesor
Euclides en tu libreta
Elige dos enteros positivos menores que 100, dibuja en el lienzo el rombo y tres cajas con tus restos reales, y escribe al lado el mcd. No copies 48 y 18.