Comment augmenter l'efficacité de l'algorithme de récursivité?

Question

La question est:

Étant donné un int n non négatif, calculez récursivement (sans boucle) le nombre d'occurrences de 8 comme un chiffre, sauf qu'un 8 avec un autre 8 immédiatement à sa gauche compte le double, donc 8818 donne 4. Notez que mod (%) par 10 donne le chiffre le plus à droite (126% 10 est 6), tandis que diviser (/) par 10 supprime le chiffre le plus à droite (126/10 est 12).

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

Ma solution ressemblait à ceci:

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;
}

Existe-t-il un moyen de supprimer les conditions multiples et de le rendre plus propre et plus efficace?

Answer 1

Noms de variables. Nommez vos variables d'après ce qu'elles font, sans exception.

---

En passant, notez que vous comptez sur le fonctionnement de la division entière en Java.

---

Cela dit, vous pouvez améliorer le code en étant explicite.

// 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);
}

Comme vous pouvez le voir, nous pouvons complètement nous débarrasser de l'imbrication ifen étant explicite sur notre intention.

Answer 2

Lorsqu'il s'agit de récursivité, il est important de noter ce que sont vos cas de base et récursifs et de partir de là. Ces différents cas deviendront essentiellement la structure de votre fonction.

Vous avez déjà identifié les différents cas de votre problème:

1. Si n == 0
2. Si 8 est à la place des chiffres ( n % 10 == 8)
3. Si 8 n'est pas à la place des chiffres ( n % 10 != 8)

Si n == 0, alors nous retournons simplement 0.

Si n % 10 == 8, alors nous savons que nous avons un 8, mais nous devons appeler à count8nouveau avec n / 10comme paramètre d'entrée à count8. Au retour de cet appel, nous ajoutons 1 à notre résultat avant de le renvoyer puisque nous en avions déjà trouvé un 8. Maintenant, ajoutez 1 (le 8 que nous avons déjà trouvé) au résultat de l' count8appel.

• Dans ce cas, vous voudrez vérifier si le chiffre suivant est également un 8. Si c'est le cas, vous souhaiterez incrémenter votre résultat de 1 avant de revenir. Vous pouvez le faire avant ou après le premier appel récursif. Assurez-vous simplement de passer n / 10après avoir "supprimé" les 8 dos à dos.

Si n % 10 != 8, alors nous appelons simplement count8avec n / 10comme paramètre d'entrée et renvoyons le résultat de cet appel.

J'espère que cela donne une idée de la manière dont vous pouvez structurer votre fonction de manière plus claire.