В мир информатики # 96 (16–31 октября).
Семинар

Гармонические числа

Сумма при целом n 1 так часто встречается в анализе алгоритмов⁶, что специалистам понадобилось для нее специальное обозначение — Н_n. Буква Н в этом обозначении происходит от слова “harmonic”, так что Н_n — это гармоническое число. Оно названо так потому, что k-я гармоника, извлекаемая из скрипичной струны, — это основной тон, производимый струной, длина которой равна 1/k от длины основной струны [1].

Рассчитать значение Н_n при заданном n можно с помощью функции, которая на школьном алгоритмическом языке имеет вид:

алг вещ Гармоническое_число(арг цел n)

нач цел i, вещ сумма

сумма := 1

нц для i от 2 до n

сумма := сумма + 1/i

кц

| Значение функции:

знач := сумма

кон

Учитывая, что , можно применить прием, который в программировании называют “рекурсией” [2]. Создадим простую и логичную рекурсивную (использующую саму себя в качестве вспомогательной) функцию:

алг вещ Гармоническое_число(арг цел n)

нач

если n = 1

то

знач := 1

иначе

знач := Гармоническое_число(n — 1) + 1/n

все

кон

Нетрудно увидеть, что обе приведенные функции возвращают вещественное значение гармонических чисел.

Несколько более сложной задачей является получение гармонических чисел в виде простой дроби: 3/2, 11/6 и т.п.

Задание для самостоятельной работы

На известном вам языке программирования разработайте программы для получения гармонических чисел в двух вариантах вывода их на экран:

Во втором случае две функции не создавать. Программы, пожалуйста, присылайте в редакцию. Фамилии всех приславших правильные программы будут опубликованы, а лучшие ответы мы поощрим.

Литература

1. Грэхем Р., Кнут Д., Паташник О. Конкретная математика. М.: Мир, 1998.

2. Рекурсия. / “В мир информатики” № 5 (“Информатика” № 37/2003).

⁶ В будущем мы приведем несколько интересных примеров использования этой суммы.