1. Accueil
  2. Delphi / Pascal
  3. Sources Delphi / Pascal
  4. Sources Maths
  5. Suite de conway (look and say sequence) - generateur

Suite de conway (look and say sequence) - generateur

5/5 (63 avis)

Vue 15 178 fois - Téléchargée 428 fois

Télécharger le projet
Commenter

Description

Dans la rubrique on se détend, c'est l'été...
Ce code n'a qu'une prétention, c'est de vous divertir.
Il me semble que cette énigme est proposée par Bernard Werber dans son livre "Les fourmis", mais je n'arrive pas à la retrouver...

Bon.
Ceux qui connaissent déjà ne soufflent pas !
L'énigme se présente sous cette forme :

1
11
21
1211
111221
312211
13112221
1113213211
31131211131221
13211311123113112211
11131221133112132113212221
3113112221232112111312211312113211
1321132132111213122112311311222113111221131221

Il faut trouver la logique de cette succession de chiffres.

Il paraît qu'un enfant résoudra ce problème plus facilement qu'un adulte, surtout si cet adulte est trop calé en maths...
Bref, il faut essayer de renouer avec une certaine fraicheur de regard qui n'appartiennent qu'à l'enfance.
Mais quand on programme pour le plaisir, on est resté un enfant quelque part, non ?

Le code que je joins génère cette suite de chiffres. Il fournit donc forcément la clé de l'énigme... à regarder après avoir résolu le problème, donc.
Et ne trichez pas !

Zip joint pour mise en oeuvre facile.

Mise à jour du 17/08/06 :

Il s'agit en fait de la suite de Conway, Look and Say sequence en anglais, mais ça n'est plus une énigme dans ces conditions. Merci à CptPingu pour cette information.
J'ai revu le code afin qu'il soit un peu moins lent, mais il n'a pas la prétention de rivaliser avec ceux qui suivent sur cette page !
J'ai rajouté la possibilité de choisir le chiffre initial comme me le suggère Florenth.
Le nombre de lignes : c'est le nombre de lignes rajoutées à la ligne initiale, que ça soit clair.
Bonne continuation ;-)

Source / Exemple : 


procedure GenerateConwaySequence(const TS: TStrings; const n: Word = 12;
  const Init: Byte = 1);
var
  i, j: Integer;
  Line, Reading, Tmp: string;
begin
  with TS do
  begin
    Clear;
    BeginUpdate;
    Add(IntToStr(Init));
    for i := 0 to n -1 do
    begin
      Line := TS[i];
      Reading := '';
      Tmp := '';
      for j := 1 to Length(Line) do
      begin
        Tmp := Format('%s%s', [Tmp, Line[j]]);
        if (j = Length(Line)) or (Line[j + 1] <> Tmp[Length(Tmp)]) then
        begin
          Reading := Format('%s%d%s', [Reading, Length(Tmp), Tmp[1]]);
          Tmp := '';
        end;
      end;
      Add(Reading);
    end;
    EndUpdate;
  end;
end;

Conclusion :


A priori pas de bug, j'ai vaporisé au Raid action longue durée...
Télécharger le projet

Codes Sources

A voir également

Ajouter un commentaire Commentaires
florenth
12 août 2006 à 16:22
Ah oui pas mal.
J'ai mis à peine 1 minute pour trouver (sans lire le source) ^^ (ça veut dire que j'ai un esprit d'enfant - normal quoi !)

Par contre, pourque le programme ait plus d'utilité, j'aurais mis un peit bouton, qui quand on appuye dessus, afficherait l'explication (non pas de façon statique et mathématiques (mais est-ce bien des maths ?) mais de façon ... arrgh je ne peux pas le dire sans dévoiler la solution !

Surveille ton MP

Et il faurait aussi que ta fonction puisse faire varier le chiffre de début, ça aiderait certains à comprendre
cirec Messages postés 3833 Date d'inscription vendredi 23 juillet 2004 Statut Modérateur Dernière intervention 18 septembre 2022 50
12 août 2006 à 16:34
Ben ouais c'est d'une logique ...

Bon on me l'avais déjà fait :-)
mais c'est d'un "con"
si je ne suis pas trompé ce devrait être la ligne suivante :
11131221131211131231121113112221121321132132211331222113112211

bien :-)
@+
japee Messages postés 1727 Date d'inscription vendredi 27 décembre 2002 Statut Modérateur Dernière intervention 6 novembre 2021 8
12 août 2006 à 17:02
Tu ne t'es pas trompé, Cirec ;-) chut... laissons chercher les autres.
Florenth, bravo, mais c'est vrai que tu es un des plus jeunes d'entre nous (hormis moi, bien sûr, lol). J'ai lu ton MP, je vais étudier la question.
cs_Forman Messages postés 600 Date d'inscription samedi 8 juin 2002 Statut Membre Dernière intervention 6 avril 2010 1
12 août 2006 à 20:27
Je la connaissais aussi déjà celle là ;)
Mais étudier la suite ainsi définie est un vrai casse-tête:
je m'étais posé des questions dessus il y a quelques années: peut-on exprimer la longueur du n-ième terme de la suite en fonction de n? Ou au moins trouver un équivalent vers l'infini?

La conclusion est: je ne sais ni démontrer que la suite est de longueur croissante (en effet, sans rien dévoiler, on peut imaginer des termes tels qu'en calculant le terme suivant la longueur obtenue est strictement inférieure, par exemple 111333) ni même qu'elle n'est pas périodique (il existe en effet par exemple un mot de 2 caractères tel que le mot suivant est le même: 22). Et pourtant, j'y ai passé du temps, mdr...

Les seules choses que je sais démontrer sur cette suite (et c'est très facile à faire, ce sont des propriétés immédiates) c'est:
-elle ne contient que les 3 chiffres 1,2 et 3
-la longueur du n-ième terme est plus petite que (ou égale à) 2^n

J'ai réécrit l'algorithme pour calculer un des termes à partir du précédant, de façon à ce qu'il aille plus vite (moins de réallocation de mémoire):

function f(s:string):string;
var
p,q:PChar;
c,d,e:Char;
begin
SetLength(Result,2*Length(s));
p:=PChar(s);
q:=PChar(Result);
c:=p^;
repeat
e:='0';
repeat
Inc(p);
d:=p^;
Inc(e);
until d<>c;
q^:=e;
PChar(q+1)^:=c;
q:=q+2;
c:=d;
until c=#0;
SetLength(Result,Integer(q)-Integer(PChar(Result)));
end;

procedure FastGenereEnigme(const TS:TStrings;const n:Word=12);
var
a:Integer;
begin
TS.Clear;
TS.Add('1');
for a:=0 to n-1 do
TS.Add(f(TS[a]));
end;

Ca fonctionne si on considère que calculer le terme suivant de la suite va au plus doubler la longueur (d'où l'explication du SetLength(Result,2*Length(s))). Pour calculer le 50ième terme, GenerateEnigme met 25 secondes alors que FastGenereEnigme met 32 millisecondes... Ca démontre encore, s'il en était besoin, que les allocations de mémoire cachées rallentissent énormément le code: lorsqu'on écrit a+b (où a et b sont des chaînes de caractères) il y a une réallocation de mémoire pour stocker le résultat de la concaténation.

L'algorithme à optimiser est un bon exemple: je propose le challenge de celui qui donnera un algorithme (pour la fonction f) calculant le plus vite possible le 71ième terme de la suite (à partir du 72ème, le terme devient trop grand et provoque une exception EOutOfMemory chez moi). Record à battre: 7062 millisecondes pour calculer le 71ième terme de la suite. Bien sûr, pour que ça compte, il faut que les 2 algo soient lancés sur la même machine!

A vos claviers ;-)
japee Messages postés 1727 Date d'inscription vendredi 27 décembre 2002 Statut Modérateur Dernière intervention 6 novembre 2021 8
12 août 2006 à 21:06
Visiblement, Forman, tu es le gars qui aime aller au fond des choses.
J'avais pas réfléchi à toutes les implications mathématiques, toutes ces interrogations (et les angoisses) que ça soulève. Wouah...
Je trouve que ton code est plus beau que le mien (bouh).
Merci d'avoir amené un peu de grain à moudre à notre réflexion à partir de cette simple petite énigme.
Alors, quelqu'un relève le défi ?
(moi, j'ai comme un gros coup de fatigue, lol)
S'inscrire maintenant

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.

Le fait d'être membre vous permet d'avoir des options supplémentaires.

Du même auteur (japee)