Suite de conway (look and say sequence) - generateur

Soyez le premier à donner votre avis sur cette source.

Vue 13 560 fois - Téléchargée 397 fois

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

Codes Sources

A voir également

Ajouter un commentaire Commentaires
Ben, on a beson en réalité que de deux bits (ou 4 pour faire plus commode dans les fonctions de conversion) par carac donc on peut encore plus optimiser.
Mais après faut convertir en string et là, je ne suis pas sûr que ce sera efficace (sauf si tu ne veux que la nième ligne).

Mais figure toi que j'y avais déjà pensé quand je disais "J'ai une autre méthode en vue [...]"
Tu codes, tu testes, et si ça marche, on dira que c'est grâce à moi, OK ???? ;-)
Messages postés
4202
Date d'inscription
samedi 16 octobre 2004
Statut
Modérateur
Dernière intervention
13 juin 2020
37
chiffre disponible unique 1 2 et 3

le type string est trés lents.

si on code en hexa dans un byte array en exluant les 0 on pourrait non seulement raccourcirs la taille en octets et surrement gagner en vitesse.

en hexa ce la ferais donc :
01
11
21
12 11
11 12 21
31 22 11
13 11 22 21
11 13 21 32 11
31 13 12 11 13 12 21
13 21 13 11 12 31 13 11 22 11
11 13 12 21 13 31 12 13 21 13 21 22 21
31 13 11 22 21 23 21 12 11 13 12 21 13 12 11 32 11

en gros on as toujours une paire de chiffre et une longeur paire.

la ligne
1113213211
aurait pour valeur en char* :
31313133323133323131
soit deux fois plus longue (en memoire)

donc avec un array of byte ça devrait pouvoir passer.

ça te tente flo?
Oui mais le type string est connu pour être lent. En fait, Delphi permet d'utiliser le type string pour simplifier les tableaux de caractères tel qu'on les trouve en C (affreusement horrible, trois lignes pour concaténéer deux chaines ... allocation de mémoire et tout ^^). Mais du coup, on perd en performance alors dans ce cas, mieux vaut revenir aux primitives avec les PChar et compagnie ..
Sinon:
Tmp := Format('%s%s', [Tmp, Line[j]]);
est peu performant.
On préfèrera la version "normale", à savoir : Tmp := Tmp + Line[j];
Ton code à l'avantage de pouvoir changer la ligne de départ, c'est déjà ça ^^ (n'essaye pas avec "22" lol).
Bon, vais me coucher moi ...
Messages postés
1724
Date d'inscription
vendredi 27 décembre 2002
Statut
Modérateur
Dernière intervention
15 décembre 2020
8
Ca m'a l'air net et sans bavures, avantage Florenth.
Mon code est largué, mais alors très très loin derrière.
Je laisse à ceux qui ont des configs musclées le soin d'analyser finement.
Chez moi, à partir de 40 lignes, mon proc' est à deux doigts de l'infarctus...
Bon, pour ceux qui voudraient tester sans écrire eux mêmes les fonctions de chronomètrage, voici mon programme de test (inclue les fonctions de f0xi, Forman, japee (la dernière) et moi).
Ici : http://www.filefactory.com/file/00eef4/
Afficher les 63 commentaires

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.