petite fonction récurrsive...

Recherche :

Dernière réponse

Sujet : petite fonction récurrsive...

BENB

Kyle_Katarn a écrit a écrit :

sache que mathématiquement, même l'ensemble vide est un ensemble, c'est même un espace vectoriel (voire une C-algèbre si tu veux...)

certes...
mais il me semble que son nom le laissait supposer...

Votre réponse

Nom d'utilisateur

Pour poster, vous devez être inscrit sur ce forum .... si ce n'est pas le cas, cliquez ici !

Le ton de votre message

Votre réponse

Smilies

Liste des smilies perso
Wiki smilies
Chercher un smiley

Options

Activer votre signature
Désactiver les smilies
Activer la notification par email du sujet

Aperçu

Vous avez perdu votre mot de passe ?

Vue Rapide de la discussion

BENB

Kyle_Katarn a écrit a écrit :

sache que mathématiquement, même l'ensemble vide est un ensemble, c'est même un espace vectoriel (voire une C-algèbre si tu veux...)

certes...
mais il me semble que son nom le laissait supposer...

gizmo

flo850 a écrit a écrit :

cessez le feu , je me rends , je l'ai oublié , il faut rajouter

si vide(E)
alors arreter

avant la boucle for

c'est pas grave ;) c'était juste l'occasion d'avoir une discussion intéressante.

Kyle_Katarn

sache que mathématiquement, même l'ensemble vide est un ensemble, c'est même un espace vectoriel (voire une C-algèbre si tu veux...)

flo850

cessez le feu , je me rends , je l'ai oublié , il faut rajouter

si vide(E)
alors arreter

avant la boucle for

art_dupond

flo850 a écrit a écrit :

comme tu ne dis pas le langage , voici l'algo

permutation(Ensemble E)
{
pour chaque e de E
afficher e
permutation (E-{e})
sauter une ligne
}

oki je crois que j'ai capté.

J'ai pas mis le language parce que je voulais pas qu'on me le fasse non plus.

En tout cas, merci :jap:

art_dupond

waouw, pleins de réponses :love:

Merci les gens. je vais lire tout ca... :jap:

LeGreg

[HS]Hop, l'extrait en question[/HS]

Citation :

"And only one for birthday presents, you know, There's glory for you!"
"I don't know what you mean by 'glory,' " Alice said.
Humpty Dumpty smiled contemptuously. "Of course you don't -- till I tell you. I meant "there's a nice knock-down argument for you!'"
"But 'glory' doesn't mean 'a nice knock-down argument,'" Alice objected.
"When I use a word," Humpty Dumpty said in a rather a scornful tone, "it means just what I choose it to mean -- neither more nor less.
"The question is," said Alice, "whether you can make words mean different things."
"The question is," said Humpty Dumpty, "which is to be master -- that's all."
Alice was too much puzzled to say anything, so after a minute Humpty Dumpty began again.
"They've a temper, some of them -- particularly verbs, they're the proudest -- adjectives you can do anything with, but not verbs -- however, I can manage the whole lot! Impenetrability! That's what I say!"
"Would you tell me, please," said Alice, "what that means?"
"Now you talk like a reasonable child," said Humpty Dumpty, looking very much pleased. "I meant by "impenetrability' that we've had enough of that subject, and it would be just as well if you'd mention what you meant to do next, as I suppose you don't intend to stop here all the rest of your life."
"That's a great deal to make one word mean," Alice said in a thoughtful tone.
"When I make a word do a lot of work like that," said Humpty Dumpty, "I always pay it extra."
"Oh!" said Alice. She was too much puzzled to make any other remark.

LEGREG

LeGreg

eheh il n'est pas necessaire
d'avoir un ensemble fini pour enumerer
ses elements, il suffit qu'il soit denombrable.
mais pour s'en convaincre il suffit de se dire
que si l'enumeration doit se terminer a l'element n
pour raison X ou Y (memoire, ou capacite en bits),
alors rien n'interdit de doubler la memoire ou la ressource
qui fait defaut pour enumerer l'element n+1.
Bon evidemment se pose le probleme de la terminaison
et de l'argent necessaire si les besoins en ressources
croissent avec le nombre d'element a enumerer.

Par contre si l'ensemble n'est pas denombrable
(ensemble des reels), alors le probleme est insoluble
avec les machines universelles classiques.
Ce qui fait dire a certains que les nombres
reels n'existent pas et sont une conspiration de mathematiciens
mais je m'egare :)

A+
LEGREG

BENB

LeGreg > NULL est une valeur en C/C++, 0 en general, et c'est nous qui semantiquement lui donnons le sens de "rien"

Je suis bien d'accord avec toi, "element vide" est une expression absurde, et c'est avant tout cette expression que j'ai attaque, d'abord parceque un element n'est, a priori, pas un contenaire et de plus le vide ne s'appliquait pas a lui...
Il aurrait donc ete "l'element 'vide'" ou encore "l'element du vide" mais alors l'ensemble qui le contient n'est plus vide.

Il n'est donc pas "vide"
Il n'est donc pas un element.

Pour revenir au debut de la discution avec Gizmo, "Pour chaque element de E" implique en lui meme une terminaison si E est un ensemble fini (ayant un nombre fini d'elements). La modelisation des ensembles infinis (ayant un nombre infinis d'elements) n'etant pas facile en informatique nous supposerons donc que E est fini, ce qui bien comode pour proposer des permutations...

LeGreg

En Caml tu peux
definir
type monType= Rien | Quelquechose;;

mais "Rien" n'est pas une construction
du langage
ca n'a le sens de Rien
que parce que je l'utilise ainsi dans mon programme.
C'est purement binaire c'est 0 ou 1.
(comme le type NULL en C, qui est different
de void qui signifie une 'absence' de parametre)
Quand tu as un objet de type monType qui vaut
"Rien" ca reste un objet et il vaut quelque chose:
il vaut "Rien", et il n'est pas vide
(comment un objet ou un element peut-il etre vide
si ce n'est pas un conteneur ou un ensemble?)
Si MonType represente une liste ou un ensemble
alors Rien peut signifier une liste vide mais
ce n'est que parce que MOI j'ai decide de representer
mes donnees ainsi.

Bon c'est peut-etre embrouille comme explication
mais j'espere que ca vous aura un peu eclaire.

[HS] Quelqu'un se rappelle le passage d'Alice
au pays des merveilles ou elle rencontre
Humpty Dumpty? [/HS]

A+
LEGREG

gizmo

c'est ca.

Exemples de langages fonctionnels : ML, CaML, Eiffel (cas particulier car la compilation le transforme en C), Modula,...

BENB

gizmo a écrit a écrit :

les langages fonctionnels utilisent ce concept. Un objet est défini par ce qu'il contient et ce qu'il contient peut ête le vide ou des éléments et le vide.

C'est donc plus un descripteur de l'ensemble formellement represente comme un element, ou un pre-element...

Quels sont ces langages ?

gizmo

les langages fonctionnels utilisent ce concept. Un objet est défini par ce qu'il contient et ce qu'il contient peut ête le vide ou des éléments et le vide.

BENB

gizmo a écrit a écrit :

oui, mais ce n'est pas en contradition avec la logique informatique de création de variable. Ces langages considèrent que tu vas pouvoir transformaer le vide en qqch, et donc acceptent de travailler aveuglément dessus.

Mais cette chose est elle toujours presente quand l'ensemble n'est plus vide ?
Quels sont les langages qui usent de ce concept...

gizmo

oui, mais ce n'est pas en contradition avec la logique informatique de création de variable. Ces langages considèrent que tu vas pouvoir transformaer le vide en qqch, et donc acceptent de travailler aveuglément dessus.

[edtdd]--Message édité par gizmo--[/edtdd]

BENB

gizmo a écrit a écrit :

en effet, c'est juste un concept, mais tout est-il que certains langages permettent de travailler sur le vide (donc même pas le Null ou le 0).

Oui mais c'est en contradition avec les concepts mathematiques des ensembles....
C'est pour cela que je refute le droit de cette chose a s'appeller "element"

[edtdd]--Message édité par BENB--[/edtdd]

gizmo

en effet, c'est juste un concept, mais tout est-il que certains langages permettent de travailler sur le vide (donc même pas le Null ou le 0).

BENB

gizmo a écrit a écrit :

1° c'est de l'algo, donc il doit prévoir les cas de figure les plus complexes, et d'autre langage que le C++ acceptent un élément vide (les langages fonctionnels entre autre), donc la condition d'arret est a prévoir ou au moins a documenter.

2° c'était un exemple...

2° généralement c'est traduit plutot par foreach, qui a une autre signification que le for dans certains langages.

3° entièrement d'accord.

J'ai du mal a conceptualiser un "element vide"
car un ensemble qui contiendrait un tel element ne serait pas vide...
de plus mathematiquement le contenant est l'ensemble, et l'element le contenu, et qualifier de vide qqchose suppose que ce soit un contenant...

Par contre que dans certains langages il y ait un indicateur d'ensemble vide, certes, mais ce n'est pas un element.

Par exemple en C/C++ le NULL ou 0 joue ce role... Un pointeur qui pointe sur NULL est cense pointer sur rien et donc representer un "ensemble vide"
mais il n'est en rien un element de cet ensemble...

gizmo

1° c'est de l'algo, donc il doit prévoir les cas de figure les plus complexes, et d'autre langage que le C++ acceptent un élément vide (les langages fonctionnels entre autre), donc la condition d'arret est a prévoir ou au moins a documenter.

2° c'était un exemple...

2° généralement c'est traduit plutot par foreach, qui a une autre signification que le for dans certains langages.

3° entièrement d'accord.

BENB

gizmo a écrit a écrit :

ben ca dépend des objets avec lesquels tu travailles, si tu travailles avec une liste chainnée terminée par l'élément null (en c++), et bien si ta condition d'arret est mal concue, ton algo va boucler a l'infini.

1- C'est de l'algo donc independant du langage

2- Tes listes chainee doivent etre mal concue si tu peut confondre un element de gestion de la chaine avec ce que cette chaine est sensee contenir... Utilise la list de la STL et ton probleme disparait...

2- "pour chaque" est generalement traduit par un for(), et donc la condition de fin est implicite surtout en C/C++ puisque dans le dernier For la condition de fin du for se trouverait verifiee des le debut, et donc aucune iterations.

3- Ce qui m'intrigue beaucoup plus c'est le E-{e}, qui est, a mon avis nettement plus complexe de mise en oeuvre, a priori. Mais encore une fois il s'agit ici d'un Algo et une ecriture de haut niveau se justifie parfaitement, et ce d'autant plus que c'est bien ce qu'appelle la question puisqu'elle n'indique absolument pas comment le premier E est fourni (tableau - liste chainee ) ?

gizmo

ben ca dépend des objets avec lesquels tu travailles, si tu travailles avec une liste chainnée terminée par l'élément null (en c++), et bien si ta condition d'arret est mal concue, ton algo va boucler a l'infini.

BENB

gizmo a écrit a écrit :

a condition de ne pas considérer l'élément vide, oui.

:??:
c'est quoi l'element vide ? Je ne connais rien de tel...
Je considere l'ensemble vide, mais pas l'element, or un element ne peut etre confondu avec un ensemble...

cf "l'ensemble de tous les ensembles"

De plus meme en admettant qu'il existe un tel element
si E ne contient que l'element vide, il n'est pas vide et donc l'execution continue, E / { element vide} = E/E = ensemble vide
d'ou au passage suivant l'ensemble est vide...

[edtdd]--Message édité par BENB--[/edtdd]

gizmo

a condition de ne pas considérer l'élément vide, oui.

BENB

gizmo a écrit a écrit :

ouais, mais bon, avec une codition d'arret c'est quand même nettement mieux ;)

Je suppose que "pour chaque e de E"
implique que on s'arrete quand E est vide...

gizmo

ouais, mais bon, avec une codition d'arret c'est quand même nettement mieux ;)

flo850

comme tu ne dis pas le langage , voici l'algo

permutation(Ensemble E)
{
pour chaque e de E
afficher e
permutation (E-{e})
sauter une ligne
}

art_dupond

Salut les gens,

on donne "n", et je dois sortir toutes les permutations de 0 -> n-1.

ex : n = 3

0 1 2
0 2 1
1 0 2
1 2 0
2 0 1
2 1 0

Je dois faire ca avec une fonction récursive, mais j'suis bloqué. Ca à l'air tout con, mais j'y arrive pas :(

Quelqu'un peut me donner une piste ? :jap:

ps : faut pas m'expliquer ce qu'est une fct recursive, ...