Pangramme autodescriptif
Un article de Wikipédia, l'encyclopédie libre.
Un pangramme autodescriptif est une phrase contenant toutes les lettres de l'alphabet (pangramme) et exprimant une proposition vraie sur elle-même (autodescriptif).
Sommaire |
[modifier] Exemples
| « 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. »
— oulipo |
| « Jugez que ce texte renferme l’alphabet, dix voyelles, k et w. »
— Thérèse Amiel |
[modifier] 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.
[modifier] 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. Se retrouve dans le domaine de l'electro dynamique industriel et releve un peu de la methode essaie erreur utilisé principalement pour trouver le P"I"D de la machine
[modifier] Méthodes plus rigoureuses
[modifier] 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é dans un cycle.
[modifier] 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 l'adressage associatif (hashs). Elle consomme davantage de place en mémoire aussi, mais les mémoires actuelles d'un gigaoctet et plus ne rendent pas cette question aussi critique que dans le passé.
