Dm informatique Caml

Réponses à toutes vos questions après le Bac (Fac, Prépa, etc.)
Obito31
Membre Relatif
Messages: 106
Enregistré le: 27 Fév 2017, 02:34

Dm informatique Caml

par Obito31 » 02 Nov 2017, 14:54

Bonjour
Alors voilà je suis en 3em années d'informatique et J'ai un dm a rendre en caml mais je bloque sur une question. Ils veulent une fonction qui étant donné un ensemble, construit l'ensemble de tous ses sous-ensembles . Pourrais vous m'aider
Merci



Avatar de l’utilisateur
capitaine nuggets
Modérateur
Messages: 3910
Enregistré le: 14 Juil 2012, 00:57
Localisation: nulle part presque partout

Re: Dm informatique Caml

par capitaine nuggets » 02 Nov 2017, 17:46

Salut !

Mathématiquement, je prendrais un ensemble E et :
- je ferais la liste de toutes les parties de E qui contiennent 0 élément,
- je ferais la liste de toutes les parties de E qui contiennent 1 élément,
- je ferais la liste de toutes les parties de E qui contiennent 2 élément,
etc...

Après, je ne suis pas spécialiste en informatique et encore moins en camL.
- Merci de lire attentivement le règlement du forum.
- Comment écrire de belles formules mathématiques.
- Comment joindre une image ou un scan.



Obito31
Membre Relatif
Messages: 106
Enregistré le: 27 Fév 2017, 02:34

Re: Dm informatique Caml

par Obito31 » 02 Nov 2017, 18:34

Merci pour ta réponse mais le problème c que je voit comment le faire mathématiquement mais comment faire un programme en Caml qui répond à la demande

pascal16
Membre Légendaire
Messages: 6663
Enregistré le: 01 Mar 2017, 14:58
Localisation: Angoulème : Ville de la BD et du FFA. gare TGV

Re: Dm informatique Caml

par pascal16 » 03 Nov 2017, 10:28

variante récursive à travailler un peu :
je pend un élément
les ensembles contenant cet élément sont :
_ {cet élément; tous les ensemble sans cet élément}
ceux qui ne contiennent pas cet élément :
_ tous les ensembles sans cet élément
on s’arrête à l’ensemble vide

Obito31
Membre Relatif
Messages: 106
Enregistré le: 27 Fév 2017, 02:34

Re: Dm informatique Caml

par Obito31 » 03 Nov 2017, 11:20

Merci pour ta reponse je vois a peu pres maintenant coppebt resoudre le probleme merci

FLBP
Habitué(e)
Messages: 289
Enregistré le: 25 Aoû 2017, 03:07

Re: Dm informatique Caml

par FLBP » 03 Nov 2017, 11:30

Bonjour,
Vous pouvez faire un arbre combinatoire construit récursivement.
pour un ensemble {A, B, C, D} cela donne :

arbreCombinaison.png
arbreCombinaison.png (3.39 Kio) Vu 269 fois


Où chaque élément de l'arbre représente un ensemble qui contient tous ses nœuds parents ainsi que lui-même.
Pour le construire il faut d'abord construire l'élément D, ici. Ensuite le copier et le greffer sur C. Prendre le tout, le copier et le coller au-dessus de B, et ainsi de suite .... tous les derniers éléments (ici, D) pointent sur NULL.
Il faut donc faire une fonction récursive.

Cordialement.

Obito31
Membre Relatif
Messages: 106
Enregistré le: 27 Fév 2017, 02:34

Re: Dm informatique Caml

par Obito31 » 03 Nov 2017, 11:37

On peut faire comme ça on Caml ?
Sa me rappel du C plutôt ta réponse

Avatar de l’utilisateur
fatal_error
Modérateur
Messages: 6610
Enregistré le: 22 Nov 2007, 14:00

Re: Dm informatique Caml

par fatal_error » 03 Nov 2017, 11:45

hello

je sais pas ce que tu appeles construire l'ensemble de tous les ensembles,
mais tu peux simplement représenter ton ensemble de n élem par un mot binaire (1 si l'elem i est présent)
ca revient à faire les 2^n mots possibles.

Si tu fais un compteur de 0 jusqu'à 2^n, t'as juste à récupérer la représentation binaire de ton entier (puis pour chaque représentation "générer" l'ensemble associé)
la vie est une fête :)

Obito31
Membre Relatif
Messages: 106
Enregistré le: 27 Fév 2017, 02:34

Re: Dm informatique Caml

par Obito31 » 03 Nov 2017, 12:06

Mais la récursivité me permet pas d avoir de compteur

Avatar de l’utilisateur
fatal_error
Modérateur
Messages: 6610
Enregistré le: 22 Nov 2007, 14:00

Re: Dm informatique Caml

par fatal_error » 03 Nov 2017, 20:58

ben vu que tu peux construire les nombres entiers par récurrence, jprésume, que tu peux faire un compteur en récursif...

l'algorithme du noob de base c'est la factorielle
fact(n) -> si n > 1 n*fact(n-1) sinon 1
bon ben
compteur(n) = si n > 0 dosomething(n), compteur(n-1) sinon fin
la vie est une fête :)

 

Retourner vers ✯✎ Supérieur

Qui est en ligne

Utilisateurs parcourant ce forum : Aucun utilisateur enregistré et 90 invités

Tu pars déja ?



Fais toi aider gratuitement sur Maths-forum !

Créé un compte en 1 minute et pose ta question dans le forum ;-)
Inscription gratuite

Identification

Pas encore inscrit ?

Ou identifiez-vous :

Inscription gratuite