Discussion :

[chikita]

Bonjour a tous,

j'ai un soucis dans ma fonction maximum. Le prof nous a imposé de la faire de façon récursive. Quand je compile, j'ai seulement les deux premiers qui sont bien passé dans ma condition mais je n'arrive pas a accéder à la cellule suivante. J'ai du mal sur les fonctions récursive. Est-ce que quelqu'un pourrait m'aider à y voir plus clair.

voici mon code :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
 
 
public class Cellule {
	int valeur;
	Cellule suivant;
 
	Cellule(int pvaleur) {
		valeur = pvaleur;
		suivant = null;
	}
 
}
 
import java.util.Random;
 
public class ListeChainee {
	Cellule tete;
 
	ListeChainee() {
		tete = null;
	}
 
	public void Afficher() {
		Cellule c = tete;
		while (c != null) {
			System.out.print(c.valeur + " ");
			c = c.suivant;
		}
	}
 
	public void Ajouter(int valeur) {
		Cellule nc = new Cellule(valeur);
 
		nc.suivant = tete;
		tete = nc;
	}
 
	public void Init(int n) {
		Random rand = new Random();
		for (int i = 0; i < n; i++) {
			this.Ajouter(rand.nextInt(1000));
 
 
		}
	}
 
	public int Minimum() {
		int valMin = 10000;
		Cellule c = tete;
		while (c != null) {
 
			if (c.valeur < valMin) { 										
				valMin = c.valeur;
 
			}
			c = c.suivant;
		}
 
		System.out.print(" la valeur minimum est : " + valMin);
 
		return valMin;
	}
 
	static int Maximum(Cellule c) {
		int max = c.valeur;
		if (c != null) {
			if (c.valeur < c.suivant.valeur) {
				max = c.suivant.valeur;
				max = ListeChainee.Maximum(c.suivant);
			}
		}
		return max;
	}
 
	void Supprimer(int n) {
		ListeChainee l = new ListeChainee();
		Cellule c = tete;
		while (c != null) {
			if (c.valeur != n) {
 
				l.Ajouter(c.valeur);
			}
			c = c.suivant;// on passe à la cellule suivante
		}
 
		System.out.println(" La nouvelle liste est : ");
 
		l.Afficher();
 
	}
}
import java.util.Scanner;
 
 
public class test {
 
 
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		System.out.print(" Début liste chainée : ");
	ListeChainee l1 = new ListeChainee();
	l1.Init(10);
	l1.Afficher();
	l1.Minimum();
	Cellule c2=new Cellule (0);
	c2. suivant=l1.tete;
	l1.tete = c2;
	 System.out.println(" le chiffre maximum de la liste est : " + 
	ListeChainee.Maximum(c2)); 
       System.out.print(" Deuxième liste chainée : ");
	ListeChainee l2 = new ListeChainee ();
	for (int i = 0; i < 10; i++) {
		l2.Ajouter(i);
	}
	l2.Afficher();
	l2.Supprimer(2);
	}
 
}

[jeffray03]

salut
voici le code de maximum:

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public static int Maximum(Cellule c) {
		int max = c.valeur;
		while (c != null) {
			 
			if (c.valeur > max) { 										
				max = c.valeur;
 
			}
			c = c.suivant;
		}
 
		System.out.print(" la valeur Maximun est : " + max);
 
		return max;
	}

Eric

[chikita]

merci mais la méthode doit impérativement être récursive

[joel.drigo]

Salut,

En gros, le max d'une liste, c'est le max entre le premier et le max du reste de la liste, et comme le max du reste de la liste, c'est le max entre premier du reste de la liste, et le max entre ce qu'il y ensuite... etc...

Pour l'écrire de façon récursive, il suffit de prendre pour forme générale :

Code :

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

1
2
3
max( cellule ) 
si suivante de cellule existe ,  return la cellule avec la plus grande valeur entre cellule et max ( de sa suivante )
sinon return cellule

autrement dit, en Java, par exemple :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public Cellule max(Cellule cellule) {
   if ( cellule.suivante!=null ) {
 
      Cellule celluleMax = max( cellule.suivante );
 
      if( celluleMax.value>cellule.value ) {
         return celluleMax;
      }
      else {
         return cellule;
      }
 
   }
   else {
       return cellule;
   }
}

qu'on peut simplifier en (en perdant un peu de sémantique) :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
public Cellule max(Cellule cellule) {
   if ( cellule.suivante!=null ) {
 
      Cellule celluleMax = max( cellule.suivante );
 
      if( celluleMax.value>cellule.value ) {
         return celluleMax;
      }
 
   }
   return cellule;
}

[jeffray03]

ou encore:

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
 
public static int maximumRecursive(Cellule c, Integer max, boolean debut) {
 
		if(c != null)
		{
		  if(debut) 
		  {
			  max = c.valeur;
			 return maximumRecursive(c, max, false);
		  }
		  else
		  {
			  if(c.suivant != null)
			  {
				  if (c.suivant.valeur > max) { 										
						max = c.suivant.valeur;
					}
				  return maximumRecursive(c.suivant, max, false);  
			  }
			  else
				  return max;
		  }
 
		}
		else
		{
		return max;
		}
	}

et dans la main:

Code :

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

1
2
 
max =  ListeChainee.maximumRecursive(c2, -1, true);

[thelvin]

Ouaip enfin le principe du récursif, au départ, c'est qu'on n'a pas besoin de tous ces paramètres.
Coller au plus proche de la définition récursive mathématique.

[jeffray03]

Oui je comprend.

Eric