Ejercicios de Arreglos (Estáticos) - Programación 1

Prerrequisitos y Entorno de Ejecución Requerido¶

Para compilar y verificar las soluciones de este módulo bajo el estándar C11 estricto de cátedra, se requiere:

Compilador C11: GCC 9+ o Clang 11+ configurado con flags -Wall -Wextra -Werror -pedantic -std=c11.
Entorno POSIX: Linux o WSL con utilidades estándar y verificación de límites de memoria.
Herramientas de Verificación: Valgrind (memcheck) y AddressSanitizer (-fsanitize=address,undefined) para garantizar la ausencia de lecturas o escrituras fuera de los límites del arreglo.
Conocimientos Previos: Declaración e inicialización estática (int arr[N]), indexación base-cero, paso de arreglos por referencia y calificador const int *arr.

Objetivos Pedagógicos y Competencias (Taxonomía de Bloom)¶

Nivel 2 (Comprensión): Analizar el decaimiento de arreglos a punteros (array decay) y el cálculo de direcciones contiguas.
Nivel 3 (Aplicación): Implementar algoritmos de recorrido, búsqueda, inversión in-situ, rotación y filtrado en C11.
Nivel 4 (Análisis): Evaluar cotas de memoria (0 <= i < n), invariantes de partición y complejidad temporal $O(n)$ en operaciones secuenciales.
Andamiaje Progresivo: Ejercicios andamiados con contratos formales (precondiciones/postcondiciones), tablas de vectores de prueba y suites ejecutables con assert().

Capítulos de Apunte Correspondientes¶

capitulo-arreglos
Secuencias: Arreglos y Cadenas

Operaciones Básicas¶

Ejercicio 2.03.01 - Formateo de Arreglos ⭐⭐☆☆☆¶

Exercise 1

Implementá una función pura que formatee los elementos de un arreglo entero en un búfer de caracteres con el formato "[10, 20, 30]". Debe retornar true si el búfer tuvo capacidad suficiente, o false ante desbordamientos.

bool formatear_arreglo(const int *arr, size_t n, char *buffer, size_t capacidad);

Tabla de Vectores de Prueba:

Arreglo	`n`	Capacidad Búfer	Retorno Esperado	Salida Formateada
`[10, 20, 30]`	`3`	`64`	`true`	`"[10, 20, 30]"`
`[42]`	`1`	`32`	`true`	`"[42]"`
`[]`	`0`	`16`	`true`	`"[]"`
`[1, 2, 3]`	`3`	`4`	`false`	Búfer protegido contra overflow

```c #include <stdio.h> #include <stdbool.h> #include <string.h> #include <assert.h> bool formatear_arreglo(const int *arr, size_t n, char *buffer, size_t capacidad) { if (buffer == NULL || capacidad < 3) { return false; } if (arr == NULL || n == 0) { snprintf(buffer, capacidad, "[]"); return true; } size_t offset = 0; int esc = snprintf(buffer + offset, capacidad - offset, "["); if (esc < 0 || (size_t)esc >= capacidad - offset) return false; offset += (size_t)esc; for (size_t i = 0; i < n; ++i) { if (i > 0) { esc = snprintf(buffer + offset, capacidad - offset, ", "); if (esc < 0 || (size_t)esc >= capacidad - offset) return false; offset += (size_t)esc; } esc = snprintf(buffer + offset, capacidad - offset, "%d", arr[i]); if (esc < 0 || (size_t)esc >= capacidad - offset) return false; offset += (size_t)esc; } esc = snprintf(buffer + offset, capacidad - offset, "]"); if (esc < 0 || (size_t)esc >= capacidad - offset) return false; return true; } int main(void) { char buf[64] = {0}; int datos[] = {10, 20, 30}; assert(formatear_arreglo(datos, 3, buf, sizeof(buf))); assert(strcmp(buf, "[10, 20, 30]") == 0); int uno[] = {42}; assert(formatear_arreglo(uno, 1, buf, sizeof(buf))); assert(strcmp(buf, "[42]") == 0); assert(formatear_arreglo(NULL, 0, buf, sizeof(buf))); assert(strcmp(buf, "[]") == 0); /* Capacidad insuficiente */ char corto[4] = {0}; assert(!formatear_arreglo(datos, 3, corto, sizeof(corto))); return 0; } ```


(ej_b2_c03_02)=
### Ejercicio 2.03.02 - Suma de Elementos de un Arreglo ⭐⭐☆☆☆

:::{exercise}
:label: ej_b2_c03_02_suma

Calculá la suma de todos los enteros de un arreglo contiguo en tiempo $O(n)$
utilizando acumuladores con rango extendido de 64 bits para prevenir overflow.

```c
long long sumar_elementos(const int *arr, size_t n);
```

**Tabla de Vectores de Prueba:**

| Arreglo | `n` | Suma Esperada |
| :--- | :--- | :--- |
| `[1, 2, 3, 4, 5]` | `5` | `15LL` |
| `[-10, 20, -5]` | `3` | `5LL` |
| `[]` | `0` | `0LL` |

::::{solution}
```c
#include <stdio.h>
#include <stddef.h>
#include <assert.h>

long long sumar_elementos(const int *arr, size_t n) {
    if (arr == NULL || n == 0) {
        return 0LL;
    }
    long long suma = 0LL;
    for (size_t i = 0; i < n; ++i) {
        suma += (long long)arr[i];
    }
    return suma;
}

int main(void) {
    int a1[] = {1, 2, 3, 4, 5};
    assert(sumar_elementos(a1, 5) == 15LL);

    int a2[] = {-10, 20, -5};
    assert(sumar_elementos(a2, 3) == 5LL);

    assert(sumar_elementos(NULL, 0) == 0LL);
    return 0;
}
```


(ej_b2_c03_03)=
### Ejercicio 2.03.03 - Promedio Aritmético de Arreglo ⭐⭐☆☆☆

:::{exercise}
:label: ej_b2_c03_03_promedio

Implementá una función pura que calcule el promedio (media aritmética) de los elementos de un arreglo de enteros, retornando un `double`:
- Si el arreglo es nulo o $n = 0$, retorna `0.0`.

```c
double calcular_promedio(const int *arr, size_t n);
```

**Tabla de Vectores de Prueba:**

| Arreglo | `n` | Promedio Esperado |
| :--- | :--- | :--- |
| `[10, 20, 30]` | `3` | `20.0` |
| `[1, 2]` | `2` | `1.5` |
| `[-5, 5]` | `2` | `0.0` |
| `[]` | `0` | `0.0` |

::::{solution}
```c
#include <stdio.h>
#include <stddef.h>
#include <math.h>
#include <assert.h>

#define EPSILON 1e-6

static int casi_igual(double a, double b) {
    return fabs(a - b) < EPSILON;
}

double calcular_promedio(const int *arr, size_t n) {
    if (arr == NULL || n == 0) {
        return 0.0;
    }
    long long suma = 0;
    for (size_t i = 0; i < n; ++i) {
        suma += arr[i];
    }
    return (double)suma / (double)n;
}

int main(void) {
    int a1[] = {10, 20, 30};
    assert(casi_igual(calcular_promedio(a1, 3), 20.0));

    int a2[] = {1, 2};
    assert(casi_igual(calcular_promedio(a2, 2), 1.5));

    int a3[] = {-5, 5};
    assert(casi_igual(calcular_promedio(a3, 2), 0.0));

    assert(casi_igual(calcular_promedio(NULL, 0), 0.0));
    return 0;
}
```


(ej_b2_c03_04)=
### Ejercicio 2.03.04 - Productoria ⭐⭐☆☆☆

Calcular el producto de todos los elementos de un arreglo.

:::{hint} Lógica y Consideraciones
-   **Entrada:** Un arreglo y su tamaño.
-   **Variables:** Se necesita un `acumulador` inicializado en 1 (no en 0, ya
    que cualquier cosa multiplicada por 0 es 0).
-   **Proceso:** Recorrer el arreglo con un lazo `for`. En cada iteración,
    multiplicar el `acumulador` por el elemento actual.
-   **Caso Especial:** Si el arreglo contiene un 0, el producto final será 0.

Ayuda (pseudocódigo)

1
2
3
4
5
6
7
8
9
10
FUNCION productoria_arreglo(arreglo, tamano)
VARIABLES:
    producto (tipo de dato del arreglo)
INICIO
    producto = 1
    PARA i DESDE 0 HASTA tamano-1 HACER
        producto = producto * arreglo[i]
    FIN PARA
    RETORNAR producto
FIN FUNCION

Búsqueda y Estadísticas¶

Ejercicio 2.03.05 - Máximo y mínimo ⭐⭐☆☆☆¶

Encontrar los valores más grande (máximo) y más pequeño (mínimo) dentro de un arreglo de números.

Ayuda (pseudocódigo)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
PROCEDIMIENTO encontrar_max_min(arreglo, tamano, REF maximo, REF minimo)
INICIO
    SI tamano == 0 ENTONCES TERMINAR // Arreglo vacío

    maximo = arreglo[0]
    minimo = arreglo[0]

    PARA i DESDE 1 HASTA tamano-1 HACER
        SI arreglo[i] > maximo ENTONCES
            maximo = arreglo[i]
        FIN SI
        SI arreglo[i] < minimo ENTONCES
            minimo = arreglo[i]
        FIN SI
    FIN PARA
FIN PROCEDIMIENTO

Ejercicio 2.03.06 - Casi máximo ⭐⭐☆☆☆¶

Encontrar el segundo elemento más grande en un arreglo. Este ejercicio requiere un seguimiento más cuidadoso que simplemente encontrar el máximo.

Ayuda (pseudocódigo)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
FUNCION encontrar_segundo_maximo(arreglo, tamano)
VARIABLES:
    maximo, segundo_maximo
INICIO
    // Inicializar con los dos primeros elementos o valores muy bajos
    maximo = MINIMO_VALOR_POSIBLE
    segundo_maximo = MINIMO_VALOR_POSIBLE

    PARA cada elemento x EN arreglo HACER
        SI x > maximo ENTONCES
            segundo_maximo = maximo
            maximo = x
        SINO SI x > segundo_maximo Y x < maximo ENTONCES
            segundo_maximo = x
        FIN SI
    FIN PARA
    RETORNAR segundo_maximo
FIN FUNCION

Ejercicio 2.03.07 - Búsqueda de elemento ⭐⭐☆☆☆¶

Implementar una búsqueda lineal para encontrar la primera ocurrencia de un elemento específico dentro de un arreglo. Si se encuentra, se debe devolver su índice.

Ayuda (pseudocódigo)

1
2
3
4
5
6
7
8
9
FUNCION busqueda_lineal(arreglo, tamano, buscado)
INICIO
    PARA i DESDE 0 HASTA tamano-1 HACER
        SI arreglo[i] == buscado ENTONCES
            RETORNAR i // Elemento encontrado
        FIN SI
    FIN PARA
    RETORNAR -1 // Elemento no encontrado
FIN FUNCION

Ejercicio 2.03.08 - Contar repeticiones ⭐⭐☆☆☆¶

Contar cuántas veces aparece un número específico en un arreglo.

Ayuda (pseudocódigo)

1
2
3
4
5
6
7
8
9
10
11
12
FUNCION contar_repeticiones(arreglo, tamano, buscado)
VARIABLES:
    contador (entero)
INICIO
    contador = 0
    PARA i DESDE 0 HASTA tamano-1 HACER
        SI arreglo[i] == buscado ENTONCES
            contador = contador + 1
        FIN SI
    FIN PARA
    RETORNAR contador
FIN FUNCION

Ejercicio 2.03.09 - Elemento más cercano ⭐⭐☆☆☆¶

Dado un arreglo y un valor de referencia, encontrar el elemento en el arreglo que tiene la menor diferencia absoluta con dicho valor.

Ayuda (pseudocódigo)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
FUNCION encontrar_mas_cercano(arreglo, tamano, referencia)
VARIABLES:
    menor_diferencia, diferencia_actual (reales)
    elemento_cercano (tipo del arreglo)
INICIO
    menor_diferencia = VALOR_INFINITO
    PARA cada elemento x EN arreglo HACER
        diferencia_actual = VALOR_ABSOLUTO(x - referencia)
        SI diferencia_actual < menor_diferencia ENTONCES
            menor_diferencia = diferencia_actual
            elemento_cercano = x
        FIN SI
    FIN PARA
    RETORNAR elemento_cercano
FIN FUNCION

Manipulación de Arreglos¶

Ejercicio 2.03.10 - Inversión ⭐⭐☆☆☆¶

Invertir el orden de los elementos de un arreglo in-place, es decir, sin usar un segundo arreglo para almacenar el resultado temporalmente.

Ayuda (pseudocódigo)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
PROCEDIMIENTO invertir_arreglo(REF arreglo, tamano)
VARIABLES:
    inicio, fin, temporal (enteros)
INICIO
    inicio = 0
    fin = tamano - 1
    MIENTRAS inicio < fin HACER
        // Intercambiar elementos
        temporal = arreglo[inicio]
        arreglo[inicio] = arreglo[fin]
        arreglo[fin] = temporal

        inicio = inicio + 1
        fin = fin - 1
    FIN MIENTRAS
FIN PROCEDIMIENTO

Ejercicio 2.03.11 - Copia ⭐⭐☆☆☆¶

Copiar todos los elementos de un arreglo de origen a un arreglo de destino.

Ayuda (pseudocódigo)

1
2
3
4
5
6
PROCEDIMIENTO copiar_arreglo(origen, REF destino, tamano)
INICIO
    PARA i DESDE 0 HASTA tamano-1 HACER
        destino[i] = origen[i]
    FIN PARA
FIN PROCEDIMIENTO

Ejercicio 2.03.12 - Deduplicación ⭐⭐☆☆☆¶

Eliminar los elementos duplicados de un arreglo, conservando solo la primera aparición de cada elemento. La función debe modificar el arreglo in-place y devolver el nuevo tamaño lógico.

Ayuda (pseudocódigo)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
FUNCION deduplicar_arreglo(REF arreglo, tamano)
INICIO
    SI tamano == 0 RETORNAR 0

    ORDENAR(arreglo, tamano)

    indice_escritura = 1
    PARA i DESDE 1 HASTA tamano-1 HACER
        SI arreglo[i] != arreglo[i-1] ENTONCES
            arreglo[indice_escritura] = arreglo[i]
            indice_escritura = indice_escritura + 1
        FIN SI
    FIN PARA
    RETORNAR indice_escritura
FIN FUNCION

Verificación¶

Ejercicio 2.03.13 - ¿Está ordenado? ⭐⭐☆☆☆¶

Verificar si un arreglo está ordenado de forma ascendente.

Ayuda (pseudocódigo)

1
2
3
4
5
6
7
8
9
FUNCION esta_ordenado(arreglo, tamano)
INICIO
    PARA i DESDE 0 HASTA tamano-2 HACER
        SI arreglo[i] > arreglo[i+1] ENTONCES
            RETORNAR FALSO
        FIN SI
    FIN PARA
    RETORNAR VERDADERO
FIN FUNCION

Ejercicio 2.03.14 - Solo positivos ⭐⭐☆☆☆¶

Verificar si todos los elementos de un arreglo son números positivos (mayores que cero).

Ayuda (pseudocódigo)

1
2
3
4
5
6
7
8
9
FUNCION son_todos_positivos(arreglo, tamano)
INICIO
    PARA cada elemento x EN arreglo HACER
        SI x <= 0 ENTONCES
            RETORNAR FALSO
        FIN SI
    FIN PARA
    RETORNAR VERDADERO
FIN FUNCION

Operaciones Avanzadas con Arreglos¶

Ejercicio 2.03.15 - Rotación de arreglo ⭐⭐⭐☆☆¶

Implementar una función que rote los elementos de un arreglo k posiciones hacia la derecha. Esto significa que los últimos k elementos se moverán al principio del arreglo, y el resto de los elementos se desplazarán hacia la derecha.

Ayuda (pseudocódigo)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
PROCEDIMIENTO rotar_derecha(REF arreglo, n, k)
VARIABLES:
    temporal (arreglo de tamaño n)
INICIO
    k = k MOD n // Manejar rotaciones mayores que n

    PARA i DESDE 0 HASTA n-1 HACER
        nueva_pos = (i + k) MOD n
        temporal[nueva_pos] = arreglo[i]
    FIN PARA

    // Copiar de vuelta al arreglo original
    PARA i DESDE 0 HASTA n-1 HACER
        arreglo[i] = temporal[i]
    FIN PARA
FIN PROCEDIMIENTO

Ejercicio 2.03.16 - Fusión de arreglos ⭐⭐⭐☆☆¶

Escribir una función que fusione dos arreglos en un tercer arreglo que contenga todos los elementos de los dos primeros. Si los arreglos originales están ordenados, el resultado también debería estarlo (ver Merge Sort).

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
29
FUNCION fusionar_ordenado(a1, n1, a2, n2)
VARIABLES:
    resultado (arreglo de tamaño n1+n2)
    i, j, k (enteros)
INICIO
    i=0, j=0, k=0
    MIENTRAS i < n1 Y j < n2 HACER
        SI a1[i] <= a2[j] ENTONCES
            resultado[k] = a1[i]
            i = i + 1
        SINO
            resultado[k] = a2[j]
            j = j + 1
        FIN SI
        k = k + 1
    FIN MIENTRAS

    // Copiar elementos restantes
    MIENTRAS i < n1 HACER
        resultado[k] = a1[i]
        i = i + 1, k = k + 1
    FIN MIENTRAS
    MIENTRAS j < n2 HACER
        resultado[k] = a2[j]
        j = j + 1, k = k + 1
    FIN MIENTRAS

    RETORNAR resultado
FIN FUNCION

Ejercicio 2.03.17 - Intersección de arreglos ⭐⭐⭐☆☆¶

Crear una función que reciba dos arreglos y devuelva un nuevo arreglo con los elementos que son comunes a ambos. Cada elemento debe aparecer solo una vez en el resultado.

Ayuda (pseudocódigo)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
FUNCION interseccion(a1, n1, a2, n2)
VARIABLES:
    resultado (arreglo)
    i, j (enteros)
INICIO
    i=0, j=0
    MIENTRAS i < n1 Y j < n2 HACER
        SI a1[i] < a2[j] ENTONCES
            i = i + 1
        SINO SI a2[j] < a1[i] ENTONCES
            j = j + 1
        SINO // Son iguales
            AÑADIR a1[i] a resultado (si no está ya)
            i = i + 1, j = j + 1
        FIN SI
    FIN MIENTRAS
    RETORNAR resultado
FIN FUNCION

Ejercicio 2.03.18 - Unión de arreglos ⭐⭐⭐☆☆¶

Crear una función que reciba dos arreglos y devuelva un nuevo arreglo con todos los elementos de ambos, sin duplicados.

Ayuda (pseudocódigo)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
FUNCION union_arreglos(a1, n1, a2, n2)
VARIABLES:
    resultado (arreglo)
    // Usar una tabla hash o similar para eficiencia
    elementos_vistos (conjunto)
INICIO
    PARA cada elemento x en a1 HACER
        AÑADIR x a resultado
        AÑADIR x a elementos_vistos
    FIN PARA
    PARA cada elemento y en a2 HACER
        SI y NO ESTÁ EN elementos_vistos ENTONCES
            AÑADIR y a resultado
            AÑADIR y a elementos_vistos
        FIN SI
    FIN PARA
    RETORNAR resultado
FIN FUNCION

Ejercicio 2.03.19 - Separar pares e impares ⭐⭐☆☆☆¶

Reorganizar un arreglo in-place de tal manera que todos los números pares queden al principio y todos los impares al final. El orden relativo entre los números pares o entre los impares no necesita conservarse.

Ayuda (pseudocódigo)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
PROCEDIMIENTO separar_pares_impares(REF arreglo, tamano)
VARIABLES:
    izquierda, derecha (enteros)
INICIO
    izquierda = 0, derecha = tamano - 1
    MIENTRAS izquierda < derecha HACER
        MIENTRAS arreglo[izquierda] MOD 2 == 0 Y izquierda < derecha HACER
            izquierda = izquierda + 1
        FIN MIENTRAS
        MIENTRAS arreglo[derecha] MOD 2 != 0 Y izquierda < derecha HACER
            derecha = derecha - 1
        FIN MIENTRAS

        SI izquierda < derecha ENTONCES
            INTERCAMBIAR(arreglo[izquierda], arreglo[derecha])
            izquierda = izquierda + 1
            derecha = derecha - 1
        FIN SI
    FIN MIENTRAS
FIN PROCEDIMIENTO

Ejercicio 2.03.20 - Algoritmo de Kadane (Suma Máxima de Subarreglo Contiguo) ⭐⭐⭐☆☆¶

Exercise 2

Implementá el Algoritmo de Kadane en tiempo lineal $\mathcal{O}(n)$ y espacio $\mathcal{O}(1)$ para hallar la suma máxima de un subarreglo contiguo no vacío:

long long max_suma_subarreglo_kadane(const int *arr, size_t n, bool *valido);

Reglas de cálculo:

Dominio con negativos: Si todos los elementos del arreglo son negativos, la suma máxima corresponde al elemento individual menos negativo (por ejemplo, para {-5, -2, -8}, la respuesta es -2).
Manejo defensivo: Si arr == NULL o n == 0, la función retorna 0LL y asigna false al puntero valido (si no es NULL). Ante éxito, asigna true a *valido.

Tabla de Vectores de Prueba Obligatorios¶

Caso de Prueba	Entrada `arr` ( $n$ )	Retorno Esperado	`*valido`	Subarreglo Óptimo
Normal Mixto	`{-2, 1, -3, 4, -1, 2, 1, -5, 4}`, $n=9$	`6LL`	`true`	`{4, -1, 2, 1}`
Todos Negativos	`{-5, -2, -8, -1}`, $n=4$	`-1LL`	`true`	`{-1}`
Todos Positivos	`{1, 2, 3, 4}`, $n=4$	`10LL`	`true`	Todo el arreglo
Elemento Único	`{-7}`, $n=1$	`-7LL`	`true`	`{-7}`
Vector Vacío	`NULL`, $n=0$	`0LL`	`false`	Inexistente

Solution to Exercise 2

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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include <stddef.h>
#include <stdbool.h>
#include <assert.h>

long long max_suma_subarreglo_kadane(const int *arr, size_t n, bool *valido)
{
    if (arr == NULL || n == 0)
    {
        if (valido != NULL)
        {
            *valido = false;
        }
        return 0LL;
    }

    if (valido != NULL)
    {
        *valido = true;
    }

    long long max_global = arr[0];
    long long max_actual = arr[0];

    for (size_t i = 1; i < n; i++)
    {
        long long valor = arr[i];
        if (max_actual + valor > valor)
        {
            max_actual += valor;
        }
        else
        {
            max_actual = valor;
        }

        if (max_actual > max_global)
        {
            max_global = max_actual;
        }
    }

    return max_global;
}

int main(void)
{
    bool ok = false;

    int arr1[] = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
    assert(max_suma_subarreglo_kadane(arr1, 9, &ok) == 6LL && ok == true);

    int arr_neg[] = {-5, -2, -8, -1};
    assert(max_suma_subarreglo_kadane(arr_neg, 4, &ok) == -1LL && ok == true);

    int arr_pos[] = {1, 2, 3, 4};
    assert(max_suma_subarreglo_kadane(arr_pos, 4, &ok) == 10LL && ok == true);

    int arr_uno[] = {-7};
    assert(max_suma_subarreglo_kadane(arr_uno, 1, &ok) == -7LL && ok == true);

    assert(max_suma_subarreglo_kadane(NULL, 0, &ok) == 0LL && ok == false);

    return 0;
}

-   `max_actual`: La suma máxima del subarreglo que termina en la posición
    actual.
-   `max_global`: La suma máxima encontrada en todo el arreglo hasta el
    momento.

En cada paso i:
1. max_actual = MAXIMO(arreglo[i], max_actual + arreglo[i])
2. max_global = MAXIMO(max_global, max_actual)

<!-- {hint} Lógica y Consideraciones -->

:::{tip} Ayuda (pseudocódigo)
:class: dropdown
```{code-block} pseudocode
:linenos:
FUNCION kadane(arreglo, tamano)
VARIABLES:
    max_actual, max_global
INICIO
    max_actual = arreglo[0]
    max_global = arreglo[0]

    PARA i DESDE 1 HASTA tamano-1 HACER
        max_actual = MAXIMO(arreglo[i], max_actual + arreglo[i])
        SI max_actual > max_global ENTONCES
            max_global = max_actual
        FIN SI
    FIN PARA
    RETORNAR max_global
FIN FUNCION

```
<!-- {code-block} pseudocode -->

Ejercicio 2.03.21 - Histograma ⭐⭐☆☆☆¶

Dado un arreglo de enteros no negativos, el programa debe imprimir un histograma simple usando asteriscos, donde cada número n se representa con una línea de n asteriscos.

Ayuda (pseudocódigo)

1
2
3
4
5
6
7
8
9
10
PROCEDIMIENTO imprimir_histograma(arreglo, tamano)
INICIO
    PARA i DESDE 0 HASTA tamano-1 HACER
        ESCRIBIR i, ": " SIN SALTO DE LÍNEA
        PARA j DESDE 1 HASTA arreglo[i] HACER
            ESCRIBIR "*" SIN SALTO DE LÍNEA
        FIN PARA
        ESCRIBIR SALTO DE LÍNEA
    FIN PARA
FIN PROCEDIMIENTO

Ejercicio 2.03.22 - Barajar arreglo (Fisher-Yates) ⭐⭐⭐☆☆¶

Implementar el algoritmo de Fisher-Yates para barajar (desordenar aleatoriamente) los elementos de un arreglo in-place.

Ayuda (pseudocódigo)

1
2
3
4
5
6
7
8
9
PROCEDIMIENTO barajar_fisher_yates(REF arreglo, tamano)
VARIABLES:
    j, temporal (enteros)
INICIO
    PARA i DESDE tamano-1 HASTA 1 CON PASO -1 HACER
        j = generar_aleatorio(0, i)
        INTERCAMBIAR(arreglo[i], arreglo[j])
    FIN PARA
FIN PROCEDIMIENTO

Ejercicio 2.03.23 - Encontrar elemento faltante ⭐⭐☆☆☆¶

Dado un arreglo que contiene n-1 números distintos en el rango de 1 a n, encontrar el único número que falta.

Ayuda (pseudocódigo)

1
2
3
4
5
6
7
8
9
FUNCION encontrar_faltante(arreglo, tamano_actual)
VARIABLES:
    n, suma_esperada, suma_real (enteros)
INICIO
    n = tamano_actual + 1
    suma_esperada = n * (n + 1) / 2
    suma_real = sumar_arreglo(arreglo, tamano_actual)
    RETORNAR suma_esperada - suma_real
FIN FUNCION

Ejercicio 2.03.24 - Encontrar par con suma X ⭐⭐☆☆☆¶

Dado un arreglo de números y un valor X, determinar si existe un par de elementos en el arreglo cuya suma sea exactamente X.

Ayuda (pseudocódigo)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
FUNCION existe_par_con_suma(arreglo, tamano, X)
VARIABLES:
    izquierda, derecha, suma (enteros)
INICIO
    ORDENAR(arreglo, tamano)
    izquierda = 0, derecha = tamano - 1

    MIENTRAS izquierda < derecha HACER
        suma = arreglo[izquierda] + arreglo[derecha]
        SI suma == X ENTONCES
            RETORNAR VERDADERO
        SINO SI suma < X ENTONCES
            izquierda = izquierda + 1
        SINO
            derecha = derecha - 1
        FIN SI
    FIN MIENTRAS
    RETORNAR FALSO
FIN FUNCION

Ejercicio 2.03.25 - Mediana de un arreglo ⭐⭐⭐☆☆¶

Calcular la mediana de un arreglo. La mediana es el valor que se encuentra en la posición central de un arreglo ordenado. Si el arreglo tiene un número par de elementos, la mediana es el promedio de los dos elementos centrales.

Ayuda (pseudocódigo)

1
2
3
4
5
6
7
8
9
FUNCION calcular_mediana(arreglo, tamano)
INICIO
    ORDENAR(arreglo, tamano)
    SI tamano MOD 2 != 0 ENTONCES
        RETORNAR arreglo[tamano / 2]
    SINO
        RETORNAR (arreglo[tamano/2 - 1] + arreglo[tamano/2]) / 2.0
    FIN SI
    FIN FUNCION

Ejercicio 2.03.26 - Moda de un arreglo ⭐⭐⭐☆☆¶

Encontrar la moda de un arreglo, que es el elemento que aparece con mayor frecuencia.

Ayuda (pseudocódigo)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
FUNCION encontrar_moda(arreglo, tamano)
VARIABLES:
    moda, max_frecuencia, frec_actual, elemento_actual
INICIO
    ORDENAR(arreglo, tamano)
    moda = arreglo[0], max_frecuencia = 1, frec_actual = 1

    PARA i DESDE 1 HASTA tamano-1 HACER
        SI arreglo[i] == arreglo[i-1] ENTONCES
            frec_actual = frec_actual + 1
        SINO
            frec_actual = 1
        FIN SI
        SI frec_actual > max_frecuencia ENTONCES
            max_frecuencia = frec_actual
            moda = arreglo[i]
        FIN SI
    FIN PARA
    RETORNAR moda
FIN FUNCION

Ejercicio 2.03.27 - Rellenar con secuencia aritmética ⭐⭐☆☆☆¶

Escribir una función que llene un arreglo con los términos de una secuencia aritmética, dados un valor de inicio, un tamaño y un paso (la diferencia constante entre términos).

Ayuda (pseudocódigo)

1
2
3
4
5
6
PROCEDIMIENTO rellenar_secuencia(REF arreglo, tamano, inicio, paso)
INICIO
    PARA i DESDE 0 HASTA tamano-1 HACER
        arreglo[i] = inicio + (i * paso)
    FIN PARA
FIN PROCEDIMIENTO

Ejercicio 2.03.28 - Diferencia simétrica ⭐⭐☆☆☆¶

Calcular la diferencia simétrica entre dos arreglos. El resultado debe ser un nuevo arreglo que contenga los elementos que están en uno de los arreglos, pero no en ambos.

Ayuda (pseudocódigo)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
FUNCION diferencia_simetrica(a1, n1, a2, n2)
VARIABLES:
    resultado (arreglo)
INICIO
    PARA cada elemento x en a1 HACER
        SI x NO ESTÁ EN a2 ENTONCES
            AÑADIR x a resultado
        FIN SI
    FIN PARA
    PARA cada elemento y en a2 HACER
        SI y NO ESTÁ EN a1 ENTONCES
            AÑADIR y a resultado
        FIN SI
    FIN PARA
    RETORNAR resultado
FIN FUNCION

Ejercicio 2.03.29 - Conteo de inversiones ⭐⭐☆☆☆¶

Contar el número de “inversiones” en un arreglo. Una inversión es un par de índices (i, j) tales que i < j y arr[i] > arr[j]. Un arreglo perfectamente ordenado tiene 0 inversiones.

Ayuda (pseudocódigo)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
FUNCION contar_inversiones(arreglo, tamano)
VARIABLES:
    contador (entero)
INICIO
    contador = 0
    PARA i DESDE 0 HASTA tamano-2 HACER
        PARA j DESDE i+1 HASTA tamano-1 HACER
            SI arreglo[i] > arreglo[j] ENTONCES
                contador = contador + 1
            FIN SI
        FIN PARA
    FIN PARA
    RETORNAR contador
FIN FUNCION

Más Manipulación de Arreglos¶

Ejercicio 2.03.30 - Picos y valles ⭐⭐☆☆☆¶

Escribir una función que encuentre todos los “picos” en un arreglo. Un pico es un elemento que es estrictamente mayor que sus dos vecinos (el anterior y el siguiente). Los elementos en los extremos no pueden ser picos.

Ayuda (pseudocódigo)

1
2
3
4
5
6
7
8
PROCEDIMIENTO encontrar_picos(arreglo, tamano)
INICIO
    PARA i DESDE 1 HASTA tamano-2 HACER
        SI arreglo[i] > arreglo[i-1] Y arreglo[i] > arreglo[i+1] ENTONCES
            ESCRIBIR arreglo[i], " es un pico en el índice ", i
        FIN SI
    FIN PARA
FIN PROCEDIMIENTO

Ejercicio 2.03.31 - Subarreglo más largo con suma cero ⭐⭐⭐☆☆¶

Dado un arreglo de enteros (positivos y negativos), encontrar la longitud del subarreglo contiguo más largo cuya suma de elementos sea cero.

Ayuda (pseudocódigo)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
FUNCION subarreglo_suma_cero(arreglo, tamano)
VARIABLES:
    mapa_sumas (tabla hash)
    suma, max_longitud (enteros)
INICIO
    suma = 0, max_longitud = 0
    PARA i DESDE 0 HASTA tamano-1 HACER
        suma = suma + arreglo[i]
        SI suma == 0 ENTONCES
            max_longitud = i + 1
        SINO SI mapa_sumas CONTIENE suma ENTONCES
            max_longitud = MAXIMO(max_longitud, i - mapa_sumas[suma])
        SINO
            mapa_sumas[suma] = i
        FIN SI
    FIN PARA
    RETORNAR max_longitud
FIN FUNCION

Ejercicio 2.03.32 - Reorganizar positivos y negativos ⭐⭐☆☆☆¶

Reorganizar un arreglo in-place de tal manera que todos los números negativos aparezcan antes que todos los números positivos. El orden relativo entre los números del mismo signo no es importante.

Ayuda (pseudocódigo)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
PROCEDIMIENTO reorganizar_signos(REF arreglo, tamano)
VARIABLES:
    izquierda, derecha (enteros)
INICIO
    izquierda = 0, derecha = tamano - 1
    MIENTRAS izquierda <= derecha HACER
        SI arreglo[izquierda] < 0 Y arreglo[derecha] < 0 ENTONCES
            izquierda = izquierda + 1
        SINO SI arreglo[izquierda] > 0 Y arreglo[derecha] < 0 ENTONCES
            INTERCAMBIAR(arreglo[izquierda], arreglo[derecha])
            izquierda = izquierda + 1, derecha = derecha - 1
        SINO SI arreglo[izquierda] > 0 Y arreglo[derecha] > 0 ENTONCES
            derecha = derecha - 1
        SINO
            izquierda = izquierda + 1, derecha = derecha - 1
        FIN SI
    FIN MIENTRAS
FIN PROCEDIMIENTO

Ejercicio 2.03.33 - Producto de los demás elementos ⭐⭐☆☆☆¶

Dado un arreglo de números, crear un nuevo arreglo donde cada elemento en la posición i sea el producto de todos los demás números del arreglo original, pero sin usar el operador de división.

Ayuda (pseudocódigo)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
FUNCION producto_de_los_demas(arreglo, tamano)
VARIABLES:
    resultado (arreglo de tamaño n)
    izquierda_prod, derecha_prod
INICIO
    izquierda_prod = 1
    PARA i DESDE 0 HASTA tamano-1 HACER
        resultado[i] = izquierda_prod
        izquierda_prod = izquierda_prod * arreglo[i]
    FIN PARA

    derecha_prod = 1
    PARA i DESDE tamano-1 HASTA 0 CON PASO -1 HACER
        resultado[i] = resultado[i] * derecha_prod
        derecha_prod = derecha_prod * arreglo[i]
    FIN PARA

    RETORNAR resultado
FIN FUNCION

Ejercicio 2.03.34 - Arreglo de frecuencias ⭐⭐⭐☆☆¶

Dado un arreglo de enteros que contiene números en un rango conocido (por ejemplo, de 0 a 99), crear un “arreglo de frecuencias” que cuente cuántas veces aparece cada número.

Ayuda (pseudocódigo)

1
2
3
4
5
6
7
8
9
10
FUNCION calcular_frecuencias(arreglo, tamano, rango_max)
VARIABLES:
    frecuencias (arreglo de tamaño rango_max, inicializado en 0)
INICIO
    PARA i DESDE 0 HASTA tamano-1 HACER
        numero = arreglo[i]
        frecuencias[numero] = frecuencias[numero] + 1
    FIN PARA
    RETORNAR frecuencias
FIN FUNCION

Ejercicio 2.03.35 - ¿Es subconjunto? ⭐⭐☆☆☆¶

Implementar una función que determine si un arreglo A es un subconjunto de otro arreglo B. Esto significa que todos los elementos de A deben estar presentes en B.

Ayuda (pseudocódigo)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
FUNCION es_subconjunto(A, nA, B, nB)
VARIABLES:
    i, j (enteros)
INICIO
    ORDENAR(A, nA)
    ORDENAR(B, nB)
    i = 0, j = 0
    MIENTRAS i < nA Y j < nB HACER
        SI A[i] > B[j] ENTONCES
            j = j + 1
        SINO SI A[i] == B[j] ENTONCES
            i = i + 1, j = j + 1
        SINO // A[i] < B[j]
            RETORNAR FALSO
        FIN SI
    FIN MIENTRAS

    RETORNAR (i == nA)
FIN FUNCION

Ejercicio 2.03.36 - Mover ceros al final ⭐⭐☆☆☆¶

Escribir una función que mueva todos los ceros de un arreglo al final del mismo, manteniendo el orden relativo de los elementos no nulos.

Ayuda (pseudocódigo)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
PROCEDIMIENTO mover_ceros_final(REF arreglo, tamano)
VARIABLES:
    posicion_no_cero (entero)
INICIO
    posicion_no_cero = 0
    PARA i DESDE 0 HASTA tamano-1 HACER
        SI arreglo[i] != 0 ENTONCES
            arreglo[posicion_no_cero] = arreglo[i]
            posicion_no_cero = posicion_no_cero + 1
        FIN SI
    FIN PARA

    PARA i DESDE posicion_no_cero HASTA tamano-1 HACER
        arreglo[i] = 0
    FIN PARA
FIN PROCEDIMIENTO

Ejercicio 2.03.37 - Líderes en un arreglo ⭐⭐⭐☆☆¶

Encontrar todos los “líderes” en un arreglo. Un elemento es un líder si es mayor que todos los elementos que se encuentran a su derecha. El elemento más a la derecha siempre es un líder.

Ayuda (pseudocódigo)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
PROCEDIMIENTO encontrar_lideres(arreglo, tamano)
VARIABLES:
    maximo_derecha (entero)
INICIO
    maximo_derecha = arreglo[tamano-1]
    ESCRIBIR maximo_derecha

    PARA i DESDE tamano-2 HASTA 0 CON PASO -1 HACER
        SI arreglo[i] > maximo_derecha ENTONCES
            maximo_derecha = arreglo[i]
            ESCRIBIR maximo_derecha
        FIN SI
    FIN PARA
FIN PROCEDIMIENTO

Ejercicio 2.03.38 - Máxima diferencia ⭐⭐☆☆☆¶

Encontrar la máxima diferencia arr[j] - arr[i] en un arreglo, con la condición de que el índice j sea mayor que el índice i.

Ayuda (pseudocódigo)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
FUNCION max_diferencia(arreglo, tamano)
VARIABLES:
    max_diferencia, min_elemento
INICIO
    min_elemento = arreglo[0]
    max_diferencia = arreglo[1] - arreglo[0]

    PARA i DESDE 1 HASTA tamano-1 HACER
        SI (arreglo[i] - min_elemento) > max_diferencia ENTONCES
            max_diferencia = arreglo[i] - min_elemento
        FIN SI
        SI arreglo[i] < min_elemento ENTONCES
            min_elemento = arreglo[i]
        FIN SI
    FIN PARA
    RETORNAR max_diferencia
FIN FUNCION

Ejercicio 2.03.39 - Punto de equilibrio ⭐⭐☆☆☆¶

Encontrar un “punto de equilibrio” en un arreglo. Es un índice tal que la suma de los elementos a su izquierda es igual a la suma de los elementos a su derecha. Si no existe, devolver -1.

Ayuda (pseudocódigo)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
FUNCION encontrar_equilibrio(arreglo, tamano)
VARIABLES:
    suma_total, suma_izquierda
INICIO
    suma_total = sumar_arreglo(arreglo, tamano)
    suma_izquierda = 0

    PARA i DESDE 0 HASTA tamano-1 HACER
        suma_total = suma_total - arreglo[i]
        SI suma_izquierda == suma_total ENTONCES
            RETORNAR i
        FIN SI
        suma_izquierda = suma_izquierda + arreglo[i]
    FIN PARA

    RETORNAR -1
FIN FUNCION