Problème exercice récursivité Listes/Arbres
Résolu/Fermé
ismonhf
Messages postés
6
Date d'inscription
vendredi 19 août 2011
Statut
Membre
Dernière intervention
16 novembre 2021
-
Modifié le 5 janv. 2018 à 19:41
ismonhf Messages postés 6 Date d'inscription vendredi 19 août 2011 Statut Membre Dernière intervention 16 novembre 2021 - 6 janv. 2018 à 18:20
ismonhf Messages postés 6 Date d'inscription vendredi 19 août 2011 Statut Membre Dernière intervention 16 novembre 2021 - 6 janv. 2018 à 18:20
A voir également:
- Problème exercice récursivité Listes/Arbres
- Créer des listes déroulantes excel - Guide
- Excel listes déroulantes en cascade - Guide
- Comment trouver la correction d'un exercice - Forum Programmation
- Triangle des textures exercice corrigé - Forum Loisirs / Divertissements
- Exercice informatique cm2 pdf ✓ - Forum Études / Formation High-Tech
1 réponse
KX
Messages postés
16733
Date d'inscription
samedi 31 mai 2008
Statut
Modérateur
Dernière intervention
31 janvier 2024
3 015
6 janv. 2018 à 01:44
6 janv. 2018 à 01:44
Bonjour,
Puisque tu sais que lv.get(pos)=null donne res=1, il ne reste plus qu'à calculer le cas où ce n'est pas null.
C'est à dire qu'il y a un noeud (1) + récursivement la taille du sous arbre à gauche resG = f(pos+1) + récursivement la taille du sous arbre à droite resD = f(pos+1+resG), donc f(pos)=1+resG+resD.
Remarque : bien que récursif, cet algorithme est linéaire (on ne profite pas de la dichotomie par exemple), donc un algorithme itératif (linéaire également) serait un peu plus rapide (les appels récursifs ont un coût)
Or, on peut constater (et prouver par récurrence) qu'avec cette structure de liste, dans n'importe quelle représentation d'arbre ou de sous-arbre, il y aura toujours 1 case null de plus que le nombre de cases non null.
Donc la méthode nbPositions peut s'implémenter itérativement en parcourant les cases à partir de pos et en s'arrêtant lorsque l'on a compté 1 case null de plus que le nombre de cases non null.
Ou en simplifiant un peu :
Puisque tu sais que lv.get(pos)=null donne res=1, il ne reste plus qu'à calculer le cas où ce n'est pas null.
C'est à dire qu'il y a un noeud (1) + récursivement la taille du sous arbre à gauche resG = f(pos+1) + récursivement la taille du sous arbre à droite resD = f(pos+1+resG), donc f(pos)=1+resG+resD.
public static <T> int nbPositions(List<T> lv, int pos) {
if (lv.get(pos) == null)
return 1;
int gauche = nbPositions(lv, pos + 1);
int droite = nbPositions(lv, pos + gauche + 1);
return gauche + droite + 1;
}
public static void main(String args[]) {
List<Integer> lv = Arrays.asList(20, 18, 3, null, 14, 7, null, 10, null, null, null, null, 42, 26, null, 39, 30, null, 34, null, null, null, null);
System.out.println(nbPositions(lv, 12)); // 11
System.out.println(nbPositions(lv, 4)); // 7
System.out.println(nbPositions(lv, 7)); // 3
}
Remarque : bien que récursif, cet algorithme est linéaire (on ne profite pas de la dichotomie par exemple), donc un algorithme itératif (linéaire également) serait un peu plus rapide (les appels récursifs ont un coût)
Or, on peut constater (et prouver par récurrence) qu'avec cette structure de liste, dans n'importe quelle représentation d'arbre ou de sous-arbre, il y aura toujours 1 case null de plus que le nombre de cases non null.
Donc la méthode nbPositions peut s'implémenter itérativement en parcourant les cases à partir de pos et en s'arrêtant lorsque l'on a compté 1 case null de plus que le nombre de cases non null.
public static <T> int nbPositions(List<T> lv, int pos) {
for (int i = pos, nbNode = 0, nbNull = 0;; i++) {
if (lv.get(i) == null) {
nbNull++;
} else {
nbNode++;
}
if (nbNull == nbNode + 1) {
return nbNull + nbNode;
}
}
}
Ou en simplifiant un peu :
public static <T> int nbPositions(List<T> lv, int pos) {
for (int i = pos, nbDiff = 0;; i++) {
if (lv.get(i) == null) {
nbDiff++;
} else {
nbDiff--;
}
if (nbDiff == 1) {
return i - pos + 1;
}
}
}
6 janv. 2018 à 02:17
6 janv. 2018 à 18:20