Si desea resolver un problema difícil, la estrategia de dividir y conquistar significa que lo divide en pequeños problemas más fáciles de resolver y utiliza esos algoritmos para resolver su problema difícil.
Solución 1
Digamos que quieres resolver [matemáticas] x ^ n [/ matemáticas]. En aras de mantenerlo simple, supongamos que n es un número entero. n podría ser positivo o negativo, así que dividamos nuestro problema en 2 problemas, uno para valores positivos y otro para valores negativos
- ¿Qué algoritmo debo usar para codificar un solucionador de Sudoku usando la teoría de grafos?
- ¿Cómo funciona el algoritmo de acortador de URL?
- ¿Por qué es difícil estimar el tiempo de ejecución exacto de un algoritmo?
- ¿Alguien puede dar un ejemplo en Java de pasar una matriz unidimensional, una matriz bidimensional y una matriz tridimensional por referencia y luego manipularlos?
- Si un gráfico G contiene un puente, e, ¿es posible construir un árbol de expansión que no incluya este borde?
potencia de def (x, n):
si n> = 0:
retorno positivo Potencia (x, n)
más:
retorno negativo Potencia (x, n)
Allí, dimos el primer paso en nuestra estrategia de divide y vencerás. Ahora tenemos 2 problemas más simples para resolver. Vamos a centrarnos en el problema de la energía positiva primero.
¿Cómo resolvemos [matemáticas] x ^ n [/ matemáticas] para positivo [matemáticas] n [/ matemáticas]? si [matemáticas] n = 0 [/ matemáticas], entonces el resultado es 1, de lo contrario podemos dividir más. Vamos a resolver el problema más simple de [matemáticas] x ^ {n-1} [/ matemáticas]. entonces todo lo que tenemos que hacer es multiplicarlo por x. Podemos escribir eso así:
def positivo Potencia (x, n):
si n == 0:
volver 1
más
retorno positivo Potencia (x, n-1) * x
Todavía estamos por resolver el poder negativo, sabemos que
[matemáticas] x ^ {- n} = \ frac {1} {x ^ n} [/ matemáticas]
resolver [matemáticas] x ^ n [/ matemáticas] es un problema más simple que ya hemos resuelto, así que:
def negativo Potencia (x, n):
return 1 / positivePower (x, -n)
Solución 2
La primera solución es fácil de entender, pero no la más eficiente.
Una propiedad interesante es que [math] x ^ n = x ^ {n / 2} \ times x ^ {n / 2} [/ math]. Podemos dividir esto en problemas más fáciles si consideramos el caso donde n es impar yn es incluso por separado:
[matemáticas] x ^ n = \ begin {cases} x ^ {n / 2} \ times x ^ {n / 2} & \ text {si n es par} \\ x ^ {floor (n / 2)} \ veces x ^ {floor (n / 2)} \ veces x & \ text {si n es impar} \ end {cases} [/ math]
resolver [matemáticas] x ^ {n / 2} [/ matemáticas] es mucho más fácil que resolver [matemáticas] x ^ n [/ matemáticas], así que una vez más estamos usando la estrategia de dividir y conquistar. El algoritmo para potencias positivas es:
def positivo Potencia (x, n):
si n == 0:
volver 1
tmp = positivePower (x, n // 2)
si n% 2 == 0:
volver tmp * tmp
más
volver tmp * tmp * x
