Algoritmos para procedimientos matemáticos y patrones
Un amigo te dice: «¿Es primo el 91?». Podrías probar a mano, pero ¿y si te preguntan por 10.000 números? Un computador solo hace lo que le explicas paso a paso. En esta página aprenderás a escribir esas instrucciones para generar patrones y resolver problemas con números, y al final volverás al 91.
Sucesiones definidas por una regla
Una sucesión es una lista ordenada de números: primer término, segundo, tercero… Si hay un patrón, no hace falta escribirlos todos: basta una regla que diga cómo obtener cada término.
Es exactamente lo que hace un computador: recibe un $n$ y devuelve un valor.
Una regla también puede definir cada término a partir de los anteriores. En la sucesión de Fibonacci (1, 1, 2, 3, 5, 8…) cada término es la suma de los dos anteriores.
Una sucesión está definida por la regla $a_n = 3n + 2$, con $n = 1, 2, 3, \dots$ Explica qué significa que una sucesión esté definida por una regla y escribe sus…
Una sucesión está definida por la regla $a_n = 3n + 2$, con $n = 1, 2, 3, \dots$ Explica qué significa que una sucesión esté definida por una regla y escribe sus primeros cuatro términos.
Divisores y números primos
Un número $d$ es divisor de $n$ si $n \div d$ da una división exacta (resto 0). Los divisores de 12 son $1, 2, 3, 4, 6$ y $12$.
Con esto, 13 es primo (divisores: 1 y 13), mientras que 15 no lo es (tiene 3 y 5) y 21 tampoco (tiene 3 y 7).
Escribe todos los divisores positivos del número 12. Luego indica cuál de los números 13, 15 y 21 es primo y explica qué característica de sus divisores te permitió…
Escribe todos los divisores positivos del número 12. Luego indica cuál de los números 13, 15 y 21 es primo y explica qué característica de sus divisores te permitió decidirlo.
Ciclos y tabla de seguimiento
Un ciclo repite instrucciones. En pseudocódigo, para i desde 1 hasta 5 repite el bloque con i = 1, 2, 3, 4, 5. La flecha ← significa «guarda en».
s ← 0
para i desde 1 hasta 5:
s ← s + i
escribir s
Para entender qué hace un algoritmo, se hace una tabla de seguimiento (o prueba de escritorio): una fila por vuelta y una columna por variable.
Observa el siguiente algoritmo en pseudocódigo: Haz una tabla de seguimiento con los valores de i y de s en cada vuelta del ciclo e indica qué valor escribe el algoritmo…
Observa el siguiente algoritmo en pseudocódigo:
s ← 0
para i desde 1 hasta 5:
s ← s + i
escribir s
Haz una tabla de seguimiento con los valores de i y de s en cada vuelta del ciclo e indica qué valor escribe el algoritmo al final.
Ciclos con condición: `mientras`
Cuando no sabes cuántas vueltas habrá, usa mientras: repite mientras la condición sea verdadera. Para que termine, algo dentro del ciclo debe cambiar la condición.
a ← 1
mientras a < 50:
escribir a
a ← a * 2
Seguimiento: a vale 1, 2, 4, 8, 16, 32 y se escribe cada uno. Luego a pasa a 64; como $64 < 50$ es falso, el ciclo se detiene. Escribe las potencias de 2 menores que 50.
Para escribir las potencias de 3 menores que 200, se cambian dos cosas: la condición (a < 200) y el factor (a ← a * 3). Saldría 1, 3, 9, 27, 81.
Analiza el siguiente algoritmo: a) Indica qué números escribe, en orden, y explica por qué el ciclo se detiene. b) Describe qué cambio harías para que el algoritmo…
Analiza el siguiente algoritmo:
a ← 1
mientras a < 50:
escribir a
a ← a * 2
- a) Indica qué números escribe, en orden, y explica por qué el ciclo se detiene.
- b) Describe qué cambio harías para que el algoritmo escriba las potencias de 3 menores que 200.
Algoritmo de primalidad y raíz cuadrada
Para decidir si $n$ es primo, probamos si algún número desde 2 lo divide. ¿Hasta dónde hay que llegar? Hasta $\sqrt{n}$.
leer n
primo ← verdadero
para d desde 2 hasta raíz(n):
si n mod d = 0 entonces
primo ← falso
escribir primo
(n mod d es el resto de dividir $n$ por $d$.)
Vuelve al principio: 91 no es primo, y con solo 6 pruebas lo sabemos. Para $n = 10.000$ se prueban 100 números, no 9.998.
Un algoritmo decide si un número natural $n > 1$ es primo probando si algún número desde 2 hasta $\sqrt{n}$ lo divide exactamente. a) Aplica el algoritmo al número 91 y…
Un algoritmo decide si un número natural $n > 1$ es primo probando si algún número desde 2 hasta $\sqrt{n}$ lo divide exactamente.
- a) Aplica el algoritmo al número 91 y escribe qué divisores prueba y qué concluye.
- b) Explica por qué basta con probar divisores hasta $\sqrt{n}$ y no es necesario llegar hasta $n - 1$.
Fibonacci y divisores en pseudocódigo
Fibonacci. Se guardan los dos últimos términos y se calcula el siguiente. Los primeros 8 términos: 1, 1, 2, 3, 5, 8, 13, 21.
leer n
a ← 1
b ← 1
para i desde 1 hasta n:
escribir a
c ← a + b
a ← b
b ← c
Seguimiento con $n = 4$: se escribe 1 (a=1,b=1→ a=1,b=2), luego 1 (a=1,b=2→ a=2,b=3), luego 2, luego 3.
Divisores. Se recorren los candidatos y se cuenta cuántos dividen exactamente.
leer n
cantidad ← 0
para d desde 1 hasta n:
si n mod d = 0 entonces
escribir d
cantidad ← cantidad + 1
escribir cantidad
Mejora. Si $d$ divide a $n$, también lo hace $n \div d$: cada divisor pequeño da uno grande. Basta recorrer $d$ hasta $\sqrt{n}$ y anotar ambos. Para $n = 10.000$ se hacen unas 100 divisiones en vez de 10.000: 100 veces menos trabajo.
En la sucesión de Fibonacci, los dos primeros términos son 1 y 1, y cada término siguiente es la suma de los dos anteriores. a) Escribe los primeros 8 términos. b)…
En la sucesión de Fibonacci, los dos primeros términos son 1 y 1, y cada término siguiente es la suma de los dos anteriores.
- a) Escribe los primeros 8 términos.
- b) Escribe en pseudocódigo (o en el lenguaje de programación que uses en clases) un algoritmo que reciba un número $n$ y muestre los primeros $n$ términos de la sucesión.
Diseña un algoritmo que reciba un número natural $n$, construya la lista de todos sus divisores positivos y cuente cuántos son. a) Escribe el algoritmo en pseudocódigo o…
Diseña un algoritmo que reciba un número natural $n$, construya la lista de todos sus divisores positivos y cuente cuántos son.
- a) Escribe el algoritmo en pseudocódigo o en el lenguaje que uses en clases.
- b) Explica cómo usarías el resultado para decidir si $n$ es primo y aplícalo a $n = 36$ y a $n = 37$.
- c) Si $n = 10.000$, compara cuántas divisiones haría tu algoritmo si prueba todos los números de 1 a $n$ con las que haría si solo prueba hasta $\sqrt{n}$ (recuerda que cada divisor pequeño permite obtener otro grande). Comenta qué ventaja tiene esa mejora.
La criba de Eratóstenes
¿Y si quieres todos los primos hasta 30? Probar cada número por separado funciona, pero hay un método más ingenioso, la criba de Eratóstenes:
-
Escribe los números del 2 al $N$.
-
Toma el primer número no tachado (será primo) y tacha todos sus múltiplos posteriores.
-
Repite con el siguiente número sin tachar, hasta pasar $\sqrt{N}$.
-
Los que quedan sin tachar son los primos.
¿Por qué basta hasta $\sqrt{30}$? Un número compuesto $\le 30$ tiene un factor $\le \sqrt{30}$, así que ya fue tachado como múltiplo de un primo $\le 5$.
¿Cuál conviene? La criba es muy eficiente cuando necesitas muchos primos seguidos (una lista hasta un límite). Probar la primalidad por separado conviene cuando tienes un número grande aislado, porque la criba obligaría a construir toda la lista hasta ese número.
La criba de Eratóstenes es un algoritmo para obtener todos los números primos hasta un límite dado. a) Describe sus pasos con tus palabras y aplícala a los números del 2…
La criba de Eratóstenes es un algoritmo para obtener todos los números primos hasta un límite dado.
- a) Describe sus pasos con tus palabras y aplícala a los números del 2 al 30, indicando qué números se tachan en cada etapa y cuáles quedan.
- b) Explica por qué basta con tachar múltiplos de los primos hasta $\sqrt{30}$.
- c) Compara este método con probar la primalidad de cada número por separado, y argumenta cuándo conviene cada uno.