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 - 17-11-2010 17:28:37

Nicouj
Professionnel de Prise2Tete
Enigmes résolues : 27
Messages : 330

Informatique et éliimination des doublons

Vous devez programmer une fonction qui prend une liste de nombres entiers en paramètre et qui rend une liste contenant les même nombres mais dans laquelle on aurait enlevé les doublons éventuels.

f([1; 2; 4; 2; 4; 3; 1]) = [1; 2; 3; 4] 
ou bien  [2; 4; 1; 3], etc.
L'ordre nous importe peu.

Le problème est que votre langage est un peu restrictif :

- Le langage ne permet de ne définir qu'une seule fonction à la fois.
- Cette unique fonction ne peut avoir qu'un seul paramètre (donc forcément notre liste).
- Le langage ne permet pas de définir de variable auxiliaire
- le langage ne connait que deux type de données : les entiers et les listes d'entiers

Toutefois le langage offre quelques fonctionnalités :

- Il est récursif
- Il fournit une conditionnelle if/then/else classique
- Il permet de comparer des entiers ( <, >, = )
- Il dispose d'opérations de base sur les listes :
    * une fonction qui indique si une liste est vide,
    * une fonction qui rend la "tête" d'une liste (son premier élément),
    * une fonction qui rend la "queue" d'une liste (tous ses éléments sauf le premier)
    * une constante qui vaut une liste vide.
    * une fonction qui prend un entier et une liste en paramètre et qui rend une liste dont la tête est égale à l'entier passé en premier paramètre, et la queue est égale a la liste passée en second paramètre.

Est-il possible de définir notre fonction avec ce langage ?

Finalement j'aimerais que la fonction respecte aussi l'ordre d'apparition des nombres par rapport a la première liste
f([1; 2; 4; 2; 4; 3; 1]) = [1; 2; 4; 3] 

Est-ce toujours possible ?

(Utilisez votre langage favori mais en le contraignant aux restrictions de l'énoncé)



Annonces sponsorisées :
  • |
  • Répondre

#0 Pub

 #2 - 17-11-2010 20:30:38

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

informatique et élimination ded doublons

On autorise les listes de listes ? Parce que si c'est le cas, un simple arbre binaire de recherche devrait faire l'affaire il me semble, non ?

De plus, sans un append c'est pas trop possible, si?

 #3 - 18-11-2010 08:55:16

Nicouj
Professionnel de Prise2Tete
Enigmes résolues : 27
Messages : 330

Informaatique et élimination des doublons

L'énoncé est correct (en tout cas vis-à-vis des premières remarques, j'ai vraiment pris soin d'éviter les coquilles)

je précise tout de même des points impliqués par l'énoncé :

La concaténation de liste n'est autorisée.
L'utilisation de listes de listes non plus.

D'autre part, il est vrai que la constante valant une liste vide n'est pas nécessaire pour le problème, mais un langage qui offre un type de liste sans une constante liste_vide, c'est bizarre ^^ (j'avoue le langage proposé est bizarre de toute façon :p)

Enfin nous n'avons pas de contrainte de complexité.
Le programme peut être inefficace au possible du moment qu'il se termine et rende la bonne solution

 #4 - 18-11-2010 09:38:05

Barbabulle
Professionnel de Prise2Tete
Enigmes résolues : 49
Messages : 237

Informatique et élmiination des doublons

Bonjour, j'aimerais un petite précision :
Y-a-t'il une fonction qui permet de créer des listes à partir de deux éléments ?
par exemple, si je veux créer une liste comprenant les deux premiers éléments d'une autre liste, je peux faire tête(liste) pour récupérer le premier et tête(queue(liste)) pour récupérer le deuxième, mais comment je fais pour les assembler ?


La paix dans le monde n'est pas menacée par les révoltés, mais par les soumis.        Georges Bernanos

 #5 - 18-11-2010 11:09:24

Nicouj
Professionnel de Prise2Tete
Enigmes résolues : 27
Messages : 330

informatique et élimination des doublobs

Pour répondre à Barbulle et à quiconque se poserait une question similaire à "Y-a-t'il une fonction qui permet de créer des listes à partir de deux éléments ?".

Pour créer une liste à deux éléments, nous avons en fait tout le matériel nécessaire.
Nous avons une liste vide. Appelons-la par exemple "Vide". Nous avons une fonction qui permet d'ajouter un élément en tête d'une liste. Appelons-la "Ajouter".
Je veux créer la liste constituée des éléments x et y : [x; y].
Pour cela, je pars de la liste vide et j'ajoute y en tête, puis x en tête.

Ce qui nous donnerait Ajouter(x, Ajouter(y, Vide)).


Edit : tiens je viens de m'apercevoir que j'ai oublié dans l'énoncé la fonction qui permet d'ajouter un élément en tête d'une liste ><. je rectifie

 #6 - 18-11-2010 14:20:53

Barbabulle
Professionnel de Prise2Tete
Enigmes résolues : 49
Messages : 237

informatique et élimination des doublond

Alors voilà ma solution pour la première partie (je réfléchis toujours à la seconde smile)
L = liste
V = liste vide.

Code:

doublons(L)
    si vide(L) retourne V 
    si vide(queue(L)) retourne L 
    si vide(queue(queue(L)))
        si tete(L)=tete(queue(L)) 
            retourne ajouter(tete(L),V)
        si tete(L)<tete(queue(L)) 
            retourne L 
        si tete(L)>tete(queue(L)) 
            retourne ajouter(tete(queue(L)),ajouter(tete(L),[]))
    si tete(L)=tete(queue(L)) 
        retourne doublons(queue(L))
    si tete(L)<tete(queue(L)) 
        retourne doublons(ajouter(tete(L),doublons(queue(L))))
    si tete(L)>tete(queue(L)) 
        retourne doublons(ajouter(tete(queue(L)),ajouter(tete(L),queue(queue(L)))))

l'idée est la suivante :
si la liste est vide, je renvoie une liste vide
si la liste ne contient qu'un seul élément, je renvoie cette liste
si la liste contient deux éléments, je les compare :
    s'ils sont égaux, j'en supprime un en revoie donc une liste ne contenant qu'un seul élément
    s'ils sont bien "rangés", je renvoie la liste
    sinon j'intervertis les deux éléments et renvoie cette nouvelle liste
si la liste contient plus de deux éléments, je compare les deux premiers
    s'ils sont égaux, j'en supprime un et rappelle récursivement ma fonction sur cette nouvelle liste
    s'ils sont bien rangés, je crée une nouvelle liste avec le même premier élément et un appel récursif sur la queue
    sinon, j'intervertis les deux éléments et je rappelle récursivement ma fonction sur cette nouvelle liste (j'aurais pu optimiser en faisant pareil qu'au cas précédent après l'inversion des deux premier membres, ça fait un appel récursif en moins, mais bon...)

Il me semble que ça fonctionne, à un petit détail près, je ne suis pas sûr que ça s'arrête un jour !
Mais bon, en terme de complexité, on est en n², en imaginant que chaque appel à la fonction doublons prenne 1ms, si on a une liste de 100 éléments à traiter, on a un maximum de 100²=10 secondes de traitement. Donc après mettons 20 secondes, on peut faire un CTRL+C et vérifier la mémoire, on devrait y trouver notre liste sans doublons et en plus bien rangée big_smile

voilà voilà voilà...


La paix dans le monde n'est pas menacée par les révoltés, mais par les soumis.        Georges Bernanos

 #7 - 18-11-2010 14:28:14

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

Informatique et éliination des doublons

C'est pas faute de l'avoir fait remarquer smile

Bon alors
F(liste)
{
  if liste.empty return liste
  if liste.tail.empty return liste
  if liste.head = F(liste.tail).head return F(liste.tail)
  if liste.head > F(liste.tail).head return join(liste.head, F(liste.tail))
  return join(F(liste.tail).head, F(join(liste.head, F(liste.tail).tail)))
}


Invariant: F prend en paramètre une liste de taille N et renvoie cette liste triée décroissante sans doublons.
Démonstration:
Pour N=0 ou 1, c'est la liste elle-même qui est renvoyée donc c'est vrai.
On suppose que c'est le cas au rang N.
P est le premier élément de la liste, et R est le reste. Comme R fait N éléments, alors on a R'=F(R) qui est une liste triée décroissante sans doublons de R.
On a 3 cas différents:
- P est égal au 1er élément de R'. Dans ce cas, R' correspond à la liste triée décroissante sans doublons de notre entrée.
- P est supérieur au 1er élément de R' qui est triée décroissante, alors P est supérieur à tous les éléments de R' et n'est donc pas redondant avec un autre élément de R'. La liste P+R' est donc la liste triée décroissante sans doublons qui correspond de notre entrée.
- P est inférieur au 1er élément de R'. Dans ce cas, le premier élément P' de R' n'est redondant ni les autres éléments de R', ni avec P. De plus, le reste de R' noté R'' fait N-1 éléments, donc P+R'' fait N éléments et du coup F(P+R'') est triée décroissante sans doublons. Au final, P'+F(P+R'') correspond bien à notre entrée triée décroissante sans doublons.

 #8 - 18-11-2010 14:52:37

Nicouj
Professionnel de Prise2Tete
Enigmes résolues : 27
Messages : 330

Informatique et élimination des doubllons

@Barbulle : pas loin pour la première partie ou l'ordre initial n'est pas réclamé ...
Sauf que ton programme ne s'arrêtera jamais des lors qu'il y a + de deux éléments ^^.  Mais tu y es presque.

@Scarta : au temps pour moi, comme "append" correspond en général au nom de la fonction de concaténation dans les langages, j'ai cru que tu réclamais la concaténation ^^.

 #9 - 18-11-2010 18:52:47

Barbabulle
Professionnel de Prise2Tete
Enigmes résolues : 49
Messages : 237

informatique et élimination des diublons

En fait, si je remplace mon avant dernier test

Code:

si tete(L)<tete(queue(L)) 
        retourne doublons(ajouter(tete(L),doublons(queue(L))))

par

Code:

si tete(L)<tete(queue(L)) 
        retourne ajouter(tete(L),doublons(queue(L)))

Mon programme s'arrête (ouf!).
Le problème, c'est qu'il ne détecte plus les doublons en début de liste (après une inversion)... Solution envisagée : appliquer la méthode à elle même un nombre suffisant de fois !
si je fais doublons(doublons(doublons(...(doublons(liste))))), ça fini par marcher !

Mais bon, j'ai quand même un programme de test maintenant :p


La paix dans le monde n'est pas menacée par les révoltés, mais par les soumis.        Georges Bernanos

 #10 - 18-11-2010 21:44:44

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

onformatique et élimination des doublons

Arf, j'avais pas vu la question 2 smile

F(liste)
{
  if liste.empty return liste
  if liste.tail.empty return liste
  if liste.head = liste.tail.head return F(liste.tail)
  else return join(liste.head, join(liste.tail.head, F(join(liste.head, F(liste.tail).tail))))
}

Invariant:
F prend en paramètre une liste de taille N et renvoie cette liste sans doublon avec conservation de l'ordre d'apparition
Démonstration:
Pour N=0 ou 1, c'est la liste elle-même qui est renvoyée donc c'est vrai.
On suppose que c'est le cas au rang N.
Au rang N+1:
On note L notre liste. ° signifie l'élément 0 et ~ signifie la fin d'une liste

Cas 1: L° = ( L~)° : les deux premiers éléments sont les mêmes.
Comme  L~ contient N éléments, F(L~) est L~ sans doublon avec conservation de l'ordre d'apparition. On peut donc renvoyer F(L~)

Cas 2: L° <> (L~)° : les deux premiers éléments sont distincts.
Quelques propositions pour ce cas ci
L~ compte N éléments
=> F(L~) = L~ sans doublon avec conservation de l'ordre d'apparition
=> F(L~) commence par (L~)°
=> (A) F(L~)~ ne contient pas (L~)° (premier élément et pas de doublon)

F(L~) compte au plus N éléments
=> F(L~)~ compte au plus N-1 éléments
=> L° + F(L~)~ compte au plus N éléments
=> F(L° + F(L~)~) = L° + F(L~)~ sans doublon avec conservation de l'ordre d'apparition
=> F(L° + F(L~)~) commence par L°
=> (B) F(L° + F(L~)~)~ ne contient pas L° (premier élément et pas de doublon)

(L~)° + F(L° + F(L~)~)~ ne contient pas de doublon (d'après le résultat A)
(L~)° + F(L° + F(L~)~)~ ne contient pas L° (d'après le résultat B)
=> L° + (L~)° + F(L° + F(L~)~)~ ne contient pas de doublons
L'ordre est bien respecté, car L° arrive en tête, suivi de (L~)° puis du reste dont l'ordre est conservé par F

 #11 - 19-11-2010 19:04:57

Yannek
Passionné de Prise2Tete
Enigmes résolues : 10
Messages : 60

Informatique t élimination des doublons

Partie  1 & 2 (suite aux différentes indications de Nicouj
**********************************************

Fonction f(L : Liste) : Liste;
Début
Si (EstVide(L)) alors retourner L
   sinon
    Si (EstVide(Queue(L)) alors retourner L
     sinon
      Si (Tete(L)=Tete(Queue(L))) alors retourner f(Queue(L))
       sinon
        retourner Ajout(Tete(L),f(Ajout(Tete(Queue(L)),Queue(f(Ajout(Tete(L),Queue(Queue(L))))))))
      FinSi
    FinSi
FinSi
Fin

[pour la partie 1 j'avais d'abord
retourner Ajout(Tete(f(Queue(L))),f(Ajout(Tete(L),Queue(f(Queue(L)))))) ]

 #12 - 20-11-2010 11:14:21

Nicouj
Professionnel de Prise2Tete
Enigmes résolues : 27
Messages : 330

Informatiqu et élimination des doublons

Nous avons une excellente réponse de Scarta pour les deux parties, avec preuve du résultat de ses programmes.

Très bonne réponse également de Yannek pour la première partie pour l'instant (et tres proche de la deuxième partie big_smile)

Barbabulle est proche de la solution de la première partie mais il manque encore quelque chose ^^.

Pour ceux qui ne sont pas familiers avec la programmation récursive, c'est la même façon de penser que lorsqu'on fait une preuve par récurrence (induction).

-  D'abord on définit le résultat de la fonction pour le/les cas de base.
(Typiquement pour les listes, le/les cas de base sont si la liste en paramètre est vide, ou bien a un/deux  élément )

-  Ensuite on définit le cas général où on exploite le fait que la fonction doit marcher (par récurrence) sur des données "plus petite" que le paramètre.
( par ex, pour les liste, on va pouvoir appliquer la fonction aveuglément sur une liste avec strictement moins d'élément que celle de départ)


Pour la partie 1 Spoiler : [Afficher le message] Si la liste est triée, n'est-ce pas plus facile de repérer les doublons ?


Pour la partie 2 Spoiler : [Afficher le message] On oublie le tri car la fonction doit garder l'ordre d'apparition des éléments. Si j'applique la fonction sur une liste, qu'est-ce que je peux dire sur la taille du résultat par rapport  à la liste de départ ? la "tête" du résultat ? la "queue" du résultat ? 

 #13 - 20-11-2010 11:32:49

RL
Visiteur

Informatiqeu et élimination des doublons

Bonjour,

A défaut de répondre à l'énigme, trois exemples qui pourraient vous donner envie de découvrir /Python/ :

sorted([1,2,4,2,4,3,1])
[1, 1, 2, 2, 3, 4, 4]

set([1, 2, 4, 2, 4, 3, 1])
set([1, 2, 3, 4])

list(set([1, 2, 4, 2, 4, 3, 1]))
[1, 2, 3, 4]

Évidemment, on peut faire plus compliqué.

 #14 - 20-11-2010 15:17:04

clementmarmet
Elite de Prise2Tete
Enigmes résolues : 34
Messages : 1329
Lieu: I'm in spaaaace!!

informatique et élimination des doubkons

n'ayant que des connaissances basiques en programmation, je vais essayer en langage commun:

il récupère la première valeur;
il la teste avec la valeur suivante,
puis avec la suivante;
(...)
si il trouve deux valeurs identiques, (=) il supprime l'autre -donc pas celle dont on se sert pour l'instant comme témoin-;
une fois la liste entièrement balayée, il passe à la deuxième

je ne suis pas sûr wink

Spoiler : [Afficher le message] t'as eu de la chance j'ai essayé de le faire en brainfuck lollol


eki eki eki pa tang!!

 #15 - 21-11-2010 21:42:07

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

Informatique et élimiation des doublons

Tu aurais pu, vu que BF est "turing-complet" autrement dit on peut faire avec tout ce qu'on peut faire avec un ordinateur

 #16 - 22-11-2010 11:11:14

Nicouj
Professionnel de Prise2Tete
Enigmes résolues : 27
Messages : 330

Informatique et éliminatio des doublons

Bonnes réponses de scarta et Yanneck.  Bravo supplémentaire a scarta qui offre des preuves complètes.

Barbulle était proche de la première partie.

clementmarmet : en fait ce que tu décris est typiquement ce qu'on ferait pour enlever les doublons, mais avec les contraintes de l'énigme justement ce n'est pas possible. Ça aurait été plus un exo banal d'initiation a la programmation qu'une énigme :-p

Sinon même si BF est T-complete, je mets au défi quiconque de résoudre l'énigme en BF :-p. En fait vu que de toute façon les contraintes de l'énoncé n'ont aucun sens en BF, je serai de toute façon épaté de voir un programme qui élimine les doublons d'une liste en BF ^^

 #17 - 22-11-2010 11:42:59

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

Infromatique et élimination des doublons

Bon ok je m'y mets

 #18 - 23-11-2010 22:08:12

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

infirmatique et élimination des doublons

Et bim !

Code:

>>>,[>+++++++++++[-<---->]>+<
<[----<[->++++++++++<]>[-<+>]
>]>>[>>]<[-]<[-]<,]<[<]>[[[-<
+>]<[->>[>]>>[>]>>+<<<[<]<<[<
]<]>>[>]>>[>]>>[-<<+[<]<<[<]<
+>>[>]>>[>]>]<<[<]<<[<]>]<<[[
->+<]<]>>[>]>[>]>>[[[>]+<<[->
>>>+<<<<]>[->>>[>>>>>+<<<<<->
+<<]<[>]>>>>>[-<<->>>>>>>]<[>
]<<<<<<]>[-]>>[-]>>>>>[-]<<<<
[-<<<<<+>>>>>]<<<<]<[<]>>]<<<
<[<]>[[-<+>]<[->>[>]>+>>+<<<<
[<]<]>>[>]>>>[-<<<<[<]<+>>[>]
>>>]<[->+>+<<]>>[-<<+>>]<[-<<
->>]<<[[-]>>]>[<<<[<]<[-]>>[[
-<+>]>]>>[-<+>]>]<<<<<[<]>]>>
[-<+>]<[->>[>]>+>>+<<<<[<]<]>
>[>]>>>[[-[-[-[-[-[-[-[-[-[->
+>+<<<][<]][<]][<]][<]][<]][<
]][<]][<]][<]<[>]>]<<[->+<]>>
>>[-<<<---------->>>]<<<[-<+>
]+++++++++++[-<++++>]<++++>>>
[-<<+>>]<<[->+>+<<]>[-<+>]>]<
<<[.[-]<]<<<<<[>>+++++++++++[
-<++++>]<.[-]<[[->+<]<]]>>]

Ne pas essayer avec DCode (on ne peut pas taper ses propres entrées). Plutôt avec BrainFuck.tk

Description: Taper en entrée une série de nombres séparés par des virgules; la sortie est la liste sans doublons triée croissante.

Détails: Ce programme réalise les opérations suivantes
- Lecture d'une série de caractères représentant des entiers base 10 séparés par des virgules
- recomposition des entiers en fonction des caractères
- algo similaire plus ou moins à la question 1
- décomposition des entiers du résultats en une série de chiffres en base 10
- écriture des caractères correspondants aux chiffres.

 #19 - 23-11-2010 22:27:17

Barbabulle
Professionnel de Prise2Tete
Enigmes résolues : 49
Messages : 237

Informaatique et élimination des doublons

Impressionnant ! Et surtout fonctionnel !
Tu l'as fait à la régulière ou bien via un langage de plus haut niveau ?


La paix dans le monde n'est pas menacée par les révoltés, mais par les soumis.        Georges Bernanos

 #20 - 23-11-2010 23:29:32

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

Informatique et éliminaion des doublons

C'est fait à l'ancienne, c'est pour ça que ça ne pèse que 723 octets.
Par contre il y a une limitation que je n'ai pas indiqué: le zéro est utilisé pour délimiter les listes, donc il n'est pas possible d'avoir un zéro dans notre liste d'entrée.

 

Réponse rapide

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

Répondez (numériquement) à la petite énigme suivante : 

Dans une course, vous doublez le 31ème, en quelle position êtes-vous ?

Sujets similaires

Mots clés des moteurs de recherche

Mot clé (occurences)
Doublon informatique (12) — Enigme informatique (11) — Doublons informatique (7) — Doublon arbre binaire (3) — Enigmes informatique (3) — Doublon en informatique (2) — Arbre binaire doublon (2) — Doublons arbre binaire c (2) — Doublons en informatique (2) — Elimination des doublons (1) — Informatique (1) — Traiter doublon dans arbre binaire java (1) — Reperer les doublons dans un arbre binaire (1) — Logiciel qui enleve les doublons en chiffres (1) — Cas des doublons dans l arbre binaire (1) — Une fonction qui permet d eliminer toutes le redondances (1) — Programmation enigmes maths (1) — Eliminer doublon ordre d apparition (1) — Arbre binaire recherche redondance (1) — Arbre binaire (1) — Jeux enigme par elimination (1) — Elmination des doublons avec arbre binaire (1) — Les doublons en chiffres (1) — Binaire (1) — Les doublons informatique (1) — Prog (1) — Gestopn des doublons avec avec un arbre binaire (1) — Avec les chiffres 1 346 vous devez trouver 24 en les utilisant tous et une seule fois et seules les operations (1) — Logiciel de chiffres sans doublons (1) — Arbre binaire de recherche sans doublon (1) — Enigme limination (1) — Rapport doublons en informatique (1) — Queue doublons (1) — Eliminer+les+doublons+dans+un+arbre+binaire (1) — Eliminer les duplications informatiques (1) — Enigme mathematique informatique (1) — Les elements en double dans un abr en c++ (1) — Enigme a elimination a resoudre avec reponse (1) — Eliminer les doublons arbre binaire (1) — Doublon arbre (1) — Elimintaion des doublons dans un arbres inaire d erecherche (1) — Logiciel dounlons (1) — Fonction sans doublons plusieurs listes (1) — Liste informatique doublon (1) — Cas des doublons dans l arbre binaire (1) — Doublons & r (1) — Eliminer les dounlons.fr (1) — Arf import ciel doublons (1) — Doublons informatiques (1) — Suppression doublon arbre binaire (1) — Enigme pour les informaticien (1) — Qu est ce un doublon informatique (1) — Detecter un doublons dans un arbre binaire (1) — Fonction iterative qui enleve les redondances en c (1) — Egnime informatique (1) — Arbre de recherche doublon (1) — Dedoublonner langage informatique (1) — Elimination de doublons (1) — Jeux enigme informatique (1) — Creer enigme elimination (1) — Informatique ; doublon (1) — Devinette informatique (1) — C++:programmer qui elimine les doublons (1) — Eliminer doublon ordre d apparition python (1) — Afficher liste 3 chiffres sans redondance en langage c (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