Come aumentare l'efficienza dell'algoritmo di ricorsione?

Aug 22 2020

La domanda è:

Dato un int n non negativo, calcola ricorsivamente (senza cicli) il conteggio delle occorrenze di 8 come cifra, tranne per il fatto che un 8 con un altro 8 immediatamente alla sua sinistra conta il doppio, quindi 8818 restituisce 4. Nota che mod (%) per 10 restituisce la cifra più a destra (126% 10 è 6), mentre la divisione (/) per 10 rimuove la cifra più a destra (126/10 è 12).

count8 (8) → 1 count8 (818) → 2 count8 (8818) → 4

La mia soluzione era simile a questa:

public int count8(int n) {
  if(n == 0)  return 0;
  
  int faith = count8(n/10);
  int c = 0;
  if(n%10 == 8){
    n /= 10;
    if(n%10 == 8){
      c++;
    }
    c++;
  }
  return c + faith;
}

C'è un modo per rimuovere le condizioni if ​​multiple e renderlo più pulito ed efficiente?

Risposte

4 Bobby Aug 23 2020 at 06:53

Nomi variabili. Assegna un nome alle tue variabili dopo quello che fanno, senza eccezioni.


Come nota a margine, tieni presente che ti affidi a come funziona la divisione di interi in Java.


Detto questo, puoi migliorare il codice essendo esplicito.

// As I've said, always name your variables and functions after
// what they are doing. Don't be afraid to use longer names,
// longer names which tell you what the class does are a good
// thing, even if they sound "funny".
public int countEights(int value) {
    // Early exit conditions are a good thing.
    if(value == 0) {
        return 0;
    }
    
    // We could also skip the declaration and instead return
    // the right count together with the function call. From
    // the viewpoint of the JVM it doesn't make a difference,
    // but here in the code it means that we have the logic
    // for stripping the last digit only once.
    int countedEights = 0;
    
    // We are testing explicitly for the mentioned "double eights",
    // this has the upside that the intent is clearly visible
    // when reading the code.
    if ((value % 100) == 88) {
        countedEights = 2;
    } else if ((value % 10) == 8) {
        countedEights = 1;
    }
    
    // And finally we call the function again in the return
    // statement, as it is easier to follow the recursion when
    // it is being called at the end of the function.
    return countedEights + countEights(value / 10);
}

Come puoi vedere, possiamo sbarazzarci completamente dell'annidamento ifessendo espliciti sul nostro intento.

2 chromaticc Aug 22 2020 at 15:22

Quando si ha a che fare con la ricorsione, è importante annotare quali sono i casi di base e ricorsivi e partire da lì. Questi diversi casi diventeranno essenzialmente la struttura della tua funzione.

Hai già individuato i diversi casi per il tuo problema:

  1. Se n == 0
  2. Se 8 è nella cifra delle unità ( n % 10 == 8)
  3. Se 8 non è nella cifra delle unità ( n % 10 != 8)

Se n == 0, allora restituiamo solo 0.

Se n % 10 == 8, allora sappiamo di avere un 8, ma dobbiamo chiamare di count8nuovo con n / 10il nostro parametro di input a count8. Quando torniamo da questa chiamata, aggiungiamo 1 al nostro risultato prima di restituirlo poiché ne avevamo già trovato uno 8. Ora aggiungi 1 (l'8 che abbiamo già trovato) al risultato della count8chiamata.

  • In questo caso, vorrai controllare se anche la cifra successiva è un 8. Se lo è, allora vorrai incrementare il tuo risultato di 1 prima di tornare. Puoi farlo prima o dopo la prima chiamata ricorsiva. Assicurati solo di passare n / 10dopo aver "rimosso" gli 8 consecutivi.

If n % 10 != 8, allora chiamiamo semplicemente count8with n / 10come nostro parametro di input e restituiamo il risultato di questa chiamata.

Si spera che questo dipinga un quadro su come puoi strutturare la tua funzione in modo più chiaro.