Menu

Problème exercice récursivité Listes/Arbres [Résolu]

ismonhf 4 Messages postés vendredi 19 août 2011Date d'inscription 6 janvier 2018 Dernière intervention - 5 janv. 2018 à 19:41 - Dernière réponse : ismonhf 4 Messages postés vendredi 19 août 2011Date d'inscription 6 janvier 2018 Dernière intervention
- 6 janv. 2018 à 18:20
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...

Afficher la suite 

Votre réponse

3 réponses

KX 15557 Messages postés samedi 31 mai 2008Date d'inscriptionModérateurStatut 18 juin 2018 Dernière intervention - 6 janv. 2018 à 01:44
0
Merci
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.

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 4 Messages postés vendredi 19 août 2011Date d'inscription 6 janvier 2018 Dernière intervention - 6 janv. 2018 à 02:17
Merci KX, franchement j'ai galéré dessus toute la journée. Merci beaucoup.
ismonhf 4 Messages postés vendredi 19 août 2011Date d'inscription 6 janvier 2018 Dernière intervention - 6 janv. 2018 à 18:20
Commenter la réponse de KX