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.
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.
b- El algoritmo iterativo es el siguiente:
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:
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:
Para mayor complejidad, dado que aún no hemos visto el Teorema del maestro, usaremos el árbol de llamadas:
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:
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.
2 – Partiremos del principio de divide y vencerás:
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].
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.
Aquí está el algoritmo mayoritario teniendo en cuenta las nuevas propiedades:
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.
Ejercicio 5
Aquí está la fórmula del producto 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:
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:
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.
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:
3 – El algoritmo divide y vencerás es el siguiente:
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?
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.
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.
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.
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:
- Divida la matriz en dos sub-matrices iguales.
- Calcule recursivamente la suma máxima de subarreglos para el subarreglo izquierdo,
- Calcule recursivamente la suma máxima de subarreglos para el subarreglo derecho,
- Encuentre la suma máxima del subarreglo que cruza el elemento del medio.
- 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.
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.
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.
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;
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:
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.
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:
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.
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.
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.
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.
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:
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:
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
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:
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.
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:
Para los rectángulos dichos a la izquierda tendremos como suma total:
Para el método del trapecio, el cálculo de cada subintervalo viene dado por la siguiente fórmula:
ES 
FR 
EN