22 Ejercicios corregidos Algoritmo divide y vencerás

Los siguientes ejercicios corregidos se refieren a la creación de algoritmos de acuerdo con la estructura del divide y vencerás (divide y vencerás). También se estudiarán algoritmos del tipo de dicotomía.

divide y vencerás

Ejercicio 1

Vamos a jugar al juego de “más pequeño, más grande”. El objetivo es adivinar un número entre 1 y n (entero). Consideramos que el algoritmo toma como entrada el valor de n y el número x a adivinar, y que devuelve el número de movimientos para encontrar este número.

a – Plantee el problema de manera más formal.

b – Escriba el algoritmo iterativo que resuelve este problema.

c – Escribir el algoritmo recursivo resolviendo este problema.

d – Comparar complejidades.

a – El problema se podría reescribir de la siguiente manera: Dada una matriz ordenada en orden ascendente de números enteros, ¿cómo determinar si un elemento pertenece a esta matriz o no? El principio es bien conocido: el elemento buscado se compara con el elemento mediano y, si es necesario, se repite la búsqueda en la parte izquierda o derecha de la tabla.

algoritmo de búsqueda binaria

b- El algoritmo iterativo es el siguiente:

algoritmo de búsqueda binaria

Dado que la matriz se corta en dos cada vez, revisaremos como máximo el elemento log n antes de encontrar el correcto o saber que no existe. los complejidad es por lo tanto O(log n)

contra - De forma predeterminada, la respuesta del algoritmo es falsa, a menos que se devuelva un verdadero que dará en el método principal:

algoritmo de búsqueda binaria

Dado que la operación es exactamente igual que el algoritmo iterativo, uno sospecha que la complejidad es la misma.

Ejercicio 2

Estamos buscando la suma de una matriz B de n elementos enteros.

1 – Escribe un algoritmo de divide y vencerás que resuelva este problema.

2 – Analice su complejidad y haga el árbol de llamadas para la matriz [3,4,2,3,4].

3 – Compáralo con un algoritmo iterativo que describirás

Definimos la función Sum(B,i,j) que es la suma de los elementos de B entre las posiciones i y j. Entonces el valor buscado es Sum(B,1,n). Calcularemos Sum(B,i,j) dividiendo la matriz B[i..j] en dos mitades; calcular sumas para cada mitad; y sumando estas dos sumas. Esto da el siguiente código:

algoritmo recursivo de matriz de suma

Para mayor complejidad, dado que aún no hemos visto el Teorema del maestro, usaremos el árbol de llamadas:

algoritmo recursivo de matriz de suma

Entendemos que cortamos la pintura en dos cada vez. El cálculo es simple, por lo que la complejidad solo depende de la profundidad del árbol p tal que 2^pag > n (tamaño de matriz), por lo tanto, p > log n y una complejidad de O (log n).

El algoritmo iterativo es el siguiente:

algoritmo recursivo de matriz de suma

Aquí la complejidad es O(n).

Ejercicio 3

Decimos que una matriz tiene un elemento mayoritario si un valor de la matriz está presente al menos n/2 veces de n elementos.

1 – Proponer un algoritmo iterativo para resolver este problema.

2 – Proponer un método para resolver este problema de divide y vencerás.

3- Escribir el método descrito por un algoritmo.

Modifica tu algoritmo teniendo en cuenta las siguientes propiedades:

  • si solo una de las mitades proporciona una mayoría, solo ese elemento puede ser una mayoría en la matriz completa.
  • si las dos llamadas recursivas dan mayorías, son diferentes, con diferente número de ocurrencias: la única que puede ser mayoritaria es la que tiene mayor número de ocurrencias.
  • en el caso de que n sea una potencia de 2, y por tanto las mitades siempre del mismo tamaño, si hay dos mayorías diferentes con el mismo número de ocurrencias, entonces no puede haber mayorías en la tabla completa.

1 – Contamos el número de ocurrencias de cada elemento (no es necesario contar hacia la izquierda porque si existe ya se ha contado antes). Para el primer ciclo, podríamos habernos detenido en n/2 + 1 porque incluso si todos los siguientes elementos fueran idénticos, aún no sería la mayoría.

algoritmo recursivo mayoritario

2 – Partiremos del principio de divide y vencerás:

algoritmo recursivo mayoritario

Si hay un elemento mayoritario x en E, entonces x es mayoritario en al menos una de las dos listas E1 y E2 (en efecto, si x no tiene mayoría en E1, ni en E2, entonces en E, número de x ≤ n/4 + n/4 = n/2).

El principio de recursión es entonces el siguiente: calcular los elementos mayoritarios de E1 y E2 (si existen) con el número total de ocurrencias de cada uno y deducir si uno de los dos es mayoritario en E.

El siguiente algoritmo Majority(i, j) devuelve un par que es igual a (x, cx) si x es la mayoría en el subarreglo E[i..j] con cx ocurrencias y que es igual a (−, 0) si existe no hay mayoría en E[i..j], siendo la llamada inicial Mayoría(1, n). La función Occurence(x, i, j) calcula el número de ocurrencias de x en el subarreglo E[i..j].

algoritmo recursivo mayoritario

No es tan fácil de entender, tomemos un ejemplo de una matriz de 8 elementos con 5 elementos idénticos para comprender completamente cómo funciona.

algoritmo recursivo mayoritario

Aquí está el algoritmo mayoritario teniendo en cuenta las nuevas propiedades:

mayoría divide y vencerás

Ejercicio 4

1 – Proponer un algoritmo de divide y vencerás buscando el mínimo de un arreglo.

2 – Así mismo con el máximo.

3 – Del mismo modo buscando tanto el mínimo como el máximo.

Daré la respuesta directamente a la pregunta 3 ya que contiene la respuesta a las dos anteriores. En este método, es necesario recordar las posiciones en la tabla así como el valor mínimo y máximo.

min max divide y vencerás

Ejercicio 5

Aquí está la fórmula del producto matriz:

producto de matriz

1 – Proponer un algoritmo iterativo y dar su complejidad.

Para descomponer una matriz en una dicotomía, se debe hacer tanto en las filas como en las columnas, por lo tanto en 4 partes como el siguiente diagrama:

pedrería

Cada elemento es una matriz cuadrada. Denotemos r=ae+bg, s=af+bh, t=ce+dg y u=cf+dh.

2 – Strassen ha encontrado un método para reducir aún más el número de cálculos. Propone calcular r, s, t, u mediante una combinación lineal (suma o resta) de las siguientes matrices:

algoritmo de strassen

Exprese r, s, t, u en términos de pi.

3 – Proponer un algoritmo recursivo basado en los cálculos de Strassen para el producto de matrices.

1 – Notamos en la fórmula que tendremos que hacer tres bucles según i, j y k. 

algoritmo de producto de matriz

En lo profundo de las estructuras de iteración, hay tres bucles anidados de 1 a n, por lo que una complejidad de O(n^3)

2 – Esto da las siguientes relaciones lineales:

algoritmo de strassen

3 – El algoritmo divide y vencerás es el siguiente:

algoritmo de strassen

Ejercicio 6

Escribe un pseudocódigo para un algoritmo de Divide y vencerás para encontrar la posición del elemento más grande en una matriz de números. Escribe un pseudocódigo para un algoritmo de fuerza bruta, compara con el anterior. Mostrar un árbol del proceso del algoritmo divide y vencerás. ¿Cuál es el nivel máximo de árbol para los números?

divide y vencerás programación dinámica ejercicios corregidos

El algoritmo de fuerza bruta es trivial: un bucle.

En cada nivel l, el árbol binario completo se compone de 2^(l-1) hojas. Entonces el total de los vértices es 2^l -1. Sea l el nivel del árbol, entonces l=sup(log_2 (n)).

Ejercicio 7

Escriba un pseudocódigo para un algoritmo de divide y vencerás para el problema de exponenciación de calcular a^n donde a>0 y n es un número entero positivo. Escribe un pseudocódigo para un algoritmo de fuerza bruta, compara con el anterior. Muestre un árbol de procesos del algoritmo divide y vencerás. ¿Cuál es el nivel máximo del árbol para n no dado? Comprobar el terminación, exactitud y exhaustividad.

Ejercicio 8

Para multiplicar dos números enteros de n dígitos, un método ingenuo consiste en multiplicar cada dígito del primer número por cada dígito del segundo, y hacer las compensaciones correctas y las sumas correctas. El tiempo de cálculo está entonces en O(n²).

El algoritmo de Karatsuba utiliza el principio de que el cálculo utilizado en este enfoque ingenuo:

(a × 10^k+ b)(c × 10k+ d) = ac × 10^2k+ (ad + bc) × 10^k+ bd

requerir cuatro productos (ac, ad, bc y bd) se puede hacer con solo tres productos agrupando los cálculos de la siguiente forma:

(a × 10^k + b)(c × 10^k + d) = ac × 10^2k + (ac + bd − (a − b)(c − d)) × 10^k + bd

Ciertamente se han introducido las restas, pero ahora solo son necesarios tres productos de números grandes: ac, bd y (a − b)(c − d).

Como las sumas y restas son económicas (insignificantes en comparación con las multiplicaciones), ahorraremos tiempo de cálculo. Para información, la multiplicación por una potencia de la base de cálculo corresponde a un desplazamiento de dígito y es muy rápida de ejecutar en una máquina.

Escriba el código de la función karatsuba() que permita multiplicar dos enteros grandes de n dígitos según este principio.

Ejercicio 9

Dado un conjunto de puntos reales, encuentre la distancia mínima entre dos puntos usando un algoritmo tipo Divide and Conquer. Para ello utilizaremos la distancia euclidiana entre dos puntos.

La solución obvia es hacer una matriz de distancia entre cada par de puntos. El algoritmo divide y vencerás corta el espacio recursivamente en 2 bloques y busca la distancia mínima en cada bloque. Además, entonces es necesario mirar la distancia más pequeña entre puntos de dos bloques diferentes.

distancia mínima divide y vencerás

Solución de divide y vencerás
— Ordenar los puntos en relación con sus coordenadas x.
— Divide los puntos en dos grupos: la mitad izquierda y la mitad derecha.
— Use la recursividad para encontrar dg, la distancia mínima entre los puntos de
izquierda.
— Use la recursividad para encontrar dd, la distancia mínima entre puntos de línea.
— La solución óptima es:
     - ya sea dg,
     - ya sea dd,
     — sea la distancia entre dos puntos A y B tal que A está en la parte
izquierda y B está en la parte derecha.

Sea midx la coordenada x del punto más a la derecha entre los puntos de la izquierda. Tenga en cuenta que en el tercer caso citado anteriormente, los dos puntos A y B están ubicados en una banda delgada de ancho min(dg, dd), centrada en midx.

Notamos en la banda central, dos puntos ubicados en el mismo lado de la
el límite midx están al menos a una distancia d entre sí. Esta información se utiliza de la siguiente manera:

— Comenzamos ordenando todos los puntos presentes en la banda central según su coordenada y.

 Para cada punto A de la banda central, nos fijamos en la distancia que lo separa de los puntos situados en su radio.

distancia mínima divide y vencerás

Ejercicio 10

En este ejercicio, estamos interesados en la complejidad en el peor de los casos y en el número de comparaciones de los algoritmos.

1. Para encontrar el elemento más grande y el segundo más grande de n enteros, dé un algoritmo simple y su complejidad.

2. Para mejorar el rendimiento, proponemos considerar la solución que consiste en calcular el máximo según el principio de Divide y vencerás

1.

doble máximo

2.

El principio es bastante simple ya que está cerca del algoritmo Merge Sort. Durante el reinado se levanta una tupla de dos elementos (max1, max2) o max1 > max2. El reinado consiste en comparar las tuplas izquierda y derecha y devolver las dos más grandes. Así, cada rama devolverá los dos mayores de su subarreglo hasta obtener los dos mayores del arreglo en su totalidad.

Ejercicio 11

Dada una matriz de enteros, encuentre la suma máxima entre todas las subarreglas posibles. Los subconjuntos deben ocupar posiciones consecutivas en el conjunto original.

Entrada: números[] = [2, -4, 1, 9, -6, 7, -3]

Salida: la suma máxima del subarreglo es 11 (marcado en audaz)

La idea es usar la técnica Divide and Conquer para encontrar la suma máxima de los sub-arreglos. El algoritmo funciona de la siguiente manera:

  1. Divida la matriz en dos sub-matrices iguales.
  2. Calcule recursivamente la suma máxima de subarreglos para el subarreglo izquierdo,
  3. Calcule recursivamente la suma máxima de subarreglos para el subarreglo derecho,
  4. Encuentre la suma máxima del subarreglo que cruza el elemento del medio.
  5. Devuelve el máximo de las tres sumas anteriores.
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
#include <stdio.h>
#include <limits.h>
 
// Función de utilidad para encontrar el máximo de dos números
int max(int x, int y) {
    return (x > y) ? x : y;
}
 
// Función para encontrar la suma máxima de subarreglo usando divide y vencerás
int maximum_sum(int nums[], int low, int high)
{
    // Si la matriz contiene 0 o 1 elemento
    if (high <= low) {
        return nums[low];
    }
 
    // Encuentra el elemento de la matriz del medio
    int mid = (low + high) / 2;
 
    // Encuentra la suma máxima de subarreglo para el subarreglo izquierdo,
    // incluyendo el elemento del medio
    int left_max = INT_MIN;
    int sum = 0;
    for (int i = mid; i >= low; i)
    {
        sum += nums[i];
        if (sum > left_max) {
            left_max = sum;
        }
    }
 
    // Encuentra la suma máxima de subarreglo para el subarreglo derecho,
    // excluyendo el elemento del medio
    int right_max = INT_MIN;
    sum = 0;    // restablece la suma a 0
    for (int i = mid + 1; i <= high; i++)
    {
        sum += nums[i];
        if (sum > right_max) {
            right_max = sum;
        }
    }
 
    // Encuentra recursivamente la suma máxima de subarreglo para la izquierda
    // y subarreglo derecho, y toma el máximo
    int max_left_right = max(maximum_sum(nums, low, mid),
                            maximum_sum(nums, mid + 1, high));
 
    // devuelve el máximo de los tres
    return max(max_left_right, left_max + right_max);
}
 
int main(void)
{
    int arr[] = { 2, 4, 1, 9, 6, 7, 3 };
    int n = sizeof(arr) / sizeof(arr[0]);
 
    printf(« The maximum sum of the subarray is %d »,
            maximum_sum(arr, 0, n 1));
 
    return 0;
}

Podemos resolver fácilmente este problema en tiempo lineal usando el algoritmo de Kadane. La idea es mantener un subarreglo máximo (suma positiva) que "termina" en cada índice del arreglo dado. Este subarreglo está vacío (en cuyo caso su suma es cero) o consta de un elemento más que el subarreglo máximo que termina en el índice anterior.

algoritmo de kadanes

Ejercicio 12

Dada una matriz de enteros, encuentre el elemento pico que contiene. Un elemento pico es un elemento superior a sus vecinos. Puede haber varios elementos de pico en una matriz y la solución debe informar cualquier elemento de pico.

Un elemento A[i] de un arreglo A es un elemento pico si no es más pequeño que su(s) vecino(s).
A[i-1] <= A[i] >= A[i+1] para 0 < i < n-1
A[i-1] <= A[i] si i = n – 1
A[i] >= A[i+1] si i = 0

Por ejemplo,
Entrada: [8, 9, 10, 2, 5, 6]
Salida: el elemento pico es 10 (o 6)


Entrada: [8, 9, 10, 12, 15]
Salida: el elemento pico es 15


Entrada: [10, 8, 6, 5, 3, 2]
Salida: el elemento pico es 10

Una solución ingenua sería probar todos los elementos para el pico ejecutando una búsqueda lineal en la matriz y devolviendo el elemento más grande que sus vecinos. Hay que tratar dos casos particulares. Si la matriz se ordena en orden descendente, su elemento máximo es el primer elemento. Si la matriz se ordena en orden ascendente, el elemento de pico es el último. El problema con este enfoque es que su complejidad temporal en el peor de los casos es O(n), donde n es el tamaño de la entrada.

Podemos resolver fácilmente este problema en tiempo O(log(n)) usando una idea similar al algoritmo de búsqueda binaria. La idea es calcular el índice de la mediana y, si el elemento central es mayor que sus dos vecinos, devolver el elemento como si fuera un pico. Si el vecino derecho del índice de la mediana es mayor que el elemento del medio, busque recursivamente el pico en el lado derecho de la matriz. Si el vecino izquierdo del índice medio es mayor que el elemento medio, busque recursivamente el pico en el lado izquierdo de la matriz.

pic elemento divide y vencerás

Ejercicio 13

Dada una matriz ordenada con elementos posiblemente duplicados, la tarea es encontrar los índices de la primera y última aparición de un elemento x en la matriz dada.

Ejemplos:

Entrada: tabulador[] = {1, 3, 5, 5, 5, 5, 67, 123, 125}, x = 5
Salida: Primera ocurrencia = 2
Última aparición = 5

Entrada: tabulador[] = {1, 3, 5, 5, 5, 5, 7, 123, 125 }, x = 7
Salida: Primera ocurrencia = 6
Última ocurrencia = 6

La idea para resolver este problema es iterar sobre los elementos de una matriz dada y comprobar los elementos dados en una matriz y realizar un seguimiento de la primera y última aparición del índice del elemento encontrado.

Ejecute un ciclo for y for i = 0 a n-1
Tomar primero = -1 y último = -1
Cuando encontramos un elemento por primera vez, primero actualizamos = i
Siempre actualizamos last=i cada vez que encontramos el elemento.
Imprimimos primero y último.

encontrar ocurrencia

Un enfoque eficiente utilizando la búsqueda binaria:

1. Para la primera aparición de un número

a) Si (alto >= bajo)
b) Calcular medio = bajo + (alto – bajo)/2;
c) Si ((medio == 0 || x > arr[medio-1]) && arr[medio] == x)
espalda media;
d) De lo contrario si (x > arr[medio])
return first(arr, (middle+1), top, x, n);
e) De lo contrario
return first(arr, low, (mid-1), x, n);
f) De lo contrario, devuelve -1;

2. Por la última ocurrencia de un número

a) si (alto >= bajo)
b) calcular medio = bajo + (alto – bajo)/2;
c)si( ( medio == n-1 || x < arr[medio+1]) && arr[medio] == x )
espalda media;
d) else if(x < arr[medio])
return last(arr, low, (mid-1), x, n);
e) más
return last(arr, (mid + 1), high, x, n);
f) sino devuelve -1;

encontrar ocurrencia

Ejercicio 14

Dados n edificios rectangulares en una ciudad bidimensional, calcule el horizonte de estos edificios, eliminando las líneas ocultas. La tarea principal es ver los edificios desde un lado y eliminar todas las secciones no visibles.

Todos los edificios comparten un fondo común y cada edificio está representado por un triplete (izquierda, altura, derecha)

'izquierda': es la coordenada x del lado izquierdo (o del muro).
'derecha': es la coordenada x del lado derecho
'ht': es la altura del edificio.
Una línea de horizonte es un conjunto de bandas rectangulares. Una tira rectangular está representada por un par (izquierda, ht) donde izquierda es la coordenada x del lado izquierdo de la tira y ht es la altura de la tira.

Ejemplos:

Entrada: matriz de edificios
{ (1, 11, 5), (2, 6, 7), (3, 13, 9), (12, 7, 16), (14, 3, 25),
(19, 18, 22), (23, 13, 29), (24, 4, 28) }

Salida: Skyline (un conjunto de tiras rectangulares)
Una tira tiene la coordenada x del lado izquierdo y la altura
(1, 11), (3, 13), (9, 0), (12, 7), (16, 3), (19, 18),
(22, 3), (25, 0)

La siguiente imagen es para la entrada 1:

Problema de SkyLine

Podemos encontrar Skyline en el tiempo Θ(nLogn) usando Divide and Conquer. La idea es similar a Merge Sort, dividiendo el conjunto dado de edificios en dos subconjuntos. Construya recursivamente el horizonte por dos mitades y finalmente fusione los dos horizontes.

La idea es similar a la combinación de clasificación de combinación, comience con las primeras bandas de dos horizontes, compare las coordenadas x. Elija la banda con la coordenada x más pequeña y súmela al resultado. La altura de la franja añadida se toma como el máximo de las alturas actuales de skyline1 y skyline2.

La altura de la nueva tira siempre se obtiene tomando el siguiente máximo

(a) Altura actual del horizonte1, digamos 'h1'.
(b) Altura actual del horizonte2, diga 'h2'

h1 y h2 se inicializan en 0. h1 se actualiza cuando se agrega una franja SkyLine1 al resultado y h2 se actualiza cuando se agrega una franja SkyLine2.

Horizonte1 = {(1, 11), (3, 13), (9, 0), (12, 7), (16, 0)}
Horizonte2 = {(14, 3), (19, 18), (22, 3), (23, 13), (29, 0)}
Resultado = {}
h1 = 0, h2 = 0

Compara (1, 11) y (14, 3). Dado que la primera banda tiene una x izquierda más pequeña, agréguela al resultado e incremente el índice para Skyline1.
h1 = 11, nueva altura = max(11, 0)
Resultado = {(1, 11)}

Compara (3, 13) y (14, 3). Dado que la primera banda tiene una x izquierda más pequeña, agréguela al resultado e incremente el índice para Skyline1
h1 = 13, nueva altura = max(13, 0)
Resultado = {(1, 11), (3, 13)}

De manera similar se suman (9, 0) y (12, 7).
h1 = 7, nueva altura = max(7, 0) = 7
Resultado = {(1, 11), (3, 13), (9, 0), (12, 7)}

Compara (16, 0) y (14, 3). Como la segunda banda tiene una x izquierda más pequeña, se suma al resultado.
h2 = 3, nueva altura = max(7, 3) = 7
Resultado = {(1, 11), (3, 13), (9, 0), (12, 7), (14, 7)}

Compara (16, 0) y (19, 18). Como la primera banda tiene una x izquierda más pequeña, se suma al resultado.
h1 = 0, nueva altura = max(0, 3) = 3
Resultado = {(1, 11), (3, 13), (9, 0), (12, 7), (14, 7), (16, 3)}

Dado que Skyline1 no tiene más elementos, se agregan todos los elementos restantes de Skyline2
Resultado = {(1, 11), (3, 13), (9, 0), (12, 7), (14, 7), (16, 3),
(19, 18), (22, 3), (23, 13), (29, 0)}

Una observación con respecto a la salida anterior es que la tira (14, 7) es redundante (ya hay una tira de la misma altura). Eliminamos todos los elementos redundantes.
bandas.
Resultado = {(1, 11), (3, 13), (9, 0), (12, 7), (16, 3), (19, 18),
(22, 3), (23, 13), (29, 0)}

En el código a continuación, la redundancia se maneja al no agregar una banda si la banda anterior en el resultado tiene la misma altura.

horizonte divide y vencerás

horizonte divide y vencerás

Ejercicio 15

Dada una matriz de citas enteras donde citas[i] es el número de citas que recibió un investigador por su i-ésimo artículo y las citas están ordenadas en orden ascendente, vuelva a calcular el índice h del investigador.

De acuerdo con la definición de índice h de Wikipedia: un científico tiene un índice h si h de sus n artículos tienen al menos h citas cada uno, y los otros n − h artículos no tienen más de h citas cada uno.

Si hay varios valores posibles para h, se toma como índice h el valor máximo.

Entrada: comillas = [0,1,3,5,6]
Salida: 3
Explicación: [0,1,3,5,6] significa que el investigador tiene 5 artículos en total y cada uno de ellos recibió 0, 1, 3, 5, 6 citas respectivamente.

Dado que el investigador tiene 3 artículos con al menos 3 citas cada uno y los otros dos con no más de 3 citas cada uno, su índice h es 3.

Solo búsqueda binaria, cada vez que verifique las comillas [mid]

caso 1: citas[mid] == len-mid, entonces eso significa que hay citas[mid] artículos que tienen al menos citas[mid] citas.

caso 2: comillas[mid] > len-mid, entonces eso significa que hay artículos de comillas[mid] que tienen más comillas[mid] comillas, por lo que debemos seguir buscando en la mitad izquierda

caso 3: citations[mid] < len-mid, debe continuar la búsqueda en la parte derecha

Después de la iteración, se garantiza que right+1 sea el que necesitamos encontrar (es decir, len-(right+1) papers tiene al menos len-(right+1) citas)

El siguiente algoritmo está escrito en forma iterativa pero es divide y vencerás:

índice h divide y vencerás

Ejercicio 16

En el problema "Koko comiendo plátanos", se nos da una matriz de tamaño n que contiene el número de plátanos en cada montón. En una hora, Koko puede comer un máximo de plátanos K. Si la pila contiene menos de K bananas, entonces si Koko termina todas las bananas de esta pila, no puede comenzar a comer bananas de otra pila en la misma hora.

Koko quiere comerse todos los plátanos en H horas. Se supone que debemos encontrar el valor mínimo de K.

pilas = [30,11,23,4,20], H = 6. Aquí la respuesta es 23.

22 Ejercicios corregidos Algoritmo divide y vencerás divide y vencerás

Koko comerá plátanos de esta manera para comerse todos los plátanos en 6 horas:

Primera hora: 23

Segunda hora: 7

Tercera hora: 11

Cuarta hora: 23

Quinta hora: 4

Sexta hora: 20

Lo primero y más importante para resolver este problema es sacar observaciones. Aquí hay algunas observaciones para nuestro rango de búsqueda:

Koko debe comer al menos un plátano por hora. Así que este es el valor mínimo de K. Vamos a llamarlo Inicio

Podemos limitar el número máximo de plátanos que Koko puede comer en una hora al número máximo de plátanos en un montón entre todos los montones. Es por tanto el valor máximo de K. Llamémoslo Fin.

Ya tenemos nuestro rango de búsqueda. Suponga que el tamaño del intervalo es Longitud y el número de pilas es n. El enfoque ingenuo podría ser verificar todos los valores intermedios. si para este valor de K Koko puede comerse todos los plátanos en la hora H con éxito, elige el mínimo de ellos. La complejidad de tiempo para el enfoque ingenuo será Longitud*n en el peor de los casos.

Podemos mejorar la complejidad del tiempo utilizando la búsqueda binaria en lugar de la búsqueda lineal. El algoritmo está escrito de forma iterativa, pero de hecho es un enfoque de Divide y vencerás.

22 Ejercicios corregidos Algoritmo divide y vencerás divide y vencerás

Ejercicio 17

Dada una matriz ordenada de enteros distintos no negativos, encuentre el elemento no negativo faltante más pequeño en ella.

Por ejemplo,

Entrada: números[] = [0, 1, 2, 6, 9, 11, 15]
Resultado: El elemento faltante más pequeño es 3


Entrada: números[] = [1, 2, 3, 4, 6, 9, 11, 15]
Salida: el elemento faltante más pequeño es 0


Entrada: números[] = [0, 1, 2, 3, 4, 5, 6]
Resultado: El elemento faltante más pequeño es 7

Una solución ingenua sería ejecutar una búsqueda lineal en la matriz y devolver el primer índice, que no coincide con su valor. Si no se produce ninguna discrepancia, devuelve el tamaño de la matriz. El problema con este enfoque es que su complejidad temporal en el peor de los casos es O(n), donde n es el tamaño de la entrada. Esta solución tampoco aprovecha el hecho de que la entrada está ordenada.

Podemos resolver fácilmente este problema en tiempo O(log(n)) modificando el algoritmo de búsqueda binaria (equivalente a Divide and Conquer). La idea es comparar el índice de la mediana con el elemento de la mediana. Si los dos son iguales, entonces la discrepancia está en el subarreglo correcto; de lo contrario, está en el subconjunto izquierdo. Así que descartamos una mitad en consecuencia y volvemos por la otra.

elemento faltante más pequeño

Ejercicio 18

Dada una matriz de enteros nums y un entero k, devuelve el k-ésimo elemento más grande de la matriz.

Tenga en cuenta que este es el k-ésimo elemento más grande en orden ordenado, no el k-ésimo elemento distinto.

Tienes que resolverlo en complejidad de tiempo O (nlogn).

Ejemplo 1:

Entrada: números = [3,2,1,5,6,4], k = 2
Salida: 5

Ejemplo 2:

Entrada: números = [3,2,3,1,2,4,5,5,6], k = 4
Salida: 4

Para solucionar este problema debemos ir a lo más sencillo. Ordene la matriz en O (nlogn) y luego itere a través de ella de mayor a menor. Un contador se incrementa tan pronto como cambiamos de número, devolvemos el número del k-ésimo cambio.

Ejercicio 19

Dada una matriz de enteros nums, devuelve una matriz de números enteros donde counts[i] es el número de elementos más pequeños a la derecha de nums[i].

Entrada: números = [5,2,6,1]
Salida: [2,1,1,0]

Explicación:
A la derecha de 5 hay 2 elementos más pequeños (2 y 1).
A la derecha de 2, solo hay un elemento más pequeño (1).
A la derecha de 6 hay 1 elemento más pequeño (1).
A la derecha de 1 hay 0 elemento más pequeño.

Los números más pequeños a la derecha de un número son exactamente aquellos que saltan de su derecha a su izquierda durante una ordenación estable. Así que estoy haciendo una clasificación por combinación con un seguimiento adicional de esos saltos de derecha a izquierda. Aquí están los algoritmos en su forma iterativa.

Ordenamos los pares (índice, valor). El valor se usa para ordenar y el índice se usa para el seguimiento de saltos.

22 Ejercicios corregidos Algoritmo divide y vencerás divide y vencerás

También puede ordenar solo índices y buscar números reales para realizar comparaciones sobre la marcha. Tal vez un poco más fácil de entender y portar en otros idiomas:

22 Ejercicios corregidos Algoritmo divide y vencerás divide y vencerás

Ejercicio 20

Dadas dos matrices ordenadas nums1 y nums2 de tamaño m y n respectivamente, devuelve la mediana de las dos matrices ordenadas.

La complejidad total del tiempo de ejecución debe ser O(log (m+n)).

Ejemplo 1:

Entrada: nums1=[1,3], nums2=[2]
Salida: 2.00000
Explicación: matriz fusionada = [1,2,3] y la mediana es 2.

Ejemplo 2:

Entrada: nums1 = [1,2], nums2 = [3,4]
Salida: 2.50000
Explicación: matriz combinada = [1,2,3,4] y la mediana es (2 + 3) / 2 = 2,5.

Veamos primero el concepto de 'MEDIAN' de una manera poco convencional. Es decir:

"si cortamos la matriz ordenada en dos mitades de LONGITUDES IGUALES, entonces la mediana es la MEDIA DE Máx. (mitad_inferior) y Mín. (mitad_superior), es decir, los dos números inmediatamente al lado del corte".

Por ejemplo, para [2 3 5 7], cortamos entre 3 y 5:
[2 3 / 5 7]
entonces la mediana = (3+5)/2.

Aquí está el algoritmo Divide and Conquer:

22 Ejercicios corregidos Algoritmo divide y vencerás divide y vencerás

encuentre el k-ésimo elemento en las dos matrices ordenadas: A[aMid] <= B[bMid], x: la mitad de la longitud de a, y: la mitad de la longitud de b, entonces podemos saber

(1) habrá al menos (x + 1 + y) elementos antes de bMid
(2) habrá al menos (m – x – 1 + n – y) = m + n – (x + y +1) elementos después de aMid

Entonces

si k <= x + y + 1, encuentre el k-ésimo elemento en a y b, pero ignore bMid y su sufijo

si k > x + y + 1, encuentre el k – (x + 1)-ésimo elemento en a y b, pero sin considerar aMid y su prefijo

22 Ejercicios corregidos Algoritmo divide y vencerás divide y vencerás

Ejercicio 21

Su tarea es calcular a^b mod 1337 donde a es un entero positivo yb es un entero positivo extremadamente grande dado como una matriz.

Un conocido: ab % k = (a%k)(b%k)%k

Dado que el poder aquí es una matriz, será mejor que lo manejemos dígito por dígito. Un descubrimiento :

a^1234567 % k = (a^1234560 % k) * (a^7 % k) % k = (a^123456 % k)^10 % k * (a^7 % k) % k

¿Te parece complicado? Permítanme decirlo de otra manera:

Suponga que f(a, b) calcula a^b % k; Luego traduce la fórmula anterior usando f:

f(a,1234567) = f(a, 1234560) * f(a, 7)% k = f(f(a, 123456),10) * f(a,7)%k ;

Implementación de esta idea:

súper poder

Ejercicio 22

Para calcular el área bajo la curva, es posible rodear la curva con un rectángulo y deducir que el área de la curva está en el orden de magnitud del área del rectángulo.

El método de los rectángulos es un método algorítmico lo que permite obtener un marco de una integral. Como recordatorio ; una función positiva sobre un intervalo [a,b], cuya integral sobre este intervalo es el área bajo la curva que representa f y el eje de abscisas.

En el algoritmo Divide and Conquer, el intervalo [a,b] se subdivide en n intervalos de ancho menor que un umbral k (siendo k la precisión de cálculo de la integral).

Sea I el centro de un intervalo, el área bajo la curva en este intervalo es por lo tanto igual al rectángulo cuya altura está definida por f(I). Por lo tanto, el área en el intervalo original es igual a la suma de todas las áreas subdivididas.

También es posible acotar el área bajo la curva considerando que es del mismo tamaño que la suma de los rectángulos de altura f(a) y del mismo tamaño que la suma de los rectángulos de altura f(b).

Existe un tercer método para simular el área bajo la curva: el método del trapecio. 

22 Ejercicios corregidos Algoritmo divide y vencerás divide y vencerás

Para calcular el área del trapecio ABED sumamos las áreas del rectángulo ABCD y del triángulo rectángulo BEC. El área del trapecio es una representación del área bajo la curva en el intervalo [a,b].

Los algoritmos son muy simples. Mientras no se alcance el tamaño del umbral, devolvemos method(a, (a+b)/2, function) + method ((a+b)/2, b, function).

Este cálculo permite sumar las partes izquierda y derecha de la división del intervalo. Una vez alcanzado el umbral, el método devuelve el cálculo del área correspondiente al enunciado estudiado.

Para los rectángulos dichos a la derecha tendremos como suma total:

método del rectángulo

Para los rectángulos dichos a la izquierda tendremos como suma total:

método del rectángulo

Para el método del trapecio, el cálculo de cada subintervalo viene dado por la siguiente fórmula:

22 Ejercicios corregidos Algoritmo divide y vencerás divide y vencerás