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
[+]

 #26 - 31-05-2018 09:03:43

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 3500

abv

Recherche du plus long mot dans une suite.

On numérote les lettres selon leur rang. On établit un tableau de 3 colonnes a, b et c et dans chacune d'elles, en 1ère ligne on place les n° correspondants.

En seconde ligne, on place les couples :
(x,x+1) en colonne c pour tout x appartenant à la colonne a et x+1 à la colonne b.
(y,y+1) en colonne a pour tout y appartenant à la colonne b et y+1 à la colonne c.
(z,z+1) en colonne b pour tout z appartenant à la colonne c et z+1 à la colonne a.

En 3ème ligne, on place les couples :
(v, w) en colonne c pour tout v ou couple (v, v+1) appartenant à la colonne a et respectivement (v+1, w) ou (v+2,w) appartenant à la colonne b.
Idem pour les 2 autres colonnes.

A toutes les lignes suivantes k : Dans c, les couples résultats des fusions possibles d'un couple de la colonne a et de la ligne k-1 avec un élément (couple ou simple) de la colonne b dont le numéro suit, ou bien un élément de la colonne a qui précède un couple ligne k-1 de la colonne b.

Chaque couple d'une ligne k comporte des couples qui englobent au moins k numéros. Le mot le plus long du dico se trouve parmi les dernières lignes de la colonne "a". 

Exemple avec le mot de 9 lettres accaabcba

......a...........b............c......
1459...........68............237
(6,7)..........(3,4)..........(5,6)
(3,6)...........................(6,8) ...........................(3,6) est la fusion de (3,4) avec (5,6)
..............(2,6)(6,9)..............
(2,7).........................(1,6)(5,9)
(3,9)...........................(2,8)
..............(2,9)(1,8).................

(3,9) est le mot le plus long du dico. Il est recommandé de vérifier en établissant l'arbre correspondant.

#0 Pub

 #27 - 31-05-2018 09:04:06

Ebichu
Expert de Prise2Tete
Enigmes résolues : 49
Messages : 741

Ab

Réponse à #25 :

C'est une jolie façon de présenter les choses. Ça explique encore le lien avec les nombres de Catalan : https://fr.wikipedia.org/wiki/Nombre_de … es_entiers

Sinon, mon programme a donné que les 4 mots de 7 lettres dont on parlait plus haut sont :
* bacabac = a + babcba = acbcac + a
* bcbabcb = a + acbcac = abac + cac
* cabacab = bc + cbabc = bcacb + bc
* cbcacbc = babcba + a = bab + baca

On remarque que la 4e ligne est l'antisymétrique de la 2e, et que la 1e et la 3e sont auto-antisymétriques.

 #28 - 31-05-2018 09:08:46

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 3500

Abcc

Merci pour l'info (pas facile à trouver sans programme.....)

 #29 - 31-05-2018 09:47:49

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 3500

Abbc

Pour ces 4 mots en doublon, je ne retrouve qu'un seul arbre correspondant. C'est à dire que si on raisonne "forme d'arbre" ce ne sont pas des doublons.

 #30 - 31-05-2018 10:40:19

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 3500

abv

C'est bon en fait. Oublis répétés dans la construction (c'est vite fait !) il y a bien à chaque fois 2 arbres différents qui donnent le même mot.

Et en effet, la construction des nombres de Catalan est identique, sauf bien sûr que dans notre problème, il existe des doublons.

 #31 - 31-05-2018 22:09:30

Ebichu
Expert de Prise2Tete
Enigmes résolues : 49
Messages : 741

Ac

Réponse à #26 : joli algorithme, je n'avais pas du tout pensé à ce moyen de limiter la complexité de l'analyse rétrograde.

 #32 - 05-06-2018 08:40:06

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 3500

abv

Un autre problème possible, pour lequel j'ai une réponse, mais je voudrais la soumettre à un autre regard :

Une suite de lettres donnée, comment la compléter par une autre suite, la plus courte possible, pour en faire un mot du dico ?

Exemple : abcbbca à compléter par la suite ?

 #33 - 05-06-2018 10:06:26

Ebichu
Expert de Prise2Tete
Enigmes résolues : 49
Messages : 741

Abbc

Tu as une réponse, mais as-tu la réponse, c'est-à-dire as tu une méthode donnant la suite la plus courte ?

Ce n'est pas dur de trouver une suite convenable dans le dico, mais pour ce qui est de la plus courte, ce n'est peut-être pas aussi évident ?

 #34 - 05-06-2018 11:01:00

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 3500

zbc

Non, je n'ai pas de recettte pour arriver directement à la suite la plus courte.

 #35 - 05-06-2018 11:21:14

Ebichu
Expert de Prise2Tete
Enigmes résolues : 49
Messages : 741

AAbc

OK, je vais regarder quand j'aurai un moment (sans doute pas avant quelques jours).

 #36 - 06-06-2018 22:56:50

Ebichu
Expert de Prise2Tete
Enigmes résolues : 49
Messages : 741

Ac

Voici une démarche que je pense optimale, mais il faudrait le prouver : partant de "a", on développe le mot petit à petit en s'occupant prioritairement des caractères à gauche. Quand les premiers caractères recherchés apparaissent, je les mets en gras et je n'y touche plus.

a
bc
cac
abac
abbcc
abcacc
abcbccc
abcbabcc
abcbbcbcc
abcbbccacc
abcbbcabacc

 #37 - 07-06-2018 08:09:09

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 3500

abx

Tu as au fond entrepris la même approche que la mienne, à savoir traiter les lettres dans l'ordre où elles se présentent. Ce n'est pas sûr que ce soit l'approche la meilleure, un contre exemple est à trouver.....

Pour ma part, j'avais repris la théorie des arbres déjà décrite. Si elle est plus sobre en écriture ( 2n -2 lettres à écrire pour n lettres du mot final ) elle demande du temps pour bien la comprendre.

-----------------------------------------------------------------------------------------

Compléter une suite de lettres par la suite la plus courte possible pour obtenir un mot du dico.

On ne peut pas garantir avec la méthode suivante qu'on obtient toujours le complément le plus court. Toutefois, on obtient facilement une solution.

On établit un arbre avec la suite à l'aide du chemin orienté et on complète les branches manquantes ( toujours des branches droites ) des V.
Pour compacter la présentation de l'arbre (les V de bas en haut, quoique très visuels, ne sont pas tjs faciles à dessiner) on peut procéder comme ci-après sur la base d'un exemple.

Soit la suite aabcb.
 
On rappelle que le chemin orienté est la suite de lettres bc abc abc....qu'on rencontre en longeant toutes les branches de l'arbre.

On démarre donc le chemin jusqu'à obtention de la 1ère lettre de la suite, soit ici " a ".

bcaI

Pour marquer la lettre atteinte, on la complète par I. Après une lettre atteinte, la suite se complète sur la seconde ligne (il n'y a que 2 lignes ), à partir de la dernière lettre atteinte, mais pour une seule lettre, les suivantes remontent en 1ère ligne (en fait la 1ère ligne représente les branches gauches de l'arbre, la seconde les branches droites). 

bcaIcaI
....b

La lettre suivante est b, elle est sous le dernier "a".
bcaIcaI
....b..bI

Lorsqu'une lettre de la 2ème ligne est marquée, alors la 1ère lettre de la suite est en seconde ligne, à partir du 1er vide en partant de la droite, c'est à dire ici sous " c ", les lettres suivantes sont écrites en 1ère ligne à droite. Il faut s'arranger pour qu'à la fin d'un marquage, il reste au moins 1 vide en 2ème ligne. Pour cela, on peut être amené à ne pas marquer une lettre normalement prévue, mais en ajouter 3 lettre supplémentaires et marquer la dernière lettre écrite.

bcaIcaIbcI
....babI

Il ne nous manque plus que le "b"

bcaIcaIbcIbI
....babI..a

Comme tous les V de l'arbre d'un mot du dico ont 2 branches, il n'y a plus qu'à compléter les lettres de la 2ème ligne.

bcaIcaIbcIbI
cab.abIca.c.

Les lettres ajoutées si lisent sur l'arbre de droite à gauche : ccac. La suite aabcb ccac est un mot du dico.

On peut le vérifier par l'arbre, les fusions se font par paire, de droite à gauche ( paires à identifier dans le mot).

 #38 - 07-06-2018 08:18:38

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 3500

Abbc

J'évoquais un contre exemple, en voici un : bcabaac.
En construisant cette suite avec notre méthode, on n'aboutit pas au complément minimum, cette suite étant...un mot du dico !

 #39 - 12-06-2018 09:43:44

Ebichu
Expert de Prise2Tete
Enigmes résolues : 49
Messages : 741

abx

Oui, ce contre-exemple est bien vu. Je dois admettre que j'ai fini par décrocher de ce problème de a, b et c. C'est tellement vaste...

Juste pour info, les invariants qui permettent de séparer tous les mots basés sur a, b, c en 8 familles contenant respectivement :

* a
* b
* c
* aa
* cb
* ba
* ac
* cba

Il y a donc d'abord les parités des nombres de a, b ou c. Par exemple, la famille contenant "a" ne contient que des mots dont les trois parités sont IPP ou PII. Ceci permet déjà de séparer les mots en quatre, mais pas de séparer la famille de "a" de celle de "cb", ni "b" et "ac", ni "c" et "ba", ni "aa" et "cba".

Pour les séparer, il faut avoir recours à un autre invariant, puis difficile à voir : la "signature" du mot, à savoir la parité du nombre d'inversions dans le mot. Par exemple, le mot babca contient 3 inversions : babca, babca et babca, une inversion étant donc un couple de lettres dont la première dans le mot est la dernière dans l'alphabet. La signature de babca est donc impaire.

On démontre alors que dans la famille contenant "a", la signature des mots est, si les mots contiennent 1, 2, 3,... lettres, P, P, I, I, P, P, I, I... tandis que dans la famille contenant "cb", c'est la signature opposée. De même, la signature permet de séparer les 3 autres couples de familles.

 #40 - 12-06-2018 11:31:22

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 3500

Ab

ça a l'air costaud ce truc....

Qu'entends tu par parité d'une lettre ?

 #41 - 12-06-2018 14:31:51

Ebichu
Expert de Prise2Tete
Enigmes résolues : 49
Messages : 741

Abbc

Non, ce n'est pas costaud du tout. La première partie tout du moins.

Prends des mots issus de "a", par exemple, bc, cac, caab...
* pour "a", le nombre de lettres de type "a", "b", "c" est 1,0,0 soit IPP (Impair Pair Pair).
* pour "bc", c'est 0,1,1 soit PII.
* pour "cac", c'est 1,0,2 soit IPP.
* pour "caab", c'est 2,1,1 soit PII.

Il est immédiat par récurrence que les mots issus de "a" avec un nombre impair de lettres sont du type IPP, et que ceux avec un nombre pair de lettres sont du type PII.

On peut dire la même chose des mots issus de "cb", mais pas des 6 autres familles. Par exemple, les mots issus de "b" alternent entre PIP et IPI.

Par contre, l'histoire avec la signature s'observe bien sur des exemples, mais est un peu plus casse pieds à démontrer.

 #42 - 12-06-2018 16:27:39

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 3500

Ab

OK pour la parité. Mais pour la signature, il faudrait en dire un peu plus. Tu as renoncé à rédiger un petit quelque chose là dessus ?

 #43 - 12-06-2018 17:33:49

Ebichu
Expert de Prise2Tete
Enigmes résolues : 49
Messages : 741

zbc

Oui, je crois que je ne le ferai pas, vu le temps dont je dispose en ce moment. Et me connaissant, dans deux mois je serai passé à autre chose et je n'aurai pas le courage de m'y remettre.

Pour la signature, le raisonnement est ainsi.

Imaginons qu'un mot est du type (début)a(fin), et qu'on transforme le "a" en "bc". Par exemple,  le mot (bc)a(baac) devient (bc)bc(baac).

Dans le mot initial, avant le "a", il y avait :
* un certain nombre de "a", qui ne créaient aucune inversion avec le "a", et qui n'en créeront pas non plus avec "bc".
* un certain nombre de "b", qui créaient des inversions avec le "a", mais ces inversions disparaitront avec le "bc".
* un certain nombre de "c", qui créaient des inversions avec le "a", et il y aura autant d'inversions dans le nouveau mot avec le "b".
Donc au total, il y a autant d'inversions qui disparaissent qu'il y avait de "b" avant la lettre qu'on développe.

Dans le mot initial, après le "a", il y avait :
* un certain nombre de "a", qui ne créaient aucune inversion avec le "a", et qui en créeront 2 chacun avec "bc".
* un certain nombre de "b", qui ne créaient aucune inversion avec le "a", mais en créeront 1 chacun avec "bc".
* un certain nombre de "c", qui ne créaient aucune inversion avec le "a", et qui n'en créeront pas non plus avec "bc".
Le premier point n'a pas d'influence sur la signature, car 2 est pair. Seul le nombre de "b" est à considérer.

Donc en regroupant les deux parties du mot, il suffit de considérer le nombre de "b" du mot initial. Si ce nombre de "b" est pair, alors la signature ne change pas, s'il est impair, alors la signature change.

 #44 - 13-06-2018 18:45:45

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 3500

abx

Bien vu !

 #45 - 18-06-2018 10:34:40

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 3500

Ac

Après relecture de ton dernier message, cette phrase :

* un certain nombre de "c", qui créaient des inversions avec le "a", et il y aura autant d'inversions dans le nouveau mot avec le "b".

n'est pas tout à fait correcte, car pas d'inversion "c" avec "a".

 #46 - 18-06-2018 19:38:17

Ebichu
Expert de Prise2Tete
Enigmes résolues : 49
Messages : 741

anc

Ben si :

si tu passes de c(a)c à c(bc)c, dans le premier mot, il y a une inversion : cac, et dans le deuxième, une également : cbcc.

"...c...a..." est une inversion car "c" est après "a" dans l'alphabet, mais avant dans le mot.

 #47 - 19-06-2018 07:45:37

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 3500

abv

OK, j'ai bien fait de poser la question, je ne l'avais pas compris comme ça.

Subtil.

 

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 ?

Sujets similaires

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