Obtenir le second minimum...
Résolu
bilao
Messages postés
71
Date d'inscription
Statut
Membre
Dernière intervention
-
KX Messages postés 16761 Date d'inscription Statut Modérateur Dernière intervention -
KX Messages postés 16761 Date d'inscription Statut Modérateur Dernière intervention -
Bonsoir tous les commentçamarchiens,
Je cherche à programmer un fonction (en caml) qui à partir d'une liste fournit le deuxième plus petit élément de la liste. Je sens que ça doit être bête, mais je bloque....
Quelqu'un pourrait-il me donner des pistes dans n'importe quel language que ce soit (l'important c'est l'idée) ?
Merci d'avance
Je cherche à programmer un fonction (en caml) qui à partir d'une liste fournit le deuxième plus petit élément de la liste. Je sens que ça doit être bête, mais je bloque....
Quelqu'un pourrait-il me donner des pistes dans n'importe quel language que ce soit (l'important c'est l'idée) ?
Merci d'avance
A voir également:
- Obtenir le second minimum...
- Obtenir windows 10 gratuitement - Accueil - Mise à jour
- Second écran - Guide
- Comment obtenir du jaune ✓ - Forum Loisirs / Divertissements
- Le montant minimum de retrait autorisé sur le compte émetteur n'est pas atteint ✓ - Forum Vos droits sur internet
- Cliquez sur ce lien. en n'utilisant que le clavier, quel mot obtenez-vous ? ✓ - Forum souris / Touchpad
5 réponses
Bonjour
Tu utilises deux variables pour mémoriser les deux plus petits éléments.
soit m0 pour la + petite et m1 pour la seconde plus petite
Tu initialises avec les deux premiers éléments du tableau, avec la plus petite des deux dans m0
Tu balayes le tableau :
Si l'élément courant est > m1, tu l'oublies
S'il est compris entre m1 et m0, tu le mets dans m1
S'il est plus petit que m0, tu commences par recopier m0 dans m1 puis tu mets la valeur trouvée dans m0
À la fin, ton résultat est dans m1
Bref, c'est comme pour chercher la plus petite, sauf que tu mémorises les deux plus petites (et pas seulement la seconde plus petite !)
Tu utilises deux variables pour mémoriser les deux plus petits éléments.
soit m0 pour la + petite et m1 pour la seconde plus petite
Tu initialises avec les deux premiers éléments du tableau, avec la plus petite des deux dans m0
Tu balayes le tableau :
Si l'élément courant est > m1, tu l'oublies
S'il est compris entre m1 et m0, tu le mets dans m1
S'il est plus petit que m0, tu commences par recopier m0 dans m1 puis tu mets la valeur trouvée dans m0
À la fin, ton résultat est dans m1
Bref, c'est comme pour chercher la plus petite, sauf que tu mémorises les deux plus petites (et pas seulement la seconde plus petite !)
J'ai pigé vos réponses merci. Pourtant l'itératif sur camL avec les listes est délicat. J'étais donc parti sur un programme récursif, mais ça n'empêche pas de m'inspirer de ce que j'ai vu.
Si vous avez aussi des suggestions récursives (en français pas en langage info histoire que je bosse un peu quand même) ce serait sympa !
Merci
Si vous avez aussi des suggestions récursives (en français pas en langage info histoire que je bosse un peu quand même) ce serait sympa !
Merci
Au final, j'ai utilisé une fonction auxiliaire (min_et_reste) qui fournit le minimum de la liste et la liste privée de ce minimum. J'ai tire ma fonction second_min que voici (si jamais quelqu'un se posait la même question...)
let rec min_et_reste liste = match liste with
| [] -> failwith"liste vide"
| [a] -> a,[]
| a::q -> let c,d = min_et_reste q in
if a<c then a,c::d else c,a::d;;
let second_min liste =
let c,d = min_et_reste liste in
let e,f = min_et_reste d in
e ;;
Merci et @+
let rec min_et_reste liste = match liste with
| [] -> failwith"liste vide"
| [a] -> a,[]
| a::q -> let c,d = min_et_reste q in
if a<c then a,c::d else c,a::d;;
let second_min liste =
let c,d = min_et_reste liste in
let e,f = min_et_reste d in
e ;;
Merci et @+
Vous n’avez pas trouvé la réponse que vous recherchez ?
Posez votre question
Ta solution me paraît un peu lourde bilao (d'un point de vue efficacité) car elle parcourt une liste, en créé une deuxième et la parcours aussi...
Voici une solution alternative (il faudra peut-être remplacé les < par des <= )
On considère que x est le premier minimum et y le deuxième :
Voici une solution alternative (il faudra peut-être remplacé les < par des <= )
On considère que x est le premier minimum et y le deuxième :
let rec recherche x y l= match l with |[]-> y |t::q-> if t<x then recherche t x q else if t<y then recherche x t q else recherche x y q;; let second_minimum l= match l with |a::b::q -> if a<b then recherche a b q else recherche b a q |_-> failwith "liste trop petite";;