Ce magnifique diagramme de Hass a l’inconvénient majeur de ne pas présenter les nombres de Hamming dans l’ordre.
Afin de perpétré la nouvelle rubrique des Misez Rapide – Accélérez, je vous propose, de mesurer les performances de nos vieux pockets et micro à la génération ordonnées des nombres de Hamming.
Les nombres de Hamming ont plusieurs dénominations ; en fonction de leur champ d’application se sont des nombres moches , des nombres cinq-mous ou de glyphes babyloniens.
Les mathématiques les définissent comme étant les entiers de la forme c'est-à-dire les entiers dont les seuls diviseurs sont 2, 3 ou 5.
Les 20 premiers Nombre de Hamming sont : 1 2 3 4 5 6 8 9 10 12 15 16 18 20 24 25 27 30 32 36
Un peu comme Dijkstra, Edsger W. l’avait fait en 1976 dans sont ouvrage A Discipline of Programming au chapitre n°17 intitulé "An exercise attributed to R. W. Hamming" ( Prentice-Hall, pp. 129–134, ISBN 978-0132158718 ), je vous propose de générer la séquence ordonnée de ces nombres sur nos Pockets et Micros préférés.
Evidemment, ce M.R.A. est en relation directe avec le M.P.O. n°67 qui partage le même thème. Mais, il n’en a pas le même objectif.
L’objectif de ce M.R.A. est de générer dans l’ordre et au plus vite la liste des nombres de Hamming.
Quel sera le temps mis par votre appareil pour afficher ou imprimer dans l’ordre les 10, 20, 50, 100, 200, 500 ou 1000 premiers nombre de Hammig ?
Votre technique permet-elle de déterminer en un temps raisonnable quel est le n-ième nombre de Hamming de la série.
Est-il possible de trouver le 1500ième, le 2000ième, le 5000ième , voir même le 10000ième ou le millionième ?
Vous pourrez pour cela mettre en œuvre tout algorithme de votre choix et de votre convenance qui utilisera ou non les multiples propriétés des Nombre de Hamming.
Vous pourriez utiliser, par exemple, l’une ou l’autre des méthodes suivantes:
- décomposer chaque entier en facteur premiers et les afficher/imprimer au fur et à mesure,
- construire par récurrence l’ensemble H des nombres de Hamming, sachant que si H est un ensemble composé uniquement de nombre de Hamming, alors 2.H, 3.H et 5.H sont également des ensembles de nombres de Hamming
- trouver les intonations justes de votre instrument de musique préféré et parcourir les gammes diatoniques afin d’en lister les harmoniques,
- retrouver les plaquettes d’argile que votre grand-père archéologue a remmenée d’Asie sumérienne et comprendre sont système de classement afin de remettre dans l’ordre les glyphes mésopotamiens qui y sont gravées,
- tirer au sort le résultat du programme,…
- Utiliser les résultats du MPO n°67
- utiliser un algorithme personnel, mais fort dynamique...
Afficher ou imprimer de longues listes prends du temps et consomme des ressources. Afin de faciliter l’évaluation nous ne mesurerons les temps d’affichage/impression que pour les listes contenant moins de 50 nombres.
A partir de 100 nombres, nous ne mesurerons que le temps déterminé pour trouver le n-ième élément de la série. Ce qui sera plus rapide et plus économique. Bien entendu, cela sous-entend que le programme testé est capable de déterminer tous les éléments de la série quelque soit leur coordonnée et qu’il n’y a pas de « trou ».
Quelque soit l’algorithme que vous déciderez d’implémenter dans votre calculette ou micro, n’oubliez pas de Miser Rapide et d’Accélérer.