Aller au contenu
Omnikalc

Calculateur de nombre harmonique : H(n), collectionneur, pile de livres et tri rapide

Saisissez n pour obtenir le nombre harmonique H(n) et ses principales applications : les tirages pour collectionner n vignettes, le porte-à-faux d’une pile de livres et les comparaisons moyennes du tri rapide.

Mis à jour le
Vos paramètres

Valeur hors limites

Résultats

Nombre harmonique H(n) = 1 + 1/2 + ... + 1/n

7,4855

Tirages attendus pour collectionner n vignettes (n × H(n))
7 485,5
Porte-à-faux d’une pile de livres, en longueurs de livre (H(n) / 2)
3,743
Comparaisons moyennes du tri rapide (2(n+1)H(n) − 4n)
10 986
H(n) moins ln(n) (tend vers 0,5772)
0,5777

Le nombre harmonique H(n) est la somme 1 + 1/2 + 1/3 + … + 1/n, un nombre qui croît comme le logarithme. Le calculateur de nombre harmonique donne H(n) et trois usages classiques : les tirages pour collectionner n vignettes, le porte-à-faux d’une pile de livres et les comparaisons moyennes du tri rapide.

Comment se fait le calcul

  • Saisissez le nombre n de termes : pour une collection de vignettes, le nombre de vignettes différentes, pour une pile, le nombre de livres, pour un tri, le nombre d’éléments.
  • Le calculateur calcule le nombre harmonique H(n) = 1 + 1/2 + 1/3 + … + 1/n avec la formule asymptotique ln n + γ + 1/(2n) − 1/(12n²) + 1/(120n⁴), où γ = 0,5772 est la constante d’Euler-Mascheroni.
  • La formule est exacte à environ 8 chiffres dès n = 5, et l’erreur baisse vite quand n grandit.
  • Lisez le nombre harmonique et ses usages : le collectionneur de vignettes, le porte-à-faux d’une pile de livres et le coût moyen du tri rapide.

Exemple

Prenez n = 1 000. Le nombre harmonique est H(1 000) = ln 1 000 + 0,5772 + 1/2 000 − 1/12 000 000 = 7,4855. Un collectionneur qui veut les 1 000 vignettes différentes à partir de pochettes aléatoires a besoin en moyenne de 1 000 × 7,4855 = 7 485,5 tirages. Une pile de 1 000 livres identiques, chacun en équilibre sur le suivant, peut dépasser la table de H(1 000) / 2 = 3,743 longueurs de livre. Un tri rapide de 1 000 éléments fait en moyenne 2 × 1 001 × 7,4855 − 4 000 = 10 986 comparaisons. H(1 000) − ln 1 000 vaut 0,5777, proche de la constante d’Euler 0,5772.

Pourquoi c’est utile

Le calculateur aide les étudiants en probabilités, en informatique et en analyse, et les curieux, à calculer un nombre harmonique pour un grand n sans additionner tous les termes, et à voir où il apparaît. Il sert à l’analyse des algorithmes, à estimer la taille d’une collection, et au casse-tête de la pile penchée.

À savoir

Utilisez le résultat pour n supérieur ou égal à 5, où la formule est très précise. Pour un petit n, additionnez les inverses à la main. Rappelez-vous que le résultat du collectionneur est une moyenne : le nombre réel de tirages varie beaucoup, et les dernières vignettes prennent le plus de temps, puisque la dernière seule demande environ n tirages en moyenne.

Outils liés

Le calculateur du collectionneur de vignettes donne le détail du problème de collection avec les probabilités, celui de la moyenne harmonique utilise les inverses dans une moyenne, celui du logarithme donne ln n, et celui de la valeur espérée couvre les moyennes de variables aléatoires.

Questions fréquentes

Qu’est-ce qu’un nombre harmonique ?

Le nombre harmonique H(n) est la somme des inverses des n premiers entiers : 1 + 1/2 + 1/3 + ... + 1/n. Il croît sans limite, mais très lentement, comme le logarithme népérien : H(n) vaut environ ln n + 0,5772. La somme des 1 000 premiers termes n’est que de 7,49, et il faut environ 12 367 termes pour dépasser 10, et 1,5 × 10⁴³ termes pour atteindre 100.

Où apparaissent les nombres harmoniques ?

Ils apparaissent dans le problème du collectionneur de vignettes, où le nombre moyen de tirages pour obtenir les n vignettes est n × H(n). Ils donnent le nombre moyen de records dans une suite aléatoire, le coût moyen du tri rapide, le porte-à-faux d’une pile de blocs (le problème de l’empilement harmonique) et le temps moyen de nombreux processus aléatoires. À chaque fois, la somme des 1/k vient d’un temps d’attente ou d’une probabilité de 1/k.

Comment calcule-t-on H(n) sans faire la somme ?

Pour un grand n, la formule d’Euler-Maclaurin donne H(n) = ln n + γ + 1/(2n) − 1/(12n²) + 1/(120n⁴) − ..., où γ = 0,5772156649 est la constante d’Euler-Mascheroni. Le calculateur utilise les cinq premiers termes. L’erreur est inférieure à 1/(252 n⁶), ce qui est minuscule : pour n = 5 le résultat est 2,283334 contre 2,283333 exact.

La pile de livres dépasse-t-elle vraiment autant ?

En théorie oui : n blocs identiques empilés avec les meilleurs décalages atteignent un porte-à-faux de H(n) / 2 longueurs de bloc, et avec 4 blocs, il dépasse déjà une longueur de bloc. Le porte-à-faux croît sans limite, mais très lentement, comme la moitié du logarithme de n. En pratique, il faut un équilibre parfait, donc le résultat est la limite idéale, pas une recette de tour stable.

Ce calculateur vous a-t-il été utile ?

Merci pour votre avis !

Résultats indicatifs fournis à titre d'information. Ils ne remplacent pas l'avis d'un professionnel.