El nombre realmente se ajusta bien al propósito general:
- Divide el problema en dos o más problemas más pequeños que puede resolver de forma independiente.
- Conquiste el problema (que es una buena manera de llamar para encontrar una solución) combinando los resultados de sus problemas más pequeños en el resultado.
Lo bueno de este enfoque es que puede repetir el primer paso hasta llegar al problema de un tamaño que sea solucionable, y luego combinar las respuestas de subproblemas más pequeños en consecuencia.
Usemos este método para encontrar el mayor de siete números:
- ¿Por qué la clasificación de montón se considera un algoritmo in situ?
- Cómo restar enteros usando un algoritmo
- ¿Por qué Google dice que 'Global University' es una de las mejores universidades?
- ¿Cuáles son los ejemplos de implementación de algoritmos de clasificación en Android?
- ¿Por qué deberíamos conocer más de un algoritmo de clasificación en Python (burbuja, inserción, selección) si todos están haciendo el mismo trabajo?
[matemáticas] [3, 19, 7, 11, 13, 2, 5] [/ matemáticas]
Pero aquí está el truco: solo sabemos cómo comparar dos números, nada más. Entonces dividimos el problema en dos problemas: vamos a encontrar el mayor número en [matemáticas] [3, 19, 7] [/ matemáticas] y luego lo compararemos con el mayor número en [matemáticas] [11, 13, 2, 5] [/ matemáticas].
El primer conjunto de tres números sigue siendo demasiado grande, por lo que lo dividimos en [matemáticas] [3] [/ matemáticas] y [matemáticas] [19, 7] [/ matemáticas].
Ahora finalmente podemos hacer más. Tenemos dos matrices con uno o dos números cada una, por lo que podemos juzgar que el número más grande (ya que es el único) en el primero es 3 y en el segundo – 19. Cuando los comparamos, vemos que el mayor número del primer conjunto es menor que el mayor número del segundo conjunto. De esta manera llegamos a la conclusión de que el mayor número en [matemáticas] [3, 19, 7] [/ matemáticas] es 19.
Analógicamente podemos ver que el número más grande en la segunda matriz de cuatro números es, por supuesto, 13. Cuando lo comparamos con el resultado de la primera matriz, llegamos a la conclusión de que el mayor de los ocho números dados es 19.
Este fue un largo ejemplo, pero creo que ilustra el concepto lo suficientemente bien. Algunos algoritmos populares que hacen uso de ese concepto son Quicksort y Mergesort: si comprende cómo funcionan, comprenderá el concepto de dividir y conquistar aún mejor. ¡Buena suerte!
