Ejercicios Matemáticos - Programación 1

Acerca de¶

Estos ejercicios están centrados en algoritmos de teoría de números y operaciones matemáticas en C. Te permitirán comprender cómo se implementan los cálculos matemáticos de forma iterativa y condicional, y cómo manejar las limitaciones de precisión de las variables.

Capítulos de Apunte Correspondientes¶

Cuestiones de Estilo Aplicables¶

Desbordamientos numéricos: Es fundamental elegir los tipos de datos apropiados (long long, unsigned long long) al realizar operaciones como factoriales para evitar desbordamientos aritméticos (ver Introducción).
Uso de tipos reales: Al dividir enteros para obtener coeficientes reales, recordá realizar el cast explícito o usar constantes reales (como 2.0) para prevenir la truncación no deseada por división entera.

Aritmética Lenta¶

Ejercicio 3.1 - Suma lenta ⭐⭐☆☆☆¶

Descripción¶

Implementar una función que simule la adición de dos números enteros, n y m, utilizando únicamente las operaciones más básicas de la unidad aritmético-lógica: sumar o restar 1. Este ejercicio ayuda a comprender la suma como una serie de incrementos o decrementos sucesivos.

Ayuda (pseudocódigo)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
FUNCION suma_lenta(n, m)
VARIABLES:
    resultado (entero)
INICIO
    resultado = n
    SI m > 0 ENTONCES
        PARA i DESDE 1 HASTA m HACER
            resultado = resultado + 1
        FIN PARA
    SINO
        PARA i DESDE 1 HASTA VALOR_ABSOLUTO(m) HACER
            resultado = resultado - 1
        FIN PARA
    FIN SI
    RETORNAR resultado
FIN FUNCION

Ejercicio 3.2 - División lenta ⭐⭐☆☆☆¶

Descripción¶

Implementar la división entera para obtener el cociente y el resto de a / b utilizando únicamente restas sucesivas. Este método emula cómo se podría realizar una división de forma manual o en hardware muy simple.

Ayuda (pseudocódigo)

1
2
3
4
5
6
7
8
9
PROCEDIMIENTO division_lenta(dividendo, divisor, REF cociente, REF resto)
INICIO
    cociente = 0
    MIENTRAS dividendo >= divisor HACER
        dividendo = dividendo - divisor
        cociente = cociente + 1
    FIN MIENTRAS
    resto = dividendo
FIN PROCEDIMIENTO

Ejercicio 3.3 - División egipcia ⭐⭐☆☆☆¶

Descripción¶

Implementar el antiguo método de división egipcio, que no requiere tablas de multiplicar ni operaciones de división directa. Se basa en duplicar el divisor, encontrar qué duplicaciones suman el dividendo y sumar los factores de duplicación correspondientes.

Lógica y Consideraciones

Entrada: Un dividendo y un divisor.
Proceso:
1. Tabla de Duplicación: Crear dos columnas. La primera empieza en 1 y la segunda en el divisor. En cada paso, duplicar el valor de la fila anterior en ambas columnas. Detenerse cuando el siguiente valor en la columna del divisor supere al dividendo.
2. Búsqueda y Suma: Recorrer la tabla de abajo hacia arriba. Para cada fila, si el valor en la columna del divisor es menor o igual al dividendo restante, se resta ese valor del dividendo y se suma el valor correspondiente de la primera columna al cociente.
Salida: El cociente acumulado y el dividendo final (que es el resto).
[plus ultra]: Optimizar el acceso a memoria respetando el orden por filas (row-major order) para mejorar el uso de caché.
[plus ultra]: Validar que los índices ingresados se encuentren estrictamente dentro de los límites del contenedor.

Ayuda (pseudocódigo)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
PROCEDIMIENTO division_egipcia(dividendo, divisor, REF cociente, REF resto)
VARIABLES:
    col1, col2 (arreglos)
    i (entero)
INICIO
    // 1. Crear tabla
    col1[0] = 1, col2[0] = divisor
    i = 0
    MIENTRAS col2[i] <= dividendo HACER
        i = i + 1
        col1[i] = col1[i-1] * 2
        col2[i] = col2[i-1] * 2
    FIN MIENTRAS

    // 2. Buscar y sumar
    cociente = 0
    PARA j DESDE i-1 HASTA 0 CON PASO -1 HACER
        SI col2[j] <= dividendo ENTONCES
            dividendo = dividendo - col2[j]
            cociente = cociente + col1[j]
        FIN SI
    FIN PARA
    resto = dividendo
FIN PROCEDIMIENTO

Divisibilidad y Factores¶

Ejercicio 3.4 - Divisibilidad ⭐⭐☆☆☆¶

Descripción¶

Determinar si un número entero a es divisible de forma exacta por otro entero b.

Ayuda (pseudocódigo)

1
2
3
4
5
6
7
8
9
10
11
FUNCION es_divisible(a, b)
INICIO
    SI b == 0 ENTONCES
        RETORNAR FALSO // O manejar como error
    FIN SI
    SI a MOD b == 0 ENTONCES
        RETORNAR VERDADERO
    SINO
        RETORNAR FALSO
    FIN SI
END FUNCION

Ejercicio 3.5 - Factorial ⭐⭐☆☆☆¶

Descripción¶

Calcular el factorial de un número entero no negativo n, denotado como n!. El factorial es el producto de todos los enteros positivos desde 1 hasta n.

Ayuda (pseudocódigo)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
FUNCION factorial(n)
VARIABLES:
    resultado (entero largo)
INICIO
    SI n < 0 ENTONCES
        RETORNAR -1 // Error
    FIN SI
    SI n == 0 ENTONCES
        RETORNAR 1
    FIN SI

    resultado = 1
    PARA i DESDE 2 HASTA n HACER
        resultado = resultado * i
    FIN PARA
    RETORNAR resultado
FIN FUNCION

Ejercicio 3.6 - MCD y MCM ⭐⭐☆☆☆¶

Descripción¶

Implementar funciones para calcular el Máximo Común Divisor (MCD) y el Mínimo Común Múltiplo (MCM) de dos números enteros.

Ayuda (pseudocódigo)

1
2
3
4
5
6
7
8
9
10
11
FUNCION mcd(a, b)
VARIABLES:
    temporal (entero)
INICIO
    MIENTRAS b != 0 HACER
        temporal = b
        b = a MOD b
        a = temporal
    FIN MIENTRAS
    RETORNAR a
FIN FUNCION

Propiedades de los Números¶

Ejercicio 3.7 - Suma de dígitos ⭐⭐☆☆☆¶

Descripción¶

Calcular la suma de los dígitos individuales de un número entero positivo.

Ayuda (pseudocódigo)

1
2
3
4
5
6
7
8
9
10
11
FUNCION sumar_digitos(n)
VARIABLES:
    suma (entero)
INICIO
    suma = 0
    MIENTRAS n > 0 HACER
        suma = suma + (n MOD 10)
        n = n / 10
    FIN MIENTRAS
    RETORNAR suma
FIN FUNCION

Ejercicio 3.8 - Invertir un número ⭐⭐☆☆☆¶

Descripción¶

Tomar un número entero y devolver otro número con sus dígitos en orden inverso.

Ayuda (pseudocódigo)

1
2
3
4
5
6
7
8
9
10
11
FUNCION invertir_numero(n)
VARIABLES:
    invertido (entero)
INICIO
    invertido = 0
    MIENTRAS n > 0 HACER
        invertido = (invertido * 10) + (n MOD 10)
        n = n / 10
    FIN MIENTRAS
    RETORNAR invertido
FIN FUNCION

Ejercicio 3.9 - Capicúas ⭐⭐⭐⭐☆¶

Descripción¶

Verificar si un número es capicúa (o palíndromo), es decir, si se lee igual de izquierda a derecha que de derecha a izquierda.

Ayuda (pseudocódigo)

1
2
3
4
5
6
7
8
FUNCION es_capicua(n)
INICIO
    SI n == invertir_numero(n) ENTONCES
        RETORNAR VERDADERO
    SINO
        RETORNAR FALSO
    FIN SI
FIN FUNCION

Ejercicio 3.10 - Números Primos ⭐⭐☆☆☆¶

Descripción¶

Verificar si un número entero mayor que 1 es un número primo. Un número es primo si solo es divisible por 1 y por sí mismo.

Ayuda (pseudocódigo)

1
2
3
4
5
6
7
8
9
10
FUNCION es_primo(n)
INICIO
    SI n <= 1 ENTONCES RETORNAR FALSO
    PARA i DESDE 2 HASTA RAIZ_CUADRADA(n) HACER
        SI n MOD i == 0 ENTONCES
            RETORNAR FALSO
        FIN SI
    FIN PARA
    RETORNAR VERDADERO
FIN FUNCION

Ejercicio 3.11 - Números Perfectos ⭐⭐☆☆☆¶

Descripción¶

Determinar si un número es un “número perfecto”. Un número perfecto es un entero positivo que es igual a la suma de sus divisores propios positivos (todos sus divisores excepto él mismo).

Ayuda (pseudocódigo)

1
2
3
4
5
6
7
8
9
10
11
12
FUNCION es_perfecto(n)
VARIABLES:
    suma_divisores (entero)
INICIO
    suma_divisores = 0
    PARA i DESDE 1 HASTA n-1 HACER
        SI n MOD i == 0 ENTONCES
            suma_divisores = suma_divisores + i
        FIN SI
    FIN PARA
    RETORNAR (suma_divisores == n)
FIN FUNCION

Ejercicio 3.12 - Números Amigos ⭐⭐☆☆☆¶

Descripción¶

Verificar si dos números enteros positivos, a y b, son “números amigos”. Dos números son amigos si la suma de los divisores propios de a es igual a b, y viceversa.

Lógica y Consideraciones

Entrada: Dos enteros positivos, a y b.
Reutilización de Código: Este problema se simplifica si ya se tiene una función que calcula la suma de los divisores propios de un número (como la usada en el ejercicio de “Números Perfectos”).
Proceso:
1. Calcular la suma de los divisores propios de a. Llamémosla suma_div_a.
2. Calcular la suma de los divisores propios de b. Llamémosla suma_div_b.
3. Verificar si se cumplen las dos condiciones: suma_div_a == b Y suma_div_b == a.
Caso Especial: Asegurarse de que a y b no sean el mismo número (un número perfecto es amigo de sí mismo, lo que a veces se excluye de la definición de números amigos).
[plus ultra]: Diseñar la función para devolver un código de estado de error e informar el resultado mediante parámetros de salida.
[plus ultra]: Documentar la función con etiquetas Doxygen especificando precondiciones y postcondiciones.

Ayuda (pseudocódigo)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
FUNCION suma_divisores_propios(n)
    // ... implementación como en el ejercicio de Números Perfectos ...
FIN FUNCION

FUNCION son_amigos(a, b)
INICIO
    // Opcional: excluir números perfectos
    SI a == b ENTONCES
        RETORNAR FALSO
    FIN SI

    suma_a = suma_divisores_propios(a)
    suma_b = suma_divisores_propios(b)

    SI suma_a == b Y suma_b == a ENTONCES
        RETORNAR VERDADERO
    SINO
        RETORNAR FALSO
    FIN SI
FIN FUNCION

Ejercicio 3.13 - Números Abundantes ⭐⭐☆☆☆¶

Descripción¶

Determinar si un número es “abundante”. Un número es abundante si la suma de sus divisores propios es mayor que el propio número.

Ayuda (pseudocódigo)

1
2
3
4
5
6
7
8
9
10
11
12
FUNCION es_abundante(n)
VARIABLES:
    suma_divisores (entero)
INICIO
    suma_divisores = 0
    PARA i DESDE 1 HASTA n-1 HACER
        SI n MOD i == 0 ENTONCES
            suma_divisores = suma_divisores + i
        FIN SI
    FIN PARA
    RETORNAR (suma_divisores > n)
FIN FUNCION

Ejercicio 3.14 - Conjetura de Collatz ⭐⭐☆☆☆¶

Descripción¶

Implementar la secuencia de Collatz para un número inicial n. La secuencia se genera aplicando repetidamente una regla: si el número actual es par, se divide por 2; si es impar, se multiplica por 3 y se le suma 1. La conjetura (no probada) es que esta secuencia siempre llega a 1.

Ayuda (pseudocódigo)

1
2
3
4
5
6
7
8
9
10
11
12
PROCEDIMIENTO secuencia_collatz(n)
INICIO
    MIENTRAS n != 1 HACER
        ESCRIBIR n
        SI n MOD 2 == 0 ENTONCES
            n = n / 2
        SINO
            n = 3 * n + 1
        FIN SI
    FIN MIENTRAS
    ESCRIBIR 1 // El último término de la secuencia
FIN PROCEDIMIENTO

Ejercicio 3.15 - Números de Armstrong ⭐⭐☆☆☆¶

Descripción¶

Verificar si un número es un número de Armstrong (o narcisista). Un número de k dígitos es de Armstrong si es igual a la suma de sus propios dígitos elevados a la potencia k.

Ayuda (pseudocódigo)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
FUNCION es_armstrong(n)
VARIABLES:
    k, suma, temp, digito (enteros)
INICIO
    k = contar_digitos(n)
    suma = 0
    temp = n

    MIENTRAS temp > 0 HACER
        digito = temp MOD 10
        suma = suma + potencia(digito, k)
        temp = temp / 10
    FIN MIENTRAS

    RETORNAR (suma == n)
FIN FUNCION

Ejercicio 3.16 - Números Felices ⭐⭐☆☆☆¶

Descripción¶

Determinar si un número es un “número feliz”. El proceso consiste en reemplazar el número por la suma de los cuadrados de sus dígitos repetidamente. Si el proceso llega a 1, el número es feliz. Si entra en un ciclo que no incluye el 1 (notablemente el ciclo 4 → 16 → 37 → 58 → 89 → 145 → 42 → 20 → 4), no es feliz.

Ayuda (pseudocódigo)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
FUNCION es_feliz(n)
INICIO
    MIENTRAS n != 1 Y n != 4 HACER
        suma_cuadrados = 0
        temp = n
        MIENTRAS temp > 0 HACER
            digito = temp MOD 10
            suma_cuadrados = suma_cuadrados + digito * digito
            temp = temp / 10
        FIN MIENTRAS
        n = suma_cuadrados
    FIN MIENTRAS

    RETORNAR (n == 1)
FIN FUNCION

Algoritmos Numéricos Avanzados¶

Ejercicio 3.17 - Criba de Eratóstenes ⭐⭐☆☆☆¶

Descripción¶

Implementar la Criba de Eratóstenes, un algoritmo altamente eficiente para encontrar todos los números primos hasta un límite superior N especificado.

Lógica y Consideraciones

Estructura de Datos: Se necesita un arreglo booleano (o de enteros) es_primo de tamaño N+1. es_primo[i] será verdadero si i es primo y falso en caso contrario.
Inicialización: Se inicializa todo el arreglo a verdadero, asumiendo que todos los números son primos al principio. Luego, se marcan 0 y 1 como no primos.
Proceso:
1. Se itera con un número p desde 2 hasta $\sqrt{N}$ .
2. Si p sigue marcado como primo (es_primo[p] es verdadero): a. Se itera a través de todos los múltiplos de p (comenzando desde p*p) y se marcan como no primos (es_primo[multiplo] = falso). Se empieza en p*p porque los múltiplos menores ya habrán sido marcados por primos más pequeños.
Salida: Al final, se recorre el arreglo es_primo y se imprimen todos los índices i para los cuales es_primo[i] es verdadero.
[plus ultra]: Garantizar la terminación con \0 y prevenir desbordamientos de búfer validando la capacidad máxima.
[plus ultra]: Soportar la lectura de cadenas con espacios y múltiples líneas de manera robusta.

Ayuda (pseudocódigo)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
PROCEDIMIENTO criba_eratostenes(N)
VARIABLES:
    es_primo (arreglo booleano de tamaño N+1)

INICIO
    // Inicialización
    PARA i DESDE 0 HASTA N HACER
        es_primo[i] = VERDADERO
    FIN PARA
    es_primo[0] = FALSO, es_primo[1] = FALSO

    // Marcado de múltiplos
    PARA p DESDE 2 HASTA RAIZ_CUADRADA(N) HACER
        SI es_primo[p] == VERDADERO ENTONCES
            PARA i DESDE p*p HASTA N CON PASO p HACER
                es_primo[i] = FALSO
            FIN PARA
        FIN SI
    FIN PARA

    // Imprimir resultados
    ESCRIBIR "Números primos hasta ", N, ":"
    PARA i DESDE 2 HASTA N HACER
        SI es_primo[i] == VERDADERO ENTONCES
            ESCRIBIR i
        FIN SI
    FIN PARA
FIN PROCEDIMIENTO

Ejercicio 3.18 - Descomposición en Factores Primos ⭐⭐☆☆☆¶

Descripción¶

Dado un número entero, encontrar y mostrar su descomposición en factores primos. Por ejemplo, para 360, la salida sería 2^3 * 3^2 * 5.

Ayuda (pseudocódigo)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
PROCEDIMIENTO factores_primos(n)
VARIABLES:
    contador (entero)
INICIO
    // Manejar el factor 2
    contador = 0
    MIENTRAS n MOD 2 == 0 HACER
        contador = contador + 1
        n = n / 2
    FIN MIENTRAS
    SI contador > 0 ENTONCES ESCRIBIR "2^", contador

    // Manejar factores impares
    PARA i DESDE 3 HASTA RAIZ_CUADRADA(n) CON PASO 2 HACER
        contador = 0
        MIENTRAS n MOD i == 0 HACER
            contador = contador + 1
            n = n / i
        FIN MIENTRAS
        SI contador > 0 ENTONCES ESCRIBIR i, "^", contador
    FIN PARA

    // Si n es primo > 2
    SI n > 2 ENTONCES
        ESCRIBIR n, "^1"
    FIN SI
FIN PROCEDIMIENTO

Ejercicio 3.19 - Números de Catalan ⭐⭐☆☆☆¶

Descripción¶

Implementar una función que calcule el n-ésimo número de Catalan, $C_n$ . Estos números forman una secuencia de números naturales que aparece en varios problemas de conteo en combinatoria.

Lógica y Consideraciones

Entrada: Un entero no negativo n.
Fórmula: La fórmula más directa es $C_n = \frac{1}{n+1} \binom{2n}{n}$ . Para calcularla, se necesita una función para el coeficiente binomial $\binom{n}{k}$ .
Coeficiente Binomial: $\binom{n}{k}$ se puede calcular como $\frac{n!}{k!(n-k)!}$ . Sin embargo, calcular los factoriales directamente puede causar desbordamiento muy rápido. Una forma más segura es calcularlo iterativamente: $\binom{n}{k} = \prod_{i=1}^{k} \frac{n-i+1}{i}$ .
Proceso:
1. Implementar una función coeficiente_binomial(n, k).
2. La función numero_catalan(n) llamará a coeficiente_binomial(2*n, n) y dividirá el resultado por n+1.
[plus ultra]: Implementar encapsulamiento completo manteniendo la definición interna oculta en el archivo .c.
[plus ultra]: Añadir una función de duplicación profunda (deep copy) para copiar la estructura de forma segura.

Ayuda (pseudocódigo)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
FUNCION coeficiente_binomial(n, k)
    SI k < 0 O k > n ENTONCES
        RETORNAR 0
    FIN SI
    SI k == 0 O k == n ENTONCES
        RETORNAR 1
    FIN SI
    SI k > n / 2 ENTONCES
        k = n - k
    FIN SI

    resultado = 1
    PARA i DESDE 1 HASTA k HACER
        resultado = resultado * (n - i + 1) / i
    FIN PARA
    RETORNAR resultado
FIN FUNCION

FUNCION numero_catalan(n)
INICIO
    // C_n = C(2n, n) / (n+1)
    c = coeficiente_binomial(2 * n, n)
    RETORNAR c / (n + 1)
FIN FUNCION

Ejercicio 3.20 - Coeficiente Binomial ⭐⭐☆☆☆¶

Descripción¶

Calcular el coeficiente binomial “n en k”, denotado como $C(n, k)$ o $\binom{n}{k}$ , que representa el número de formas de elegir k elementos de un conjunto de n elementos sin importar el orden.

Lógica y Consideraciones

Entrada: Dos enteros no negativos, n y k.
Proceso: Como se mencionó en el ejercicio anterior, calcularlo mediante la fórmula iterativa $\prod_{i=1}^{k} \frac{n-i+1}{i}$ es numéricamente más estable que usar factoriales. Es importante realizar la multiplicación antes de la división en cada paso para mantener la precisión y evitar divisiones prematuras.
Optimización: Dado que $\binom{n}{k} = \binom{n}{n-k}$ , se puede elegir el valor más pequeño entre k y n-k para reducir el número de iteraciones.
[plus ultra]: Implementar encapsulamiento completo manteniendo la definición interna oculta en el archivo .c.
[plus ultra]: Añadir una función de duplicación profunda (deep copy) para copiar la estructura de forma segura.

Ayuda (pseudocódigo)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
FUNCION coeficiente_binomial(n, k)
    SI k < 0 O k > n ENTONCES
        RETORNAR 0
    FIN SI
    SI k == 0 O k == n ENTONCES
        RETORNAR 1
    FIN SI
    // Optimización
    SI k > n / 2 ENTONCES
        k = n - k
    FIN SI

    resultado = 1
    PARA i DESDE 1 HASTA k HACER
        resultado = resultado * (n - i + 1) / i
    FIN PARA
    RETORNAR resultado
FIN FUNCION

Ejercicio 3.21 - Raíz Cuadrada Entera (Método Babilónico) ⭐⭐☆☆☆¶

Descripción¶

Implementar un algoritmo para calcular la parte entera de la raíz cuadrada de un número n utilizando el método babilónico (o de Herón), que es un método iterativo eficiente.

Ayuda (pseudocódigo)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
FUNCION raiz_cuadrada_entera(n)
VARIABLES:
    x (real)
INICIO
    SI n < 0 RETORNAR -1 // Error
    SI n == 0 RETORNAR 0

    x = n
    // Iterar un número fijo de veces para aproximar
    PARA i DESDE 1 HASTA 10 HACER
        x = (x + n / x) / 2
    FIN PARA

    RETORNAR PARTE_ENTERA(x)
FIN FUNCION

Ejercicio 3.22 - Números Triangulares ⭐⭐☆☆☆¶

Descripción¶

Un número triangular es la suma de los n primeros números naturales. Por ejemplo, el 4º número triangular es 1+2+3+4=10. El objetivo es escribir una función que determine si un número entero dado es un número triangular.

Ayuda (pseudocódigo)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
FUNCION es_triangular(num)
VARIABLES:
    suma, i (enteros)
INICIO
    SI num < 0 RETORNAR FALSO

    suma = 0
    i = 1
    MIENTRAS suma < num HACER
        suma = suma + i
        i = i + 1
    FIN MIENTRAS

    RETORNAR (suma == num)
FIN FUNCION

Ejercicio 3.23 - Conjetura de Goldbach ⭐⭐☆☆☆¶

Descripción¶

La conjetura de Goldbach (aún no probada) establece que todo número par mayor que 2 puede expresarse como la suma de dos números primos. Escribir un programa que, dado un número par, encuentre un par de números primos que lo sumen.

Ayuda (pseudocódigo)

1
2
3
4
5
6
7
8
9
PROCEDIMIENTO encontrar_par_goldbach(n)
INICIO
    PARA p DESDE 2 HASTA n / 2 HACER
        SI es_primo(p) Y es_primo(n - p) ENTONCES
            ESCRIBIR n, " = ", p, " + ", n - p
            TERMINAR
        FIN SI
    FIN PARA
FIN PROCEDIMIENTO

Ejercicio 3.24 - Primos Gemelos ⭐⭐☆☆☆¶

Descripción¶

Dos números primos p y q son gemelos si q = p + 2. El programa debe encontrar todos los pares de primos gemelos hasta un límite N.

Ayuda (pseudocódigo)

1
2
3
4
5
6
7
8
PROCEDIMIENTO primos_gemelos(N)
INICIO
    PARA p DESDE 2 HASTA N - 2 HACER
        SI es_primo(p) Y es_primo(p + 2) ENTONCES
            ESCRIBIR "(", p, ", ", p + 2, ")"
        FIN SI
    FIN PARA
FIN PROCEDIMIENTO

Ejercicio 3.25 - Identidad de Bézout ⭐⭐☆☆☆¶

Descripción¶

Extender el Algoritmo de Euclides para encontrar no solo el MCD de dos enteros a y b, sino también dos enteros x e y que satisfacen la identidad de Bézout: $ax + by = mcd(a, b)$ .

Ayuda (pseudocódigo)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
FUNCION mcd_extendido(a, b, REF x, REF y)
INICIO
    SI a == 0 ENTONCES
        x = 0
        y = 1
        RETORNAR b
    FIN SI

    x1, y1 (enteros)
    mcd = mcd_extendido(b MOD a, a, REF x1, REF y1)

    x = y1 - (b / a) * x1
    y = x1

    RETORNAR mcd
FIN FUNCION

Ejercicio 3.26 - Cálculo de Pi (Serie de Leibniz) ⭐⭐☆☆☆¶

Descripción¶

Aproximar el valor de $\pi$ utilizando la serie de Leibniz. La función debe recibir el número de términos a utilizar para la aproximación.

Ayuda (pseudocódigo)

1
2
3
4
5
6
7
8
9
10
11
FUNCION aproximar_pi(n_terminos)
VARIABLES:
    suma (real)
INICIO
    suma = 0.0
    PARA k DESDE 0 HASTA n_terminos - 1 HACER
        termino = potencia(-1, k) / (2.0 * k + 1.0)
        suma = suma + termino
    FIN PARA
    RETORNAR 4.0 * suma
FIN FUNCION

Ejercicio 3.27 - Números de Lucas ⭐⭐☆☆☆¶

Descripción¶

Generar los primeros n términos de la secuencia de Lucas. Es una secuencia similar a la de Fibonacci, pero comienza con 2 y 1.

Ayuda (pseudocódigo)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
PROCEDIMIENTO secuencia_lucas(n)
VARIABLES:
    a, b, siguiente (enteros)
INICIO
    SI n >= 1 ENTONCES ESCRIBIR 2
    SI n >= 2 ENTONCES ESCRIBIR 1

    a = 2, b = 1
    PARA i DESDE 3 HASTA n HACER
        siguiente = a + b
        ESCRIBIR siguiente
        a = b
        b = siguiente
    FIN PARA
FIN PROCEDIMIENTO

Ejercicio 3.28 - Números de Mersenne ⭐⭐☆☆☆¶

Descripción¶

Un número de Mersenne es un número de la forma $M_p = 2^p - 1$ , donde p es un número primo. El programa debe generar números de Mersenne y verificar si son a su vez primos (primos de Mersenne).

Ayuda (pseudocódigo)

1
2
3
4
5
6
7
8
9
10
11
PROCEDIMIENTO primos_de_mersenne(limite_p)
INICIO
    PARA p DESDE 2 HASTA limite_p HACER
        SI es_primo(p) ENTONCES
            m = potencia(2, p) - 1
            SI es_primo(m) ENTONCES
                ESCRIBIR "M(", p, ") = ", m, " es un primo de Mersenne."
            FIN SI
        FIN SI
    FIN PARA
FIN PROCEDIMIENTO

Ejercicio 3.29 - Test de Primalidad de Miller-Rabin ⭐⭐☆☆☆¶

Descripción¶

Implementar una versión simplificada del test de primalidad de Miller-Rabin. Es un test probabilístico que, a diferencia de la división por tentativa, es eficiente para números grandes.

Lógica y Consideraciones

Teorema: Se basa en propiedades de los números primos relacionadas con el Pequeño Teorema de Fermat. Es más complejo que los algoritmos anteriores.
Proceso Simplificado:
1. Dado un número n a probar, se eligen varias bases aleatorias a < n.
2. Para cada base a, se comprueba si satisface ciertas congruencias. Si para alguna base no las satisface, n es compuesto. Si las satisface para todas las bases, es “probablemente primo”.
Nota: La implementación completa es avanzada. Un ejercicio más simple puede ser implementarlo para una sola base fija.
[plus ultra]: Diseñar la función para devolver un código de estado de error e informar el resultado mediante parámetros de salida.
[plus ultra]: Documentar la función con etiquetas Doxygen especificando precondiciones y postcondiciones.

Ayuda (pseudocódigo)

1
2
3
4
5
6
7
8
9
10
11
12
FUNCION es_probablemente_primo(n, k_iteraciones)
INICIO
    // ... Lógica compleja del test de Miller-Rabin ...
    // Descomponer n-1 en d * 2^s
    // Repetir k veces:
    //   Elegir 'a' aleatorio en [2, n-2]
    //   Calcular x = a^d mod n
    //   Si x == 1 o x == n-1, continuar
    //   ... (lazo para s-1) ...
    // Si no pasa las pruebas, RETORNAR FALSO
    RETORNAR VERDADERO
FIN FUNCION

Ejercicio 3.30 - Números Vampiro ⭐⭐☆☆☆¶

Descripción¶

Un número vampiro es un número de 2k dígitos que puede ser factorizado en dos números de k dígitos (los “colmillos”), donde los dígitos de los colmillos, concatenados, son una permutación de los dígitos del número original.

Ayuda (pseudocódigo)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
FUNCION es_vampiro_4_digitos(n)
INICIO
    PARA i DESDE 10 HASTA 99 HACER
        PARA j DESDE i HASTA 99 HACER
            SI i * j == n ENTONCES
                digitos_n = obtener_digitos_ordenados(n)
                digitos_colmillos = obtener_digitos_ordenados(i, j)
                SI digitos_n == digitos_colmillos ENTONCES
                    RETORNAR VERDADERO
                FIN SI
            FIN SI
        FIN PARA
    FIN PARA
    RETORNAR FALSO
FIN FUNCION

Ejercicio 3.31 - Cuadrado Mágico ⭐⭐☆☆☆¶

Descripción¶

Verificar si una matriz cuadrada n x n de números es un cuadrado mágico. Un cuadrado mágico es una matriz donde la suma de los números de cada fila, cada columna y ambas diagonales principales es la misma (“constante mágica”).

Ayuda (pseudocódigo)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
FUNCION es_cuadrado_magico(matriz, n)
VARIABLES:
    constante_magica, suma_actual (entero)
INICIO
    // Calcular constante de referencia
    constante_magica = suma_fila(matriz, 0)

    // Verificar filas y columnas
    PARA i DESDE 1 HASTA n-1 HACER
        SI suma_fila(matriz, i) != constante_magica RETORNAR FALSO
        SI suma_columna(matriz, i) != constante_magica RETORNAR FALSO
    FIN PARA

    // Verificar diagonales
    SI suma_diagonal_principal(matriz) != constante_magica RETORNAR FALSO
    SI suma_diagonal_secundaria(matriz) != constante_magica RETORNAR FALSO

    RETORNAR VERDADERO
FIN FUNCION

Más Teoría de Números y Algoritmos¶

Ejercicio 3.32 - Números de Smith ⭐⭐☆☆☆¶

Descripción¶

Un número de Smith es un número compuesto cuya suma de dígitos es igual a la suma de los dígitos de sus factores primos. El programa debe verificar si un número dado es un número de Smith.

Ayuda (pseudocódigo)

1
2
3
4
5
6
7
8
9
10
11
12
13
FUNCION es_numero_smith(n)
INICIO
    SI es_primo(n) RETORNAR FALSO

    suma_digitos_n = sumar_digitos(n)
    suma_digitos_factores = 0
    temp_n = n

    // Lógica para obtener factores primos y sumar sus dígitos
    // ... (similar a la descomposición en factores primos)

    RETORNAR (suma_digitos_n == suma_digitos_factores)
FIN FUNCION

Ejercicio 3.33 - Primos de Sophie Germain ⭐⭐☆☆☆¶

Descripción¶

Un número primo p es un primo de Sophie Germain si 2p + 1 también es un número primo. El programa debe encontrar todos los primos de Sophie Germain hasta un límite N.

Ayuda (pseudocódigo)

1
2
3
4
5
6
7
8
PROCEDIMIENTO primos_sophie_germain(N)
INICIO
    PARA p DESDE 2 HASTA N HACER
        SI es_primo(p) Y es_primo(2*p + 1) ENTONCES
            ESCRIBIR p
        FIN SI
    FIN PARA
FIN PROCEDIMIENTO

Ejercicio 3.34 - Función φ de Euler (Totient) ⭐⭐☆☆☆¶

Descripción¶

Implementar una función que calcule el Totient de Euler, φ(n). Esta función cuenta el número de enteros positivos hasta n que son coprimos con n (es decir, mcd(k, n) = 1 para 1 <= k <= n).

Ayuda (pseudocódigo)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
FUNCION phi_euler(n)
VARIABLES:
    resultado (real)
INICIO
    resultado = n
    p = 2
    temp_n = n
    MIENTRAS p*p <= temp_n HACER
        SI temp_n MOD p == 0 ENTONCES
            MIENTRAS temp_n MOD p == 0 HACER
                temp_n = temp_n / p
            FIN MIENTRAS
            resultado = resultado * (1.0 - (1.0 / p))
        FIN SI
        p = p + 1
    FIN MIENTRAS
    SI temp_n > 1 ENTONCES
        resultado = resultado * (1.0 - (1.0 / temp_n))
    FIN SI
    RETORNAR PARTE_ENTERA(resultado)
FIN FUNCION

Ejercicio 3.35 - Radical de un Número ⭐⭐☆☆☆¶

Descripción¶

Calcular el radical de un número n, denotado como rad(n), que es el producto de sus factores primos distintos.

Ayuda (pseudocódigo)

1
2
3
4
5
6
7
8
9
FUNCION radical(n)
VARIABLES:
    resultado (entero)
INICIO
    resultado = 1
    // Lógica para encontrar factores primos distintos y multiplicarlos
    // ...
    RETORNAR resultado
FIN FUNCION

Ejercicio 3.36 - Secuencia de Tribonacci ⭐⭐☆☆☆¶

Descripción¶

Generar los primeros n términos de la secuencia de Tribonacci, donde cada término es la suma de los tres anteriores. La secuencia puede comenzar de diferentes formas, una común es 0, 1, 1, 2, 4, 7, 13, ...

Ayuda (pseudocódigo)

1
2
3
4
5
6
7
8
9
10
11
12
PROCEDIMIENTO tribonacci(n)
VARIABLES:
    a, b, c, siguiente (enteros)
INICIO
    a=0, b=1, c=1
    // Imprimir los primeros términos según n
    PARA i DESDE 4 HASTA n HACER
        siguiente = a + b + c
        ESCRIBIR siguiente
        a = b, b = c, c = siguiente
    FIN PARA
FIN PROCEDIMIENTO

Ejercicio 3.37 - Fracciones Egipcias ⭐⭐☆☆☆¶

Descripción¶

Escribir una función que descomponga una fracción propia a/b en una suma de fracciones unitarias distintas (fracciones con numerador 1).

Ayuda (pseudocódigo)

1
2
3
4
5
6
7
8
9
10
PROCEDIMIENTO fracciones_egipcias(num, den)
INICIO
    MIENTRAS num != 0 HACER
        d = TECHO(den / num)
        ESCRIBIR "1/", d
        num = num * d - den
        den = den * d
        // Simplificar fracción num/den
    FIN MIENTRAS
    FIN PROCEDIMIENTO

Ejercicio 3.38 - Ternas Pitagóricas ⭐⭐☆☆☆¶

Descripción¶

Implementar un programa que genere todas las ternas pitagóricas primitivas (`a^2

b^2 = c^2, con mcd(a,b,c)=1) hasta un cierto límite para c`, utilizando la fórmula de Euclides.

Ayuda (pseudocódigo)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
PROCEDIMIENTO ternas_pitagoricas(limite_c)
INICIO
    PARA m DESDE 2 HASTA RAIZ_CUADRADA(limite_c) HACER
        PARA n DESDE 1 HASTA m-1 HACER
            SI (m - n) MOD 2 == 1 Y mcd(m, n) == 1 ENTONCES
                a = m*m - n*n
                b = 2*m*n
                c = m*m + n*n
                SI c <= limite_c ENTONCES
                    ESCRIBIR "(", a, ", ", b, ", ", c, ")"
                FIN SI
            FIN SI
        FIN PARA
    FIN PARA
FIN PROCEDIMIENTO

Ejercicio 3.39 - Números de Carmichael ⭐⭐☆☆☆¶

Descripción¶

Un número de Carmichael es un número que satisface la congruencia $b^{n-1} \equiv 1 \pmod{n}$ para todos los enteros b coprimos con n. Escribir una función que verifique si un número es un número de Carmichael.

Ayuda (pseudocódigo)

1
2
3
4
5
6
7
8
9
10
11
12
13
FUNCION es_carmichael(n)
INICIO
    SI es_primo(n) O n MOD 2 == 0 RETORNAR FALSO

    PARA b DESDE 2 HASTA n-1 HACER
        SI mcd(b, n) == 1 ENTONCES
            SI potencia_modular(b, n-1, n) != 1 ENTONCES
                RETORNAR FALSO
            FIN SI
        FIN SI
    FIN PARA
    RETORNAR VERDADERO
FIN FUNCION

Ejercicio 3.40 - Logaritmo Entero ⭐⭐☆☆☆¶

Descripción¶

Calcular el logaritmo entero en base b de un número n. Es el mayor entero k tal que $b^k \le n$ . La implementación no debe usar funciones de math.h.

Ayuda (pseudocódigo)

1
2
3
4
5
6
7
8
9
10
11
FUNCION logaritmo_entero(n, b)
VARIABLES:
    k (entero)
INICIO
    k = 0
    MIENTRAS n >= b HACER
        n = n / b
        k = k + 1
    FIN MIENTRAS
    RETORNAR k
FIN FUNCION

Ejercicio 3.41 - Conversión de Base Numérica ⭐⭐☆☆☆¶

Descripción¶

Escribir una función que convierta un número n de una base b1 a una base b2.

Ayuda (pseudocódigo)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
FUNCION convertir_base(numero_original, b1, b2)
INICIO
    // Paso 1: Convertir de b1 a base 10
    valor_base10 = 0
    // ... lazo para calcular el valor en base 10 ...

    // Paso 2: Convertir de base 10 a b2
    resultado_final = ""
    MIENTRAS valor_base10 > 0 HACER
        resto = valor_base10 MOD b2
        resultado_final = caracter(resto) + resultado_final
        valor_base10 = valor_base10 / b2
    FIN MIENTRAS

    RETORNAR resultado_final
FIN FUNCION