Qual è la strategia di divisione e conquista? Scrivi un algoritmo per trovare x all’ennesima potenza usando il metodo divide and conquer.

Se si desidera risolvere un problema difficile, la strategia di divisione e conquista significa che lo si scompone in piccoli problemi più facili da risolvere e si usano quegli algoritmi per risolvere il tuo problema difficile.

Soluzione 1

Diciamo che vuoi risolvere [matematica] x ^ n [/ matematica]. Per motivi di semplicità, supponiamo che n sia un numero intero. n potrebbe essere positivo o negativo, quindi dividiamo il nostro problema in 2 problemi, uno per i valori positivi e uno per i valori negativi

def power (x, n):
se n> = 0:
ritorno positivo Potenza (x, n)
altro:
restituisce negativo Potenza (x, n)

Lì, abbiamo fatto il primo passo nella nostra strategia di divisione e conquista. Ora abbiamo 2 problemi più semplici da risolvere. Concentriamoci prima sul problema del potere positivo.

Come risolviamo [matematica] x ^ n [/ matematica] per [matematica] n [/ matematica] positivo? se [matematica] n = 0 [/ matematica], il risultato è 1, altrimenti possiamo dividere ulteriormente. Risolviamo il problema più semplice di [matematica] x ^ {n-1} [/ matematica]. allora tutto ciò che dobbiamo fare è moltiplicarlo per x. Possiamo scrivere così:

def positivePower (x, n):
se n == 0:
ritorno 1
altro
ritorno positivo Potenza (x, n-1) * x

Dobbiamo ancora risolvere il potere negativo, lo sappiamo

[matematica] x ^ {- n} = \ frac {1} {x ^ n} [/ math]

risolvere [matematica] x ^ n [/ matematica] è un problema più semplice che abbiamo già risolto, quindi:

def negativePower (x, n):
restituisce 1 / positivo Potenza (x, -n)

Soluzione 2

La prima soluzione è facile da capire, ma non la più efficiente.

Una proprietà interessante è che [matematica] x ^ n = x ^ {n / 2} \ times x ^ {n / 2} [/ math]. Possiamo dividerlo in problemi più semplici se consideriamo il caso in cui n è dispari e n è anche separatamente:

[matematica] x ^ n = \ begin {casi} x ^ {n / 2} \ times x ^ {n / 2} & \ text {se n è pari} \\ x ^ {piano (n / 2)} \ times x ^ {floor (n / 2)} \ times x & \ text {se n è dispari} \ end {casi} [/ math]

risolvere [matematica] x ^ {n / 2} [/ matematica] è molto più facile che risolvere [matematica] x ^ n [/ matematica], quindi ancora una volta stiamo usando la strategia di divisione e conquista. L’algoritmo per i poteri positivi è:

def positivePower (x, n):
se n == 0:
ritorno 1
tmp = positivePower (x, n // 2)

se n% 2 == 0:
ritorna tmp * tmp
altro
ritorna tmp * tmp * x