Enigmes

Forum dédié aux énigmes et à toutes formes de jeux de logique.

Déconnexion

Tu n'es pas identifié sur Prise2tete : s'identifier.

accueil Accueil forum Forum
[+]

 #1 - 29-01-2014 16:49:29

scarta
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 1934

Informtique et inversion

Salut à tous !
Je sais, je ne passe plus souvent sur P2T et non,je ne fais pas mon retour actif sur le forum smile
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

  • |
  • Répondre

#0 Pub

 #2 - 29-01-2014 21:21:58

fix33
Elite de Prise2Tete
Enigmes résolues : 48
Messages : 1198
Lieu: Devant un clavier depuis 1748

Infromatique 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

Informatiquue 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 : 1934

informatisue 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 : 4045
Lieu: hébesphénorotonde triangulaire

Informatique et inverison

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 : 1934

informatique rt 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,896E+3

Informatiique et inversion

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 : 4045
Lieu: hébesphénorotonde triangulaire

informatique et inverdion

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 : 1934

Informatiquee et inversion

@gwen: la taille de la liste n'est pas connue à l'avance. Ça serait trop facile sinon smile
@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 : 4045
Lieu: hébesphénorotonde triangulaire

Informaique et inversion

D'accord smile ! 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

Informatique et nversion

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 : 1934

Informatique et inveersion

@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 : 1934

ingormatique et 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

informatique et ibversion

Bonjour smile

je propose le programme suivant :

Code:

Définition F (l : liste d'entier) :=
if l.empty then l
else if (l.tail).empty then l
else (F l.tail).head + (F (l.head + F (F l.tail).tail))

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 : 1934

Informatique et niversion

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

Informatique et inversoin

OK, du coup, je te propose de résoudre F(F(liste)) ! lol

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... hmm


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

infoematique et inversion

ça me rappelle beaucoup le caml ce genre de manipulation smile

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 : 1934

informatique et invzrsion

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.

 

Réponse rapide

Rédige ton message
| | | | Upload | Aide
:) :| :( :D :o ;) :/ :P :lol: :mad: :rolleyes: :cool:
Sécurité

Répondez à la devinette suivante : 

Le père de toto a trois fils : Pif, Paf et ?

Mots clés des moteurs de recherche

Mot clé (occurences)
Enigme informatique (1) — ?l?ments (1) —

Pied de page des forums

P2T basé sur PunBB
Screenshots par Robothumb

© Copyright 2002–2005 Rickard Andersson

Prise2Tete Forum Statistiques Liste des membres Hall of Fame Contact
© Prise2tete - Site d'énigmes et de réflexion.
Un jeu où seules la réflexion, la logique et la déduction permettent de trouver la solution.

Flux RSS de Prise2Tete Forum Jeux & Prise2Tete Test & Prise2Tete Partenariat et Publicité sur Prise2Tete