Discussion :

[infoJava67]

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 trouvé la solution, mais je n'y 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...

[thelvin]

Hello,

donc c'est un exercice de récursivité.

Peux-tu nous parler de la méthode de conception de base d'un algo récursif ? En gros, qu'est-ce qu'on trouve toujours dans un algo récursif et donc, constitue le point de départ de sa conception ?

Du coup, le code que tu devras faire, doit avoir quelle forme au début, en commençant par ça ? Montre du pseudocode pour les parties qui manquent.

[infoJava67]

Merci mais c'est bon j'ai eu la bonne réponse :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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
}