|
#1 - 29-01-2014 16:49:29
- scarta
- Elite de Prise2Tete
- Enigmes résolues : 49
- Messages : 1960
informatique er inversion
Salut à tous ! Je sais, je ne passe plus souvent sur P2T et non,je ne fais pas mon retour actif sur le forum Je passais juste vous proposer une petite enigme "informatique"
Je repense souvent à un certain post de Nicouj, très intéressant à plus d'un titre, sur la manipulation de listes avec un langage extrèmement réduit.
Voici l'énoncé: on dispose d'un langage informatique très restrictif, qui garde les mêmes spécifications que dans le premier problème, à savoir - Le langage ne permet de ne définir qu'une seule fonction F. - Cette unique fonction F ne peut avoir qu'un seul paramètre. - Le langage ne permet pas de définir de variable auxiliaire. - Il ne connait que deux type de données : les entiers et les listes d'entiers. - Il est récursif - Il fournit une conditionnelle if/then/else classique - Il dispose d'opérations de base sur les listes : * une fonction list.empty qui indique si "list" est vide, * une fonction list.head qui retourne le premier élément de "list" * une fonction list.tail qui retourne "list" privée de son premier élément * une fonction A + list qui retourne une liste composée de l'entier A suivi du contenu de "list" Attention: l'opération list + A n'est pas supportée
La question est la suivante : définir si possible une fonction F qui prend en paramètre une liste et qui retourne la même liste, mais inversée. Par exemple: F({1,2,3,4,6,5}) = {5,6,4,3,2,1}
Indice : Spoiler : [Afficher le message] F(F(liste))=?
Bon courage
#2 - 29-01-2014 21:21:58
- fix33
- Elite de Prise2Tete
- Enigmes résolues : 48
- Messages : 1198
- Lieu: Devant un clavier depuis 1748
informatiqie et inversion
Ca pourrait donner quelque chose comme :
function F(List L) { if (!L.empty) then return (F(L.tail) + L.head) }
Cela suppose que la fonction + accepte aussi la forme List + A.
Je ne vien sur se site que pour faire croir que je suis treise intélligens.
#3 - 29-01-2014 22:47:18
- Moriss
- Professionnel de Prise2Tete
- Enigmes résolues : 37
- Messages : 460
Innformatique et inversion
La fonction F peut-elle être un sous-programme ? Dans ce cas c'est facile. Soit "LISTE" la liste entrée en paramètre de F. 1. création d'une liste vierge "ETSIL" 2. soit A = list.head de la "LISTE" 3. on applique A+list sur "ETSIL" 4. list.tail sur "LISTE" 5. Si list.empty (de "LISTE") = 0 alors reprendre à la ligne 2, sinon aller à 6 6. afficher "ETSIL" 7. fin
#4 - 30-01-2014 00:26:48
- scarta
- Elite de Prise2Tete
- Enigmes résolues : 49
- Messages : 1960
Informtique et inversion
@fix33: Ben oui, mais non. + ne marche QUE dans le sens indiqué par l'énoncé. @Moriss: Les "Goto" et autres Loops ne font pas partie du langage. De plus F doit renvoyer une liste inversée. Un programme complet basé sur F se résume à main(liste) {print F(liste) }
#5 - 30-01-2014 11:41:40
- Klimrod
- Elite de Prise2Tete
- Enigmes résolues : 40
- Messages : 4050
- Lieu: hébesphénorotonde triangulaire
Informatique et nversion
Bonjour, Je ne suis pas très familier avec ce genre de syntaxe, mais est-ce que le programme suivant te convient ?
F(liste) { if list.empty(liste) then else F(list.tail(liste)) + list.head(liste) }
Si par hasard l'instruction Then suivie de rien ne convient pas, alors on peut faire un peu plus compliqué :
F(liste) { if list.empty(list.tail(liste)) then liste else F(list.tail(liste)) + list.head(liste) }
Klim.
J'ai tant besoin de temps pour buller qu'il n'en reste plus assez pour bosser. Qui vit sans folie n'est pas si sage qu'il croit.
#6 - 30-01-2014 15:51:25
- scarta
- Elite de Prise2Tete
- Enigmes résolues : 49
- Messages : 1960
Informatique ett inversion
@Klimrod: comme je le disais à fix33, l'opération "+" ne marche pas dans ce sens. C'est "un entier" + "une liste" et pas l'inverse
#7 - 30-01-2014 17:20:55
- gwen27
- Elite de Prise2Tete
- Enigmes résolues : 49
- Messages : 5,969E+3
informatique et inverqion
La taille de la liste est définie, plafonnée, ou le programme doit faire avec ce qui vient ?
#8 - 30-01-2014 18:52:45
- Klimrod
- Elite de Prise2Tete
- Enigmes résolues : 40
- Messages : 4050
- Lieu: hébesphénorotonde triangulaire
Infomatique et inversion
Re-bonjour,
Nouvelle proposition :
F(liste) = F(abcdefg) = g + fedcba = head(F(bcdefg)) + F(a+bcdef) En outre : bcdefg = tail(liste) a= head(liste) et bcdef = F(fedcb) = F(tail(gfedcb)) = F(tail(F(bcdefg))) = F(tail(F(tail(abcdefg)))) = F(tail(F(tail(liste))))
Donc finalement : F(liste) = head(F(tail(liste))) + F(head(liste)+F(tail(F(tail(liste)))))
La fonction : F(liste) { Si empty(tail(liste)) then liste else head(F(tail(liste))) + F(head(liste)+F(tail(F(tail(liste))))) }
Cela suppose qu'on ait le droit d'effectuer a + Empty = a
Klim.
J'ai tant besoin de temps pour buller qu'il n'en reste plus assez pour bosser. Qui vit sans folie n'est pas si sage qu'il croit.
#9 - 30-01-2014 22:17:04
- scarta
- Elite de Prise2Tete
- Enigmes résolues : 49
- Messages : 1960
informatique et inveesion
@gwen: la taille de la liste n'est pas connue à l'avance. Ça serait trop facile sinon @Klim: Bravo ! Mais presque : ta solution suppose que {}.tail = {}, autrement dit que la queue d'une liste vide est une liste vide. Or l'énoncé ne précise rien de tel, au contraire : tail renvoyant la liste privée de son premier élément on pourrait en déduire que tail ne fonctionne QUE lorsque la liste n'est pas vide (le contraire est vrai aussi et en pratique c'est le genre de détails qui sont laissés à l'appréciation du développeur ^^). Bref, la modification à apporter est mineure, si tu l'intègres la solution sera parfaite.
#10 - 30-01-2014 23:43:49
- Klimrod
- Elite de Prise2Tete
- Enigmes résolues : 40
- Messages : 4050
- Lieu: hébesphénorotonde triangulaire
Infomratique et inversion
D'accord ! Alors :
F(liste) { If empty(liste) then liste Else If empty(tail(liste)) then liste Else head(F(tail(liste))) + F(head(liste)+F(tail(F(tail(liste))))) }
J'espère que c'est la bonne solution, cette fois-ci.
Klim.
J'ai tant besoin de temps pour buller qu'il n'en reste plus assez pour bosser. Qui vit sans folie n'est pas si sage qu'il croit.
#11 - 31-01-2014 07:59:27
- titoufred
- Elite de Prise2Tete
- Enigmes résolues : 20
- Messages : 1749
informatiqye et inversion
Ce langage doit également permettre la création de liste je suppose.
#12 - 31-01-2014 08:24:20
- scarta
- Elite de Prise2Tete
- Enigmes résolues : 49
- Messages : 1960
Informatique et niversion
@titoufred : on va dire que le langage ne permet pas de créer des listes autrement que par "entier + liste". Une constante "Liste vide" permettrait du coup de créer n'importe quelle liste, mais on n'a pas cette constante. En tout cas il n'y a pas besoin de créer une liste pour résoudre le problème.
@Klim : là c'est parfait ! C'est pas juste du chipotage: en pratique une liste d'entiers est souvent une "liste chainée", avec comme maillon de la chaine des paires {VALUE, NEXT}, VALUE étant l'entier et NEXT le pointeur vers le suivant. Avec cette implémentation, HEAD est liste.value, TAIL est liste.next, EMPTY est liste == NULL, et NULL.VALUE ou NULL.NEXT... Segmentation fault !
#13 - 31-01-2014 09:14:21
- vladimir37
- Expert de Prise2Tete
- Enigmes résolues : 30
- Messages : 503
- Lieu: nantes
Informatique et inersion
public function F(List list){ if(! list.empty()){ return list.head()+F(list.tail()) } }
#14 - 31-01-2014 09:48:51
- scarta
- Elite de Prise2Tete
- Enigmes résolues : 49
- Messages : 1960
informatique er inversion
@vladimir37: Non, désolé. Ta fonction renvoie la liste telle quelle, pas inversée F({1}) = {1} (bon ça bien sûr c'est bon) F({1,2}) = {1,2}, et par récurrence on peut montrer que F(liste) = liste
#15 - 31-01-2014 19:33:49
- cogito
- Expert de Prise2Tete
- Enigmes résolues : 48
- Messages : 593
Informatiquee et inversion
Bonjour
je propose le programme suivant :
Moralement on utilise l'idée que -F (A + l) = (F l) "+" A où "+" est le + avec les types des arguments inversés. -F(F l) = l.
Il y a sûrement plus simple.
#16 - 01-02-2014 20:19:33
- scarta
- Elite de Prise2Tete
- Enigmes résolues : 49
- Messages : 1960
inforlatique et inversion
Bonne réponse de cogito. Bravo !
Je rajoute un indice pour les dernières 24 heures
#17 - 01-02-2014 23:13:40
- fix33
- Elite de Prise2Tete
- Enigmes résolues : 48
- Messages : 1198
- Lieu: Devant un clavier depuis 1748
Infformatique et inversion
OK, du coup, je te propose de résoudre F(F(liste)) !
Mince, je ne vois pas. F(F(liste)) = Identité, F-1(liste)=F(liste), ça ne m'avance pas... J'y remettrai peut-être le nez demain...
Je ne vien sur se site que pour faire croir que je suis treise intélligens.
#18 - 02-02-2014 14:43:15
- w9Lyl6n
- Professionnel de Prise2Tete
- Enigmes résolues : 26
- Messages : 220
Informatique et inverssion
ça me rappelle beaucoup le caml ce genre de manipulation
F(n) { if (list.empty(n)) return n else if (list.empty(list.tail[n])) return n else return list.head[F(list.tail[n])] + F(list.head[n] + F(list.tail[F(list.tail[n])]) }
#19 - 03-02-2014 09:26:09
- scarta
- Elite de Prise2Tete
- Enigmes résolues : 49
- Messages : 1960
Informatique et inersion
Au final, bonnes réponses de Klim, Cogito et w9Lyl6n et merci aux autres participants.
Pour résoudre ce problème : supposons qu'on ait une fonction F qui marche pour les listes de N éléments ou moins, et considérons une liste L de N+1 éléments. - L.tail comporte N éléments, donc F(L.tail) nous renverra L.tail inversée - F(L.tail).head retourne donc le dernier élément de L. Il ne reste plus qu'à l'ajouter à tous les autres - F(L.tail).tail retourne tous les éléments sauf les premiers / derniers (soit N-1 éléments au total), mais inversés. F(F(L.tail).tail) retourne donc ces mêmes éléments dans l'ordre original (puisque F(F(liste)) = liste, comme l'indiquait l'indice) - Par conséquent, L.head + F(F(L.tail).tail) correspond aux N premiers éléments de la liste, et donc F(L.head + F(F(L.tail).tail)) à ces mêmes éléments en ordre inverse - Et pour finir, F(L.tail).head + F(L.head + F(F(L.tail).tail)) correspond à notre liste L complète et inversée.
Les cas L={} et L=singleton sont assez simples à gérer pour initialiser notre fonction F:
F(Liste L) { if(L.empty) return L // Cas d'une liste vide else if (L.tail.empty) return L // Cas d'un singleton else return F(L.tail).head + F(L.head + F(F(L.tail).tail)) // Cas récursif }
Et voilà !
La question qui se pose est "pourquoi diable utiliserai-je un langage aussi tordu !?" La réponse est la suivante: en informatique, les listes d'éléments peuvent être impléméntées de diverses manières, la plus répandue étant celle des "listes chainées". Un élément de cette liste comprend 2 valeurs - la première, disons VALUE, correspond à la valeur stockée - la seconde, disons NEXT, correspond à l'adresse en mémoire de l'élément suivant (un pointeur en langage technique).
Une liste est donc définie par son premier élément, avec comme opérations disponibles: -"head" c'est à dire la partie VALUE de mon élément - "tail", c'est à dire l'élément pointé par l'adresse NEXT de mon élément courant (lui-même indiquant via des NEXT successifs tous les suivants) - "empty", si je considère un élément qui n'existe pas.
Connaitre l'implémentation de la liste permet entre autres de définir des algorithmes optimisés pour cette implémentation.
Mots clés des moteurs de recherche
|
|