Exercice caml complexité

Bonjour, je vous écris pour avoir un peu d'aide je débute en caml et j'ai un exercice à faire je ne comprend pas trop comment le faire et j'aimerai avoir des explication précises pour bien comprendre merci de me répondre. Mon sujet et le suivant :

soit l'algorithme Descente(a,l,m), ou : l est une liste dont les elements appartiennent a un ensemble totalement ordonné, l'élément a est de même type que les éléments de l, m est un entier, et où le symbole :: désigne l'opérateur de construction de listes :

Descente(a,l,m)
Soit n = longeur(l);
Si m >=n alors le résultat retourné est la liste a::l
Sinon Si l est vide alors le résultat retourné est la liste [a]
Sinon poser l=b::q; (*b est la tete de l et q sa queue*)
Si a >b alors le résultat est la liste b :: Descente(a,q,m+1)
Sinon le résultat est a::Descente(b,q,m+1)

on me demande de dérouler Descente(7,[5;4;6;8;3;9],1).
on me demande ensuite de traduire cet algorithme dans un language de programmation approprié et l'exécuter sur quesleques exemples de données.

voila merci de me répondre

Qu'est-ce que tu as fait pour l'instant, où en es-tu, et quel est ton problème pour continuer ? Qu'est-ce qui te bloque ou que tu ne comprends pas ?

Pour l'instant j'ai cela mais çà ne marche pas :

Code:

---

1 2 3 4 5

let rec descente a l m n=if m>= n then a::l else if l = [] then [a] else let b = hd[l] in let q = tl[l] in if a > b then b::descente a q (m+1) n else a::descente b q (m+1) n;;

---

merci de m'aider

Bonsoir,

Tu y es presque. Dans ton code, l est déjà une liste, de sorte que [l] serait une liste de liste. L'erreur se trouve avec hd et tl. De plus, pour savoir si une liste est vide ou comporte au moins un élément, tu peux utiliser un filtrage match l with qui fait tout le travail pour toi :

Code:

---

1 2 3 4 5 6

let rec descente a l m n= if m >= n then a :: l else match l with | [] -> [a] | b :: q -> if a > b then b :: descente a q (m + 1) n else a :: descente b q (m + 1) n

---

Essaie d'abord de voir si tu comprends bien tout ce code, puis montre-nous ce que tu as fait pour la suite (déroulement de l'exécution, etc.).

Cordialement,
Cacophrène