Problème exercice récursivité Listes/Arbres
Résolu
ismonhf
Messages postés
8
Statut
Membre
-
ismonhf Messages postés 8 Statut Membre -
ismonhf Messages postés 8 Statut Membre -
Bonjour j'ai un exercice qui est tombé au contrôle de l'année dernière en programmation Java, et j'ai essayé toute la journée de trouver la solution, mais je n'ai pas réussi. Voila l'énoncé, j'aimerai bien avoir de l'aide pour le résoudre, svp. Pour l'instant je suis seulement sûr que si on fait (pos=0) : res=lv.size() et if(lv.get(pos)=null) res=1. Voila...
A voir également:
- Problème exercice récursivité Listes/Arbres
- Listes déroulantes excel - Guide
- Listes déroulantes en cascade excel - Guide
- Problème liste de diffusion whatsapp - Guide
- Transmath 3eme exercice - Forum Loisirs / Divertissements
- Fleur d'encre 5eme corrigé exercice ✓ - Forum PDF
1 réponse
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;
}
}
}
ismonhf
Messages postés
8
Statut
Membre
Merci KX, franchement j'ai galéré dessus toute la journée. Merci beaucoup.
ismonhf
Messages postés
8
Statut
Membre
J'ai lancé ce forum aussi, si jamais tu y arrives aussi. https://forums.commentcamarche.net/forum/affich-35118973-methodes-arbres-gauches-arbres-droits-listes-prefixe-arbres-bin?6jd4LqME86L91Bpz_5od81ajvJ3aGiIM3FlhcqSjZoQ#top
