Dada una array de montaña arr[] y un entero X , la tarea es encontrar el índice más pequeño de X en la array dada. Si no se encuentra dicho índice, imprima -1 . Ejemplos: Entrada: arr = {1, 2, 3, 4, 5, 3, 1}, X = 3 Salida: 2 Explicación: El índice más pequeño … Continue reading «Buscar un elemento en un Mountain Array»
Considere el problema de buscar un elemento x en una array ‘arr[]’ de tamaño n. El problema se puede resolver en tiempo O(Logn) si. 1) La array está ordenada 2) La array está ordenada y rotada por k. k se le da a usted y k <= n 3) La array se ordena y rota … Continue reading «Algoritmos | Divide y vencerás | Pregunta 6»
Considere el siguiente programa en C int main() { int x, y, m, n; scanf («%d %d», &x, &y); /* x > 0 and y > 0 */ m = x; n = y; while (m != n) { if(m>n) m = m – n; else n = n – m; } printf(«%d», n); } … Continue reading «Algoritmos | Divide y vencerás | Pregunta 2»
El problema de la suma máxima del subarreglo es encontrar el subarreglo con la suma máxima. Por ejemplo, dado un arreglo {12, -13, -5, 25, -20, 30, 10}, la suma máxima del subarreglo es 45. La solución ingenua para este problema es calcular la suma de todos los subarreglos comenzando con cada elemento y devolver … Continue reading «Algoritmos | Divide y vencerás | Pregunta 4»
Considere una situación en la que no tiene una función para calcular la potencia (función pow() en C) y necesita calcular x^n donde x puede ser cualquier número y n es un número entero positivo. ¿Cuál puede ser la mejor complejidad temporal posible de su función de potencia? (A) O(n) (B) O(nLogn) (C) O(LogLogn) (D) … Continue reading «Algoritmos | Divide y vencerás | Pregunta 5»
Considere el polinomio p(x) = a0 + a1x + a2x^2 +a3x^3, donde ai != 0, para todo i. El número mínimo de multiplicaciones necesarias para evaluar p en una entrada x es: (A) 3 (B) 4 (C) 6 (D) 9 Respuesta: (A) Explicación: Las multiplicaciones se pueden minimizar usando el siguiente orden para la evaluación … Continue reading «Algoritmos | Divide y vencerás | Pregunta 3»
¿Cuál de los siguientes algoritmos NO es un algoritmo divide y vencerás por naturaleza? (A) Algoritmo euclidiano para calcular el máximo común divisor (B) Ordenación en montón (C) Transformada rápida de Fourier de Cooley-Tukey (D) Ordenación rápida Respuesta: (B) Explicación: consulte el cuestionario Divide y vencerás de esta pregunta Publicación traducida automáticamente Artículo escrito por … Continue reading «Algoritmos | Divide y vencerás | Pregunta 6 – Part 1»
Dada una string binaria S de longitud N . La tarea es encontrar lo siguiente: El número mínimo de subsecuencias en las que se puede dividir la string S , de modo que la subsecuencia no contenga ceros ni unos adyacentes. Número de subsecuencia al que pertenece cada carácter de la string S. Si hay … Continue reading «Minimice el recuento de subsecuencias alternas para dividir la string binaria dada con el número de subsecuencia»