Discussion :

[reuqnas]

Bonjour,
aujourd'hui

[prgasp77]

Bonjour,
le problème ne semble pas lié au langage mais à l'algorithmie qui se cache derrière.

La fonction peut être implémentée en quelques lignes seulement (3-4), grâce à notre amie récursivité. Je te conseille de faire l'exercice sur papier dans un premier temps : inscris-y une suite de nombre, et extrait-en le plus petit comme le ferait un programme. Essais ensuite d'en tirer un algo correct.

N'hésite pas à poser tes questions petit à petit.
Cdlt,

[prgasp77]

Et comment as-tu défini

Code :

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

it_list

[ManusDei]

C'est normal, ton cas d'arrêt est sur la ligne [l] -> l

Donc forcément, il va t'afficher ce que renvoie cette ligne, c'est à dire l, donc là 2.
Tu dois modifier ce passage pour qu'il affiche l et la liste complète (donc il la faut en paramètre quelque part).

D'ailleurs ton code me semble bizarre, tu as un cas d'arrêt dans l'autre membre.

[ManusDei]

Tu pourrais sinon faire quelque chose de différent, qui me semble plus clair vis-à-vis de l'algorithme utilisé.

Code :

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

1
2
3
4
5
6
let min_reste = fun l ->
  let rec aux = fun list min -> match list with 
              [] -> failwith "erreur"
            |[a] -> if a < min then (a,l) else (min,l)
            |(a::r) -> if a< min then (aux r a) else (aux r min)
in aux l max_int;;

En fait là tu as min_reste qui ne sert qu'à paramétrer aux (fonction auxiliaire), qui elle va faire tout le travail.
aux a deux paramètres, la liste restant à parcourir, et le minimum pour l'instant.
Tu regardes si ta tête de liste est inférieure au minimum, si oui on remplace, si non on continue sur la suite de la liste.
Et à la fin tu renvoie ton résultat, et la liste de départ (attention aux noms).

Il reste peut-être des erreurs dans mon code, je ne l'ai pas testé.


Edit : qu'est-ce que tu appelles le nombre de comparaisons ?

[gasche]

ManusDei > ton algorithme est faux, on ne veut pas renvoyer la liste entière (ce qui n'aurait aucun intérêt), mais la liste *des éléments restants*, c'est à dire la liste privée de son élément le plus petit.

reuqnas > en partant de ton code :

Code :

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

1
2
3
4
5
6
7
8
 
let rec min_reste = function
  | [] -> failwith "pas de minimum"
  | [l] -> l
  | (l::q) ->
    let mini_q = min_reste q in
    if l <= mini_q then l
    else mini_q ;;

Il faut modifier les valeurs de retour, comme tu l'as dit, pour avoir la "liste des éléments restant" dans un couple. Il faut le faire pour le deuxième et le troisième cas (le premier cas reste un cas d'erreur). Pour le deuxième cas, c'est facile :

Code :

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

| [l] -> (l, [])

Si la liste contient un seul élément, c'est le minimum et la "liste des éléments restants" est vide, donc on renvoie []. Peux-tu essayer de faire le cas (l::q) ? C'est le plus difficile. Ça commence comme ça :

Code :

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

1
2
let (mini_q, liste_q) = min_reste q in
if l <= mini_q then ... else ...

PS : on peut écrire ces algorithmes de façon encore plus élégante (mais légèrement moins efficace) en utilisant les fonctions "min" et "max" déjà existantes, qui renvoient respectivement le plus petit et le plus grand de leurs deux paramètres. Par exemple pour renvoyer seulement le plus petit élément d'une liste :

Code :

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

1
2
3
4
let rec min_list = function
 | [] -> invalid_arg "min_list"
 | [x] -> x
 | hd::tl -> min hd (min_list tl)

(Encore plus court,

Code :

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

let min_list li = it_list min (hd li) (tl li)

)

Ceci dit, tu devrais commencer par chercher la version avec (if l <= mini_q) si c'est plus naturel pour toi)

[gasche]

Il y a d'autres façons de faire, mais tu peux continuer à utiliser la même approche :

Code :

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

| [l] -> (l, [], 0)

je te laisse faire le cas récursif :

Code :

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

let (mini_q, liste_q, nb_q) = ... in ...

[gasche]

Utilise la solution classique quand un programme ne marche pas : comprendre ce qu'il fait sur un petit exemple, en exécutant *toi-même*, à la main, le programme exactement comme il est codé. Quand tu auras fait l'effort de faire ça plusieurs fois, tu pourras le faire de tête, et tu seras un dieu du débogage.

Essaie d'appliquer cette fonction sur [1; 2; 3], en déroulant les appels toi-même, tu vas forcément comprendre le problème.

Je commence :

Code ocaml :

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

min_reste [1; 2; 3]

=> cas (l::q), avec l=1, q = [2; 3]

Code ocaml :

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

1
2
3
4
 
(* min_reste [1; 2;3] *)
let (mini_q, liste_q) = min_reste [2;3] in
if 1 <= mini_q then (1, liste_q) else (mini_q, 1::liste_q)

=> il faut dérouler l'appel `min_reste` [2;3]
=> cas (l::q) avec l=2, q=[3]

Code ocaml :

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

1
2
3
4
5
6
7
 
(* min_reste [1;2;3] *)
let (mini_q, liste_q) =
  (* appel récursif : min_reste [2;3] *)
  let (mini_q, liste_q) = min_reste [3] in
  if 2 <= mini_q then (2, liste_q) else (mini_q, 2::liste_q) in
if 1 <= mini_q then (1, liste_q) else (mini_q, 2::liste_q)

=> il faut dérouler l'appel min_reste [3]...

[gasche]

Tu dois renvoyer un couple. Donc ce n'est certainement pas [a,0], mais plutôt ([a], 0). Pareil dans le cas vide, tu ne dois pas renvoyer la liste vide, mais un couple. Pareil dans le cas d'une liste non vide, min_reste_compte renvoie un triplet, pas une liste, alors tu ne peux pas écrire (truc :: min_reste_comp ...).

Bref, branche ton cerveau !

(Par ailleurs à priori il n'y a pas besoin de faire un cas pour les listes à seulement un élément.)