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 - 25-02-2012 14:46:15

titoufred
Elite de Prise2Tete
Enigmes résolues : 20
Messages : 1749

yn mot sans répétition successive

J'ai entendu ce problème évoqué lors d'une conférence à Grenoble, intitulée il me semble "du périodique à l'apériodique", mais ce n'est qu'un souvenir lointain...

#0 Pub

 #27 - 25-02-2012 16:58:41

godisdead
Expert de Prise2Tete
Enigmes résolues : 22
Messages : 747

un mot szns répétition successive

ce n'était pas plutot apérodique

 #28 - 25-02-2012 18:38:27

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

Un mot sans répétition successsive

titoufred a écrit:

J'ai entendu ce problème évoqué lors d'une conférence à Grenoble, intitulée il me semble "du périodique à l'apériodique", mais ce n'est qu'un souvenir lointain...

Merci. Et pas de recette pour ce problème ?

 #29 - 25-02-2012 19:49:14

shadock
Elite de Prise2Tete
Enigmes résolues : 39
Messages : 3334

Un mot sans répétition successivee


"L'expérience est une lanterne qui n'éclaire que celui qui la porte." L-F. Céline

 #30 - 25-02-2012 19:55:07

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

Un mot ssans répétition successive

Quelque chose d'autre qu'un programme, je voulais dire.

 #31 - 25-02-2012 20:45:24

shadock
Elite de Prise2Tete
Enigmes résolues : 39
Messages : 3334

Un mot sans répétition succeessive

Pour faire un programme il faut l'idée qui va avec, sinon le programme ne fait rien.
smile


"L'expérience est une lanterne qui n'éclaire que celui qui la porte." L-F. Céline

 #32 - 26-02-2012 00:33:57

titoufred
Elite de Prise2Tete
Enigmes résolues : 20
Messages : 1749

Un mt sans répétition successive

Oui, mais il y a programme "bourrin" qui va tester chaque possibilité et dont le temps de calcul va être exponentiel, et programme "intelligent" avec un algorithme dont le temps de calcul n'explose pas. il serait intéressant de savoir dans quelle catégorie se situe celui de Scarta. Au passage, on pourrait savoir si on peut construire des mots aussi longs qu'on veut.

 #33 - 26-02-2012 07:54:52

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

un mot sans répétition duccessive

ça pour le mot aussi long que l'on veut, j'en suis convaincu depuis le début...
A partir de 2 lettres, le nombre de mots différents de k lettres est inférieur (pas longtemps égal) au kième nombre de Fibonacci correspondant.

 #34 - 28-02-2012 00:32:16

titoufred
Elite de Prise2Tete
Enigmes résolues : 20
Messages : 1749

un mot sans répérition successive

scarta, tu nous en dis un peu plus sur ton algorithme ?

 #35 - 28-02-2012 21:15:03

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

Un mot sans répétitionn successive

L'idée est la suivante:
Je pars de a
Pour chaque lettre à ajouter, j'ai le choix entre a, b et c.
Je commence par éliminer la dernière lettre ajoutée.
J'essaye ensuite avec la 1ere des 2 qui restent et je regarde si ça passe. Si oui, j'ajoute la lettre; sinon j'essaye avec la suivante. Si ca ne passe pas non plus, je change la dernière lettre du mot par une autre (c'est à dire celle qui n'est ni la dernière ni l'avant dernière)

Exemple:
a => ab => aba
=> abab pas bon, abac ok => abaca => abacab
=> abacaba => abacabab pas bon, abacabac non plus, je change la dernière lettre par c (ni a la dernière, ni b l'avant dernière) => abacabc
=> abacabca
etc...

Ca c'est pour l'idée, l'implémentation est un poil plus tordue:
Stockage en mémoire: un tableau de groupes de 4 bits notés ABCD
AB peut valoir 00 (lettre a), 01 (lettre b), 10 (lettre c) et 11 (lettre non calculée encore).
CD peut valoir 00 (cette lettre apparaît pour première fois), 01 (cette lettre apparaît avant-dernière position, soit 2 lettres avant celle-ci), 10 (3 lettres avant) ou 11 (4 lettres avant)
Du coup, pour voir si une lettre passe, il faut regarder si le mot de k lettres à partir de la fin se répète juste avant la k-ième lettre avant la fin; et ce pour tout k. Comme un tel mot doit forcément finir par la même lettre que celle que je viens d'écrire, je peux remonter rapidement à toutes les instances de cette lettre pour gagner du temps. Je m'arrête quand je suis à plus de la moitié du tableau parcourue.
Bien sûr, il y a en plus de ça 3 petites variables qui indiquent à combien de lettres se truve le dernier a, b ou c; à chaque tour on en incrémente 2 et on réinitialise la 3ème.


voilà voilà

 #36 - 28-02-2012 23:08:04

titoufred
Elite de Prise2Tete
Enigmes résolues : 20
Messages : 1749

un mot sans réoétition successive

D'accord, merci pour les précisions sur l'algorithme. Donc, pas de certitude que ça ne s'arrête pas un jour...

 #37 - 29-02-2012 01:14:15

L00ping007
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 2010
Lieu: Paris

Un mot asns répétition successive

En trouvant une relation entre n, la longueur d'un mot, et le nombre de mots acceptables de longueur n, on pourrait peut-être conclure.
Un programme brute force donne ce nombre pour des petites valeurs de n, il faudrait arriver à généraliser, je ne sais pas si c'est possible ?

f(1)=3
f(2)=6
f(3)=12
f(4)=18
f(5)=30
f(6)=42
f(7)=60
f(8)=78
f(9)=108
f(10)=144
f(11)=204

Quelqu'un voit une relation ?

 #38 - 29-02-2012 10:00:40

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

un mot sans répétition suvcessive

Il y a tout un tas de preuves et d'algorithmes un peu plus génériques pour construire ce genre de suites apériodiques.
C'est pas exactement le même problème, c'est plus générique mais allez toujours voir ça:
http://en.wikipedia.org/wiki/Aperiodic_tiling

 #39 - 29-02-2012 13:17:55

dhrm77
L'exilé
Enigmes résolues : 49
Messages : 3004
Lieu: Fanning Island-?-Lac Tele,Mali

Un mot sans répéttion successive

L00ping007 a écrit:

f(2)=6
f(3)=12
f(4)=18
f(5)=30
f(6)=42
f(7)=60
f(8)=78
f(9)=108
f(10)=144
f(11)=204

Quelqu'un voit une relation ?

https://oeis.org/A006156
est-tu sur du 144?
sinon ca pourrais etre 3 fois cette seerie: https://oeis.org/A000123


Great minds discuss ideas; Average minds discuss events; Small minds discuss people. -Eleanor Roosevelt

 #40 - 29-02-2012 14:07:16

titoufred
Elite de Prise2Tete
Enigmes résolues : 20
Messages : 1749

un lot sans répétition successive

Effectivement, ce genre de mots a été assez étudié (en anglais ternary square-free words), et il a été démontré qu'il en existe des aussi longs qu'on veut.

 #41 - 29-02-2012 17:23:22

FRiZMOUT
Verbicruciste binairien
Enigmes résolues : 49
Messages : 2218

Un mot sans réépétition successive

Y'a des fautes dans l'oeis, la honte.

 

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

Sujet Date Forum
14-02-2014 Enigmes Logiques
P2T
28-12-2010 Enigmes Logiques
P2T
05-03-2015 Enigmes Logiques
19-11-2010 Enigmes Logiques
P2T
Mot de tête... par SHTF47
26-02-2011 Enigmes Logiques
P2T
Jam Mot par Lui-meme
24-09-2013 Enigmes Logiques
17-07-2013 Enigmes Logiques
P2T
Le Mot par shadock
03-05-2012 Enigmes Logiques
P2T
09-12-2009 Enigmes Logiques
P2T
Le mot mystère par mitsuidewi
13-03-2011 Enigmes Logiques

Mots clés des moteurs de recherche

Mot clé (occurences)
Enigme longue (5) — Quel est le mot a onze lettres dont aucunes ne se repete (5) — Mot le plus long sans repetition (5) — Plus long mot sans repetition (4) — Mot anglais long et sans repetition lettre (4) — Mot de 10 lettres sans repetition (4) — Mots de 11 lettres dont les lettres ne se repetent pas (3) — Mot le plus long sans repetition de lettre (3) — Repetition successive (3) — Plus long mot sans repeter (3) — Le plus long mot sans repetition (3) — Devinet je suis un mot de 11 lettres ocune lettre ne se repete qui suis je (3) — Mot le plus long sans 2 fois la meme lettre (3) — Le mot qui a 11 lettre est une lettre ne revient pas deux foi (3) — Mots de 12 lettres sans 2 fois la meme (3) — Mot de 50 lettres (3) — Mot long et complique avec les 26 lettres (2) — Un mot dont 11 lettres de se repetent pas (2) — Mot qui contient 11 lettres qui ne repete pas (2) — Un mot dont on ne repete pas deusmx lettre a la fois devinettes (2) — Pli long mot francais sans repetition de lettre (2) — Quel mot contient 7 lettres et dont les lettres ne se r?p?tent pas (2) — Mot francais de plus de 50 lettres (2) — Mots francais le plus long sans repetition de lettre (2) — Plus long mot sans repetition de lettre (2) — Mot 8 lettres lettre ne revient pas deux fois (2) — Un mot consituer de onze lettres dont on ne repete pas devinettes (2) — Le plus long mot en francais sans repetition de lettre (2) — Le plus long mot sans repetition de lettres (2) — Le plus long mot en fran?ais dont aucune lettre ne se repete (2) — Le plus long mot possible sans que deux lettres se repetent (2) — Mot 9 lettres sans repetition de lettre (2) — Quel est le mot qui a 11 lettres une lettre ne se reppete pas deux fois dans le mot (2) — Mot sans deux fois la meme lettre (2) — Mot sans repetition de lettre (2) — Un mot en 12 lettres sans repetition des lettres (2) — 3 mots en francais avec 11 lettre qui se repette pas 2 fois (1) — Le mot le plus sans repetition de lettre (1) — Le plus le mot sans repetition de lettre (1) — Repetition successiv de 3 mots (1) — Mot en 26 lettres (1) — Les mots les plus long non repetition des lettres (1) — Plus long mot sans repeter les lettres (1) — Mot en 11 lettres sans 2 fois la meme lettre (1) — Repetition lettre dans un mot (1) — Quel est le mot qui contient 9 lettres sans aucune repetition de ses lettres (1) — Enigme mot decompose repete (1) — Le mot a plus de lettre (1) — La lettre la plus repetees dans un mots (1) — Quel est le mot qui contient 11 lettre mais les lettres ne sont pas repeter deux fois (1) — Mot sans meme lettre (1) — Plus long mot sans lettre en double (1) — La plus long mot en francais sans repetition (1) — Enigme a repetition* (1) — Long mot sans repeter lettre (1) — Mot 11 lettres sans repetition lettres (1) — Les mots comportant neuf lettres qui ne se rep?tent pas (1) — Long mot 50 lettres (1) — Quel mot qui a 9 lettres qui ne se repete pas (1) — Repetition du lettre s 5 fois dans un mot (1) — Mots ne comportant pas 2 fois la meme lettre (1) — Plus long mots sans meme lettre (1) — Quel est le mot francai qui a 12 lettre dans aucune lettre ne se repete (1) — Le mot avec les lettres 1 fois (1) — 12letres dans un mot aucune letre n est repetee la dans (1) — Un mot qui contient 11 lettres dont aucune ne se repete? (1) — Quel mot de 9 lettres sans repetition de lettres (1) — Mot de 11 lettres sans repetition de lettres (1) — Le mot le plus long en fran?ais dont aucune lettre ne se repete (1) — Plus grand mot sans repetition lettre (1) — Des mots qui na pas deux fois la meme lettres (1) — Un mot contenant 11 lettres sans aucunes repetition d lettre? (1) — Le mot le plus long qui ne repete jamais la meme lettre (1) — Mots en 9 lettres sans repetition (1) — Un mot de 11 lettres qui ne se repete pas (1) — Mot a 11 lettre dont une lettre ne se repete pas deux fois (1) — Plus grand mot sans 2 fois la meme lettre (1) — Quelles sont les mots qui contient de 12 lettre sans repetition ? (1) — Quel est le mot qui est constitue de 11 lettres sans repetition dans le meme mot (1) — Un mot de dix lettre sans repetition (1) — Le plus long mot francais sans repetition de lettre (1) — Mot de 12 lettres sans repetition (1) — Mot sans 2 fois la meme lettre (1) — Mots longs sans repetition de lettre (1) — Mot de douze lettre sans repetition (1) — Astuce mathematique circonference de la terre (1) — Donner le mot en douze lettre qui ne se repete ps (1) — Quel est le mot le plus long a 11 lettres et que les lettres ne se repete plus dans se mot? (1) — Un mot de 13 lettre dont chaque lettre n est pas r?p?t? (1) — Quel est le mot qui contient 11 lettre dont les lettres ne sont pas repete (1) — Un mot compose de 11 lettre et qui ne se repete (1) — Un mot sans lettre repete deux fois (1) — Mot sans la meme lettre (1) — Un mot avec 11 lettres pas de repetition des lettres (1) — Quel est le mot francais constitue de onze lettre qui ne se repete pas ? (1) — Le mot le plus long qui n a pas deux lettres repetes (1) — Un mot a onze lettres sans la repetition des lettres (1) — Mot en 1n lettre sans repetition (1) — Mots a 12 lettres sans la repetion des lettres. (1) — Un mot contient 11 lettre sans repetition (1) — 10 mots francaise qui contient onze lettres (1) — Mot ou nom a 11 lettres avec la non repetion des lettres. (1) — Le mot francais qui a 11 lettres a condition que une lettre ne se repete pas deux fois (1) — Donner un mot qui contien 11 lettres que auccun lettre se repete 2 ou 3 fois (1) — Donnee moi un peu un nom qui a onze lettre non repette (1) — Quel est le mot compose de 11lettre et aucune lettre n es repete deux foits (1) — Une phrase ne contenant aucune lettre repete (1) — Mots de 10 lettres et plus avec jamais 2fois la m?me lettre ? (1) — Les mots le plis long en fran?ais donc aucune lettre ne se repette (1) — Movies successices (1) — 11 lettre un mot sans repetition de lettre (1) — Le plus long mot du monde sans repetition de deux lettres (1) — Le plus long mot en francais sans repeter les lettres (1) — Mot en anglais long et sans deux fois la meme lettre (1) — Un mot de 12 lettre sans en repeter (1) — Plus long mot sans la lettre a (1) — Un exemple de mots de 11 l?ttre ou les mots ne se rep?te pas (1) — Enigme avec le mot but (1) — Mot le plus long en utilisant jamais deux fois la meme lettre (1) — Un mots 11 lettre qui ce repet pas (1) — Mots plus de 50 lettres (1) — Quel est le mot en fran?ais qui a onze(11) sans r?petitions des lettres ? (1) — Mot qui prend 11 lettre et repette pas (1) — Mot a 11 lettres sans repetition de lettres (1) — Quel es le mot qui contient 11 lettre et que les ne se r??p??te (1) — Quel est le mot qui a onze lettre dont les lettres ne se repetent pas? (1) — Egnime avec le mot but (1) — Plus long mot francais ne contenant pas deux fois la meme lettre (1) — Quel est le mot qui contient 12 lettres dans les lettres ne se repete pas (1) — Mot sans repetition de lettres (1) — Un mot de 9 lettres qui ne comporte que la meme (1) — Mot le plus long sans repetition de lettre en anglais (1) — Mot de 11 lettres sans la meme lettre (1) — Un mot en francais de 11 lettres dont aucune lettre n est repeter deux fois (1) — Quelle est le mot le plus long en francais sans repetition (1) — Enigme repetition (1) — Le mot le plus long en francais qui na pas de repetition (1) — Mot contient 12 lettres sans repeter (1) — Quelle est le mot le plus long en francais dont une lettre ne ce repete pas deux fois? (1) — Mot de 11 lettres sans repetition de lettre (1) — Le mot le plus long sans repetition de lettres (1) — Mot le plus long sans les memes lettres (1) — Le mots en francais qui a 11 lettres non repeter (1) — Plus long mot sans (1) — Le mot le plus long en francais sans lettre repetee (1) — 11 mot sans repetition (1) — Mot de 11 lettres avec des lettres qui ne se repetent pas (1) — Un mot en dix lettres qui ne se repetent pas (1) — Un mot form? 11 lettres sans repetition (1) — Un mot qui onze lettre que aucune de ce lettre ne ce repete (1) — Mots les plus longs et sans deux meme lettre (1) — 11 elttres mots sans meme lettre (1) — Un mot de 50 lettre (1) — Mot en francais de 10 lettres sans repetition des lettres (1) — Mots plus long sans repeter la meme lettre (1) — Le mot le plus long sans repeter (1) — Mot plus long sans repeter le lettre (1) — Un mot francais de 11 lettres mais aucune lettre ne se repette (1) — Un mot francais compose de 11 lettres non repetes (1) — Les mots ou les lettres ne se repettent pas (1) — Long mot francais sans repetition (1) — Le plus mot en francais sans repetition (1) — Mot long sans repetition des lettre (1) — Mot de 12 lettre sans repeter meme lettre 2 fois (1) — Enigme a repetition (1) — Repetition successiv de 3 mots dans un vers (1) — Enigme repitition de mots (1) — Mot long sans repetion (1) — Plus long mot sans repeter lettre (1) — Quel est le mot de 11 lettre dont aucune de ses lettre ne sont pas repete? (1) — Mot dans le dictionnaire avec une lettre sans se repeter (1) — Le plus long mot qui contient 26 lettres sans la repitition des lettres (1) — Le mot le plus long du francais sans repetition de lettres (1) — Irepetition successive (1) — Mot de 11 lettres dans lequel les lettres ne se repete pas (1) — Longue enigme (1) — Mots sans deux fois la meme lettre (1) — Repetition en 10 lettre (1) — Mot en 14 lettres sans repetition (1) — Mots de onze lettres (1) — Le mot francais le plus long sans e (1) — Une phrase avec 11 lettres sans se repeter (1) — Mot avec lettres sans repetition (1) — Plus long mot francais sans utiliser plusieurs fois la meme lettre (1) — Master mot expliquer (1) — Un mot qui a 11 lettre qui ne se repete pas (1) — Mots de 11 lettres sans repetition (1) — Quel est le mot le plus long en francais dont une lettre ne se repete pas deux fois (1) — Mot de 11 lettres sans deux fois la meme lettre (1) — Quel est le mots en francais qui peut contenir 11 lettres sans que la lettre ne se repete deux fois. a vous (1) — Quels sont les mots contenant 11 sans repetition de lettre (1) — Le master mot (1) — Mots de 11 lettres dont aucune ne se repete (1) — Quel est le mot francais dans lequel aucune lettre ne se repete? (1) — Mot sans repetition de lettre avec 13 lettre (1) — Mot le plus long sans deux fois la meme lettre (1) — Les mots a 12 lettres sans repetition de lettres (1) — Donn? moi un mot de onze lettre et qu aucune lettre ne se r?p?te (1) — Mot le plus long en francais sans meme lettre 2 fois (1) — Quel est le mot qui contient 11 lettres et dont les lettres ne se r?p?tent pas ? (1) — Le mot qui ne repete pas les lettre (1) — Mot de 11 lettres sans 2 fois la meme lettre (1) — Un mot de 10 letres avec une seule fois la lettre (1) — Le mots le plus dont les lettres ne se repete pas (1) — Le mot qui comporte 11 lettre qui ne se repetent pas (1) — Mots francais aucune lettre ne se repete (1) — Quel est le mots qui a onze lettre sans repetition de lettre (1) — Mot en 50 lettres (1) — Un mot en francais de 11 lettres sans repetition de lettre (1) — Mot 9 lettres sans lettre repetee (1) — Mots de 9 lettres sans repetition (1) — Le mot le plus long en francais sans repition de lettre (1) — Les mots a 8 lettre les lettres qui ne se repetent pas (1) — Quel est le mot qui contient 12 lettres dont les lettres sont repetees une seule fois (1) — Mot de 10 lettres aucune 2 fois (1) — Un mot de 13 lettre sans r?p?tition de lettre (1) — Mot francais 11 ne se repete (1) — Trois fois la meme lettre dans un mot (1) — Mots de 11 lettre sans repeter (1) — Le plus mot en fracais sans repetition (1) — Le mots le plus long dont les lettres ne se repete pas? (1) — Reflexion successive (1) — Un exemple d un mot qui a 11 lettres dont les lettres ne se repete pas (1) — Mot de 11 lettres sans repetition de deux lettres (1) — Mot en 9 lettres avec aucune meme lettres (1) — Quel sont les mots de 11 lettre dont aucune lettre n est repete? (1) — Un nom de 11 letres qui ne va pas se repete? (1) — Mot le plus long sans repeter les lettres (1) — Mots de dix lettres qui ne se repetent pas (1) — Le mot le plus long que les lettres ne se repetent pas (1) — Mot le plus repete par francais (1) — Le plus long mot sans repetition de lettre (1) — Veux un mot qui contient 11 lettre mais les lettre ne se repete pas (1) — Mot francais dans lequel aucune lettre ne se repete (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