Categoría: Divide and Conquer

Encuentre la cantidad de números diferentes en la array después de aplicar la operación dada q veces

Posted on by Rudeus Greyrat

Dada una array de tamaño N, inicialmente solo consta de ceros. La tarea es aplicar la operación dada q veces y encontrar la cantidad de números diferentes en la array, excepto los ceros. Formato de operación: actualizar (l, r, x):: actualizar a[i] = x para todos (l <= i <= r).  Ejemplos:  Entrada: N = 5, … Continue reading «Encuentre la cantidad de números diferentes en la array después de aplicar la operación dada q veces»

Encuentre el término N (un ejemplo de exponenciación matricial)

Posted on by Rudeus Greyrat

Se nos da una función recursiva que describe enésimos términos en forma de otros términos. En este artículo, hemos tomado ejemplos específicos. Ahora te dan n, y tienes que encontrar el término n utilizando la fórmula anterior. Ejemplos:  Input : n = 2 Output : 5 Input : n = 3 Output :13 Requisito previo:  enfoque … Continue reading «Encuentre el término N (un ejemplo de exponenciación matricial)»

Algoritmo de Floyd-Rivest

Posted on by Rudeus Greyrat

El algoritmo de Floyd-Rivest es un algoritmo de selección que se utiliza para encontrar el k -ésimo elemento más pequeño en una array de elementos distintos. Es similar al algoritmo QuickSelect pero tiene un mejor tiempo de ejecución en la práctica. Al igual que QuickSelect, el algoritmo funciona con la idea de la partición. Después de … Continue reading «Algoritmo de Floyd-Rivest»

Encuentre el valor de XXXX…..(N veces) % M donde N es grande

Posted on by Rudeus Greyrat

Dados tres enteros X , N y M . La tarea es encontrar XXX…(N veces) % M donde X puede ser cualquier dígito del rango [1, 9] . Ejemplos:   Entrada: X = 7, N = 7, M = 50  Salida: 27  7777777 % 50 = 27 Entrada: X = 1, N = 10, M = … Continue reading «Encuentre el valor de XXXX…..(N veces) % M donde N es grande»

Programa C++ para encontrar el número más cercano en una array

Posted on by Rudeus Greyrat

Dada una array de enteros ordenados. Necesitamos encontrar el valor más cercano al número dado. La array puede contener valores duplicados y números negativos.  Ejemplos:   Input : arr[] = {1, 2, 4, 5, 6, 6, 8, 9} Target number = 11 Output : 9 9 is closest to 11 in given array Input :arr[] = … Continue reading «Programa C++ para encontrar el número más cercano en una array»

Algoritmo de Karatsuba para la multiplicación rápida de números decimales grandes representados como strings

Posted on by Rudeus Greyrat

Dadas dos strings numéricas A y B , la tarea es encontrar el producto de las dos strings numéricas de manera eficiente. Ejemplo: Entrada: A = 5678, B = 1234 Salida: 7006652 Entrada: A =74638463789, B = 35284567382 Salida: 2633585904851937530398 Enfoque: el problema dado se puede resolver usando el algoritmo de multiplicación rápida de Karastuba … Continue reading «Algoritmo de Karatsuba para la multiplicación rápida de números decimales grandes representados como strings»

Búsqueda binaria – Part 3

Posted on by Rudeus Greyrat

Problema: dada una array ordenada arr[] de n elementos, escriba una función para buscar un elemento dado x en arr[] y devuelva el índice de x en la array.                  Considere que la array tiene un índice base 0. Ejemplos:  Entrada: arr[] = {10, 20, 30, 50, 60, … Continue reading «Búsqueda binaria – Part 3»

Máximo y mínimo de una array usando el número mínimo de comparaciones

Posted on by Rudeus Greyrat

Escriba una función C para devolver el mínimo y el máximo en una array. Su programa debe hacer el mínimo número de comparaciones.  En primer lugar, ¿cómo devolvemos múltiples valores de una función C? Podemos hacerlo usando estructuras o punteros. Hemos creado una estructura llamada par (que contiene mínimo y máximo) para devolver múltiples valores.  C++ … Continue reading «Máximo y mínimo de una array usando el número mínimo de comparaciones»

Programación dinámica vs divide y vencerás

Posted on by Rudeus Greyrat

TL;DR En este artículo, trato de explicar las diferencias/similitudes entre la programación dinámica y los enfoques de divide y vencerás basándome en dos ejemplos: búsqueda binaria y distancia mínima de edición (distancia de Levenshtein). El problema Cuando comencé a aprender algoritmos, me resultó difícil comprender la idea principal de la programación dinámica (DP) y en … Continue reading «Programación dinámica vs divide y vencerás»