Come aumentare l'efficienza dell'algoritmo di ricorsione?
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
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 if
essendo espliciti sul nostro intento.
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:
- Se
n == 0
- Se 8 è nella cifra delle unità (
n % 10 == 8
) - 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 count8
nuovo con n / 10
il 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 count8
chiamata.
- 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 / 10
dopo aver "rimosso" gli 8 consecutivi.
If n % 10 != 8
, allora chiamiamo semplicemente count8
with n / 10
come 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.