Page d'accueil	encyclopedie-enligne.com en page d'accueil
Liste Articles: [0-A] [A-C] [C-F] [F-J] [J-M] [M-P] [P-S] [S-Z] | Liste Catégories | Une page au hasard | Pages liées

Pangramme autodescriptif

On nomme Pangramme autodescriptif une phrase contenant toutes les lettres de l'alphabet (pangramme) et exprimant une proposition vraie sur elle-même (autodescriptif).

Exemple

Exemple trouvé sur le Net :

Ce pangramme autodescriptif en hommage à Douglas Hofstadter, Lee Sallows, Jacques Pitrat, Nicolas Graner et Éric Angelini contient exactement dix-sept a, un b, onze c, huit d, trente-cinq e, cinq f, neuf g, six h, vingt-quatre i, deux j, un k, sept l, six m, vingt-six n, onze o, huit p, huit q, onze r, quinze s, vingt-sept t, dix-sept u, quatre v, deux w, neuf x, un y, et cinq z.

Lien : http://www2.iap.fr/users/esposito/oulipo5.html

(cela dit, vous avez le droit de vérifier quand même)

Comment trouver un pangramme autodescriptif ?

Le plus simple est d'utiliser un ordinateur, et un sous-programme ou une table qui puisse associer à chaque entier entre 0 et par exemple 50 son écriture en toutes lettres. Il suffit alors

• de tirer au hasard 26 nombres, soit 1 pour chaque lettre,
• de faire exprimer en lettres ce que l'on a tiré (« douze a, deux b », etc.)
• de compter le nombre d'occurrence de chaque lettre, et, s'il n'y a pas conformité, de recommencer l'opération avec ces 26 nouveaux nombres.
• s'il y a conformité, en revanche, imprimer le résultat.

Méthode empirique

Avec un peu de chance, on peut tomber ainsi sur un point fixe. Si on n'en a pas trouvé un au bout de par exemple 200 itérations, on peut soupçonner être dans un cycle. Le plus simple est de tirer à nouveau 26 autres valeurs et de retenter sa chance. En laissant travailler sa machine toute la nuit, on trouve quelques pangrammes autodescriptifs le matin en se levant.

Méthodes plus rigoureuses

Slow-fast

Il existe une méthode de détection de cycle qui se nomme méthode du slow-fast. Elle consiste grosso modo à faire le calcul en double à des vitesses différentes (le tableau A aura par exemple une itération par cycle et le tableau B deux itérations par cycle. Si à un moment quelconque A=B, comme 1 ne peut être égal à 2, cela signifie qu'à coup sûr on est entrés dans un cycle.

Signatures

On peut calculer pour chaque tableau que l'on obtient une signature (par exemple CRC ou MD5, et conserver à la fois tous les anciens tableaux et toutes les signatures associées. On ne procèdera à une comparaison réelle de tableaux que si leurs signatures sont identiques. Si les tableaux sont également identiques, alors on tire d'autres valeurs pour le calcul.

Cette méthode est plus rapide à implémenter comme à exécuter que le slow-fast, surtout dans un langage qui comme le Perl possède d'adressage associatif (hashs), mais consomme davantage de place en mémoire aussi.