Funzione di alimentazione con ricorsione

Question

Devo scrivere un metodo di alimentazione in Java. Riceve due int inte e non importa se sono numeri positivi o negativi. Dovrebbe avere la complessità di O(logN). Deve anche usare la ricorsione. Il mio codice corrente ottiene due numeri, ma il risultato che continuo a produrre è zero e non riesco a capire perché.

import java.util.Scanner; 

public class Powers { 

    public static void main(String[] args) { 
     float a; 
     float n; 
     float res; 

     Scanner in = new Scanner(System.in); 
     System.out.print("Enter int a "); 
     a = in.nextFloat(); 

     System.out.print("Enter int n "); 
     n = in.nextFloat(); 

     res = powers.pow(a, n); 

     System.out.print(res); 
    } 

    public static float pow(float a, float n) { 
     float result = 0; 

     if (n == 0) { 
      return 1; 
     } else if (n < 0) { 
      result = result * pow(a, n + 1); 
     } else if (n > 0) { 
      result = result * pow(a, n - 1); 
     } 

     return result; 
    } 
} 

Answer 1

Cominciamo con alcuni fatti di matematica:

• Per un n positiva, aⁿ = a⨯a⨯ ... ⨯an volte
• Per un n negativo, aⁿ = ⅟a⁻ⁿ = ⅟ (a⨯a⨯ ... ⨯a). Ciò significa che a non può essere zero.
• Per n = 0, aⁿ = 1, anche se a è zero o negativo.

Quindi partiamo dal caso positivo n e lavoriamo da lì.

Dal momento che vogliamo che la nostra soluzione sia ricorsiva, dobbiamo trovare un modo per definire aⁿ basato su un n più piccolo, e lavorare da lì. Il modo abituale in cui le persone pensano alla ricorsione è cercare di trovare una soluzione per n-1 e lavorare da lì.

E in effetti, dal momento che è matematicamente vero che aⁿ = a⨯ (aⁿ⁻¹), l'approccio ingenuo sarebbe molto simile a quello che si è creato:

public static int pow(int a, int n) { 
    if (n == 0) { 
     return 1; 
    } 
    return (a * pow(a,n-1)); 
} 

Tuttavia, la complessità di questo è O (n). Perché? Perché per n = 0 non fa alcuna moltiplicazione. Per n = 1, fa una moltiplicazione. Per n = 2, chiama pow (a, 1) che sappiamo essere una moltiplicazione, e moltiplica una volta, quindi abbiamo due moltiplicazioni. C'è una moltiplicazione in ogni passo di ricorsione, e ci sono n passi. Quindi è O (n).

Per rendere questo O (log n), è necessario applicare ogni passaggio a una frazione di n anziché solo a n-1. Anche in questo caso, esiste un fatto matematico che può aiutarci: a ^{n₁ + n₂} = a ^n₁ ⨯a ^n₂.

Questo significa che siamo in grado di calcolare aⁿ come ^n/2 ⨯a ^n/2.

Ma cosa succede se n è dispari? qualcosa come a⁹ sarà un ^4.5 ⨯a ^4.5. Ma stiamo parlando di poteri interi qui. Gestire le frazioni è una cosa completamente diversa. Fortunatamente, possiamo solo formularlo come a⨯a⁴⨯a⁴.

Così, per un numero pari utilizzare un ^n/2 ⨯a ^n/2, e per un numero dispari, utilizzare un a⨯ ^n/2 ⨯a ^n/2 (divisione intera , dandoci 9/2 = 4).

public static int pow(int a, int n) { 
    if (n == 0) { 
     return 1; 
    } 
    if (n % 2 == 1) { 
     // Odd n 
     return a * pow(a, n/2) * pow(a, n/2); 
    } else { 
     // Even n 
     return pow(a, n/2) * pow(a, n/2); 
    } 
} 

Questo effettivamente ci dà i risultati giusti (per un positivo n, cioè). Ma in effetti, la complessità qui è, di nuovo, O (n) piuttosto che O (log n). Perché? Perché stiamo calcolando i poteri due volte.Significa che in realtà lo chiamiamo 4 volte al livello successivo, 8 volte al livello successivo e così via. Il numero di passaggi di ricorsione è esponenziale, quindi questo si annulla con il presunto risparmio che abbiamo fatto dividendo n per due.

Ma in realtà, è necessario solo una piccola correzione:

public static int pow(int a, int n) { 
    if (n == 0) { 
     return 1; 
    } 
    int powerOfHalfN = pow(a, n/2); 
    if (n % 2 == 1) { 
     // Odd n 
     return a * powerOfHalfN * powerOfHalfN; 
    } else { 
     // Even n 
     return powerOfHalfN * powerOfHalfN; 
    } 
} 

In questa versione, ci chiedono il ricorsione solo una volta. Quindi otteniamo, diciamo, una potenza di 64, molto rapidamente attraverso 32, 16, 8, 4, 2, 1 e fatto. Solo una o due moltiplicazioni per ogni passaggio e ci sono solo sei passaggi. Questo è O (log n).

La conclusione di tutto questo è:

1. per ottenere un O (log n), abbiamo bisogno di ricorsione che funziona su una frazione di n ad ogni passo, piuttosto che solo n - 1 o n - qualsiasi cosa.
2. Ma la frazione è solo una parte della storia. Dobbiamo stare attenti a non chiamare la ricorsione più di una volta, perché l'utilizzo di più chiamate ricorsive in una fase crea complessità esponenziale che si annulla con l'utilizzo di una frazione di n.

Infine, siamo pronti a occuparci dei numeri negativi. Dobbiamo semplicemente ottenere il reciproco ⅟a⁻ⁿ. Ci sono due cose importanti da notare:

• Non consentire la divisione per zero. Cioè, se hai ottenuto un = 0, non dovresti eseguire il calcolo. In Java, gettiamo un'eccezione in questo caso. L'eccezione ready-made più appropriata è IllegalArgumentException. È una RuntimeException, quindi non è necessario aggiungere una clausola throws al metodo. Sarebbe positivo se tu lo prendessi o impedissi che si verificasse una situazione del genere, nel tuo metodo main quando leggi gli argomenti.
• Non è più possibile restituire un numero intero (in realtà, avremmo dovuto utilizzare long perché eseguiamo un overflow di numeri interi per potenze piuttosto basse con int), perché il risultato potrebbe essere frazionario.

Quindi definiamo il metodo in modo che ritorni doppio. Il che significa che dobbiamo anche correggere il tipo di powerOfHalfN. Ed ecco il risultato:

public static double pow(int a, int n) { 
    if (n == 0) { 
     return 1.0; 
    } 
    if (n < 0) { 
     // Negative power. 
     if (a == 0) { 
      throw new IllegalArgumentException(
        "It's impossible to raise 0 to the power of a negative number"); 
     } 
     return 1/pow(a, -n); 
    } else { 
     // Positive power 

     double powerOfHalfN = pow(a, n/2); 
     if (n % 2 == 1) { 
      // Odd n 
      return a * powerOfHalfN * powerOfHalfN; 
     } else { 
      // Even n 
      return powerOfHalfN * powerOfHalfN; 
     } 
    } 
} 

nota che la parte che gestisce a n negativo viene utilizzato solo nel livello superiore della ricorsione. Una volta che chiamiamo pow() in modo ricorsivo, è sempre con numeri positivi e il segno non cambia finché non raggiunge 0.

Questa dovrebbe essere una soluzione adeguata al tuo esercizio. Tuttavia, personalmente non mi piace il if lì alla fine, quindi ecco un'altra versione. Puoi dire perché questo sta facendo lo stesso?

public static double pow(int a, int n) { 
    if (n == 0) { 
     return 1.0; 
    } 
    if (n < 0) { 
     // Negative power. 
     if (a == 0) { 
      throw new IllegalArgumentException(
        "It's impossible to raise 0 to the power of a negative number"); 
     } 
     return 1/pow(a, -n); 
    } else { 
     // Positive power 
     double powerOfHalfN = pow(a, n/2); 
     double[] factor = { 1, a }; 
     return factor[n % 2] * powerOfHalfN * powerOfHalfN; 
    } 
} 

Answer 2

prestare attenzione a:

float result = 0; 

e

result = result * pow(a, n+1); 

è per questo che hai un risultato pari a zero. E invece si suggerisce di lavorare in questo modo:

result = a * pow(a, n+1); 

Answer 3

Oltre l'errore di inizializzazione result-0, ci sono alcune altre questioni:

1. il calcolo per il negativo n è sbagliato. Ricorda che a^n == 1/(a^(-n)).
2. Se n non è intero, il calcolo è molto più complicato e non lo si supporta. Non sarò sorpreso se non sei tenuto a supportarlo.
3. Per ottenere prestazioni O(log n), è necessario utilizzare una strategia di divisione e conquista. Ad esempio a^n == a^(n/2)*a^(n/2).

Answer 4

Una buona regola è di allontanarsi dalla tastiera fino a quando l'algoritmo non è pronto. Quello che hai fatto è ovviamente O (n).

Come suggerito Eran, per ottenere una complessità di O (log (n)), è necessario dividere n per 2 ad ogni iterazione.

condizioni finali:

• n == 0 => 1
• n == 1 => una

Caso particolare:

• n < 0 => 1./pow (a, -n) // nota il 1. per ottenere un doppio ...

normale caso:

• m = n/2
• risultato = pow (a, n)
• risultato = Resul * Resul // evitare calcolare due volte
• se n è dispari (n% 2!= 0) => Resul * = un

Questo algoritmo è in O (log (n)) - E 'a voi di scrivere codice Java corretto da esso

Ma, come v'è stato detto: n deve essere un numero intero (negativo di ok positivo, ma intero)

Answer 5

Ecco un modo molto meno confuso di farlo, almeno se non siete preoccupati per le moltiplicazioni extra. :

public static double pow(int base,int exponent) { 
     if (exponent == 0) { 
      return 1; 
     } 
     if (exponent < 0) { 
      return 1/pow(base, -exponent); 
     } 
     else { 
      double results = base * pow(base, exponent - 1); 
      return results; 
     } 
    }