Considérez ce problème:

Nous avons un triangle fait de blocs. La rangée supérieure a 1 bloc, la rangée suivante a 2 blocs, la rangée suivante a 3 blocs, et ainsi de suite. Calculez récursivement (sans boucles ni multiplication) le nombre total de blocs dans un tel triangle avec le nombre de lignes donné.

Mon approche de ce problème était la suivante

public int triangle(int rows) {
  if(rows == 0 || rows == 1 ) {
    return rows;
  } else {
    return triangle(rows-1) +2;
  }
}

Le programme fonctionne bien pour les valeurs jusqu'au nombre 3 mais les valeurs qui devraient sortir sont fausses (le calcul est faux / appel récursif). Qu'est-ce que je rate?

Merci d'avance!

1
codeisfun 23 sept. 2020 à 20:03

3 réponses

Meilleure réponse

Vous ajoutez 2 à votre appel récursif, essayez d'ajouter rows.

Exemple:

public int triangle(int rows) {
  if (rows < 2)
    return rows;
  else
    return triangle(rows - 1) + rows;
}
0
David 23 sept. 2020 à 17:24

Je l'écrirais comme:

public int triangle(int rows) {
    return (rows <= 0) ? 0 : rows + triangle(rows-1);
}
0
Idle_Mind 23 sept. 2020 à 17:45

Vous avez la bonne idée. Vous commencez à partir de la ligne "du bas" et dans chaque appel récursif, vous vous déplacez vers la ligne du dessus jusqu'à atteindre la ligne du haut, qui ne contient qu'un seul bloc. Votre seul problème est qu'au lieu d'ajouter 2, vous devez ajouter le nombre de lignes.
(Explications après le code.)

public int triangle(int rows) {
    if (rows < 1) {
        throw new IllegalArgumentException("'rows' must be positive.");
    }
    if (rows == 1) {
        return 1;
    }
    else {
        return rows + triangle(rows - 1);
    }
}

Prenons un exemple simple où vous appelez initialement la méthode triangle() avec une valeur de 4. Cela signifie que la ligne du bas contient quatre blocs et la ligne du dessus qui contient trois blocs. Donc, la dernière déclaration de retour dans le code ci-dessus signifie:
Renvoie le nombre de blocs dans ma ligne plus tous les blocs qui sont au-dessus de ma ligne dans le triangle.

Donc la méthode triangle() s'appelle elle-même avec la valeur 3. Encore une fois la même chose, retourne le nombre de blocs dans ma ligne plus tous les blocs qui sont au-dessus de ma ligne dans le triangle.

Finalement, vous arrivez à la ligne du haut où il n'y a qu'un seul bloc et aucune ligne au-dessus. Par conséquent, vous ne voulez pas faire un autre appel récursif, vous renvoyez donc simplement le nombre de blocs dans la ligne, qui est un.

Donc 1 est retourné à la méthode qui l'a appelé qui, à son tour, retourne son nombre de lignes, c'est-à-dire 2, plus le 1 que la méthode invoquée a renvoyé pour un total de trois et ainsi de suite, jusqu'à ce que vous reveniez à l'appel initial.

1
Abra 23 sept. 2020 à 17:35