Путеводитель для влюбленных в математику Шейнерман Эдвард

Глава 10

Факториал!

Сколькими способами можно расставить ваши книги на полке? Разумеется, это зависит от того, сколько у вас книг. Начнем с простейшего примера. Допустим, ваша библиотека насчитывает всего три книги с незамысловатыми названиями A, B и C.

Вначале решим, какую книгу поставить с левого края. Пусть это будет A. В таком случае остается всего два варианта расположения книг на полке: ABC и ACB. То есть, когда A стоит слева, существует две комбинации.

Если поставить на левую позицию книгу B, тогда снова возможны два варианта: BAC и BCA. Если слева стоит книга C, появляются еще две комбинации: CAB и CBA.

В общей сложности есть шесть вариантов расстановки книг:

ABC, ACB, BAC, BCA, CAB, CBA.

Теперь представим, что у наспоявилась четвертая книга: D. Сколькими способами можно расставить книги теперь? Используем тот же метод. Для начала решим, какую книгу поставить слева; пусть на первый раз снова будет A. Оставшиеся три книги, как мы знаем, можно расставить шестью способами – только что мы обосновали, почему это так.

Точно так же есть шесть способов расположить оставшиеся книги, если слева будет B, C или D. В общей сложности получается 6 4 = 24 способа. Вот они:

Прежде чем мы перейдем к вопросу о произвольном количестве книг, давайте проанализируем вариант с пятью книгами: A, B, C, D и E. Как и раньше, вначале решаем, какую книгу поставить на крайнюю левую позицию. Если это A, у нас остается четыре книги. Сколькими способами можно их расставить? Мы уже выяснили, что таких способов 24. Еще 24 способа появляется, если на крайней левой позиции стоит B. То же самое для C, D и E. Итого в совокупности 24 + 24 + 24 + 24 + 24 = 120.

Каков был наш путь решения проблемы пяти книг? Есть пять вариантов, какую книгу поставить на крайнюю левую позицию. Когда она уже там, остаются четыре книги. Таким образом, количество вариантов для пяти книг в пять раз больше, чем количество вариантов для четырех. Давайте запишем это на математическом языке.

Пусть A₅ – количество вариантов расстановки пяти книг. Мы получаем формулу:

A₅ = 5 A₄.

Здесь A₄, как вы догадались, – количество вариантов для четырех книг.

Как найти A₄? Да точно так же! Слева может быть одна из четырех книг; в каждом случае останется три книги и соответствующее количество вариантов их взаиморасположения. Мы получаем:

A₄ = 4 A₃.

Соответственно, A₃ = 3 A₂. Количество вариантов для двух книг (куда уж проще) составляет A₂ = 2 A₁, где, разумеется, A₁ = 1.

И что же мы имеем?

A₅ = 5 A₄ = 5 4 A₃ = 5 4 3 A₂ = 5 4 3 2 A₁ = 5 4 3 2 1 = 120.

Теперь все ясно и с общим случаем. Количество способов расставить N книг на полке:

N (N – 1) (N – 2) … 3 2 1. (A)

Выражение (A) носит название N факториал. Факториал обозначают восклицательным знаком: N!. Например, 6! = 6 5 4 3 2 1 = 720.

Если мы задались целью вычислить значение 10! самый простой путь – перемножить числа от 1 до 10 и получить:

10! = 10 9 8 7 6 5 4 3 2 1 = 3 628 800.

Но для подсчета 20! придется перемножать двадцать чисел. А вычислять 100! таким манером – просто каторжный труд. Есть ли какой-нибудь быстрый способ[101]?

Красивая, но никуда не годная с точки зрения реальных вычислений идея состоит в том, чтобы определить 10! через 9!. Это же «проще простого»:

10! = 10 (9 8 … 3 2 1) = 10 9!.

Для произвольного значения N мы имеем:

N! = N [(N – 1) (N – 2) … 3 2 1].

Иными словами,

N! = N (N – 1)!. (B)

Формула (B) чудесна, но она мало помогает при вычислении, скажем, 20!. Мы должны вычислить 19! и умножить его на 20. Само собой, она подсказывает, как вычислить 19!: для этого надо посчитать 18!. А затем умножить на 19. В конце концов нам придется перемножать все целые числа от 1 до 20.

Вот бы найти способ побыстрее… Есть ли основания предполагать, что мы можем ускорить вычисления? Да, и про это нам говорят треугольные числа[102] – суммы вида:

1 + 2 + 3 + … + N.

Например, пятое треугольное число равно 1 + 2 + 3 + 4 + 5 = 15. Обозначим T_N треугольное число, представляющее собой сумму N элементов:

T_N = N + (N – 1) + (N – 2) + … + 3 + 2 + 1.

Например:

T₁₀ = 10 + 9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 = 55.

Это похоже на факториал, но со сложением вместо умножения. Есть ли способ посчитать T₁₀, не складывая все десять чисел?

Есть хорошая новость: да, такое возможно, и доказательство выглядит просто и элегантно. Запишем сумму первых десяти целых положительных чисел в возрастающем и убывающем порядке:

Если мы сложим все эти 20 чисел, результат будет равен удвоенному T₁₀. Но мы не станем сразу суммировать числа по горизонтали. Для начала сложим их попарно по вертикали:

В нижней строке все элементы равны 11, потому ответ прост[103]: 11 10 = 110. Теперь поделим этот результат пополам: T₁₀ = 110 / 2 = 55.

Как мы будем действовать в общем случае? Для вычисления T_N запишем целые числа от 1 до N в возрастающем и убывающем порядке и сложим пару в каждом столбце:

В нижней строке N элементов, каждый равен N + 1; таким образом, их сумма равна N (N + 1). Поскольку это «двойная порция» T_N, получается:

Для вычисления T₁₀₀ нет необходимости складывать сотню чисел. Нужно лишь посчитать:

(100 101) / 2 = 5050.

Вот и ответ.

Существует ли простая, элегантная формула вычисления факториала? Увы, нет. Однако есть формула для вычисления приближенного значения факториала, выведенная Джеймсом Стирлингом[104]:

Эта формула включает два замечательных числа, о которых шла речь в предыдущих главах: 3,14159, представляющее собой частное от деления длины окружности на ее радиус (см. главу 6), и число Эйлера e 2,71828 (см. главу 7).

Точность формулы Стирлинга возрастает при больших значениях N. Например, для N = 10 факториал 10! = 3 628 800, а вычисления по формуле (C) дают 3 598 695,6187. Погрешность – всего около 0,8 %.

Для N = 20 мы получаем:

20! = 2 432 902 008 176 640 000.

По формуле (C):

20! = 2 422 786 846 761 133 393,6839075390.

Погрешность равна около 0,4 %. Если мы перепрыгнем к N = 1000, погрешность составит менее 0,01 %.

Число 145 называют факторионом, потому что оно обладает волшебным свойством. Если мы сложим факториалы составляющих его цифр, то получим то же самое число:

1! + 4! + 5! = 1 + 24 + 120 = 145.

Числа 1 и 2 тоже являются факторионами (но не ноль, как мы увидим чуть позже). Существует всего четыре факториона. Попробуйте самостоятельно найти четвертый.

Это сложновато без компьютерной программы. Ответ приведен в конце главы.

Многие испытывают необоримое желание ответить: «0! равен нулю!» (Второй восклицательный знак всего лишь подчеркивает экспрессивность этой фразы.) Первый множитель в N! равен N, а умножение на ноль дает ноль. Однако математики договрились, что 0! = 1, и я завершу главу разъяснением этого факта.

В главе 1 мы обсудили концепцию пустого произведения – умножения при отсутствии элементов. Факториал нуля – пример пустого произведения. Для любого N факториал представляет собой результат перемножения N элементов. Это ясно для положительных значений N, но это верно и для N = 0. По определению, при подсчете N! мы перемножаем все целые числа от 1 до N. В случае N = 0 таких чисел просто-напросто нет, и произведение оказывается пустым. По договоренности, пустое произведение равно 1.

А вот еще одно обоснование того, почему 0! = 1. При подстановке N = 1 в формулу (B) мы получаем:

N! = N (N – 1)! => 1! = 1 0!

Поскольку 1! = 1, мы получаем 0! = 1.

А теперь давайте вернемся к расстановке книг на полке. Сколькими способами можно расставить на полке ноль книг? Есть один-единственный вариант: оставить полку пустой.

Глава 11

Закон Бенфорда

Для нас очевидно, что все цифры сотворены равными. Нет, мы не имеем в виду «равными друг другу» – разумеется, нет! Но внутри нас теплится вера в то, что все десять цифр, от 0 до 9, играют одинаковые роли в мире чисел.

Печальная правда заключается в том, что числа могут быть такими же нескромными, как люди: они все стремятся к первенству. Представьте, что вам приглянулась вещь стоимостью 43,52 доллара. Какая из цифр кажется вам более значимой? Важнее всего для вас цифра четыре, а двойка на конце не играет почти никакой роли. Вы встревожитесь, если четверка вдруг изменится на девятку, а если изменится двойка, вряд ли вас это сильно взволнует.

Тот, кто ждет от Вселенной справедливости, должен верить, что у всех цифр одинаковые шансы сыграть значимую роль, – но бедный, бедный нолик! Он не становится первой значащей цифрой, честь выпала на долю других[105]. Все они стремятся быть значительней остальных настолько часто, насколько это возможно.

Мы верим, что цифры от 1 до 9 участвуют в математике на равных правах и каждая начинает одну девятую часть всех существующих чисел (примерно 11 %). Разумеется, не может быть большего количества чисел, начинающихся с двойки, чем с пятерки.

Ведь так?

Утверждение о том, что все цифры от 1 до 9 равно представлены в качестве первой значащей цифры, приобретает смысл, если иметь в виду определенный диапазон чисел: скажем, от 1 до 999 999. В этом случае все цифры от 1 до 9 одинаково часто занимают место первой значащей цифры.

Разумеется, на результат влияет, какой именно диапазон мы выбрали. Если мы посмотрим на другой ряд чисел, скажем от 1 до 19, то обнаружим, что здесь все цифры от 2 до 9 занимают первую позицию всего единожды, в то время как 1 становится первой значащей цифрой в 11 случаях.

Ради беспристрастности давайте возьмем какие-нибудь величины из внешнего мира. Мы должны быть аккуратными и не искать числа, сконцентрированные в узком диапазоне. Поэтому мы не станем брать такой параметр, как рост взрослого человека[106], ведь практически все результаты измерений будут начинаться с 1 или 2 (ничтожно малое количество людей имеет рост выше 299 или ниже 100 сантиметров).

Ради уверенности в том, что все цифры имеют одинаковые шансы стать первой значащей цифрой числа, мы будем вести измерения в широком диапазоне. Например, давайте зададимся вопросом, насколько велико население разных стран[107]. Это значение будет колебаться от миллиарда с лишним (Китай и Индия) до менее чем десяти тысяч (в случае с карликовым государством на коралловом острове Науру[108]). Вдобавок к численности населения давайте выясним следующие параметры для сотен государств:

– валовой внутренний продукт (в долларах США);

– количество аэропортов;

– площадь (в квадратных километрах);

– ежегодную выработку электроэнергии (в киловатт-часах);

– ежегодное потребление продуктов нефтепереработки (в баррелях);

– общую длину всех железных дорог (в километрах);

– количество телефонов.

Таким образом, мы соберем около 2000 параметров и затем подсчитаем, сколько чисел начинается с цифры 1, сколько – с цифры 2 и т. д. Вот что у нас получится:

Невероятно: чаще всего на первой позиции встречается цифра 1 (примерно в 30 % случаев) и реже всего – цифра 9 (меньше 5 % случаев)!

Мы призываем читателей повторить эксперимент самостоятельно: взять статистический справочник, выписать первые цифры длин рек, высот гор, курсов акций, среднего роста различных видов животных, количества слов в романах, производства риса в разных странах и т. д.

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

Такое неравномерное распределение первых значащих цифр известно как закон Бенфорда, названный в честь Фрэнка Бенфорда[109]. Он опубликовал статью об этом феномене в 1938 году, хотя необходимо отметить, что еще в 1881 году к такому же выводу пришел Саймон Ньюком[110].

Закон Бенфорда утверждает нечто большее, чем «единица на первой значащей позиции встречается чаще всего, а девятка – реже всего». Закон Бенфорда констатирует (при наличии большого количества данных) следующую частотность[111]:

Есть и другая область, где обнаруживается неравномерное распределение первых значащих цифр, – это знакомая всем таблица умножения[112]:

Среди 81 числа в этой таблице 18 начинаются на 1, а именно:

При этом всего 3 числа начинаются на 9:

Вот процентное соотношение первых значащих цифр в обычной таблице умножения.

Мы видим, что цифры поменьше встречаются чаще, чем цифры побольше, но частотность здесь не совсем такая, какую предсказывает закон Бенфорда.

Таблица умножения дает нам все возможные результаты умножения одного однозначного числа на другое от 1 1 до 9 9.

Давайте расширим этот принцип и переберем все варианты умножения трех однозначных чисел. Проделаем следующие вычисления[113]:

В общей сложности это дает 9 = 729 троек. Посмотрим, как часто встречаются разные цифры в первой позиции:

Нет резона останавливаться на перемножении трех чисел. Мы можем составить четырехмерные, пятимерные, шестимерные таблицы умножения и т. д. Давайте сразу посмотрим, что получится с десятимерной таблицей умножения[114]. Она содержит все возможные комбинации произведений десяти чисел от 1 до 9. Другими словами, мы проделываем следующие вычисления:

Занесем в таблицу, как много чисел начинается с 1, 2 и т. д.:

Мы увидим, что частотность первых цифр в этом случае уже хорошо согласуется с законом Бенфорда.

Перед тем как вникнуть в детали закона Бенфорда, давайте обратим внимание на одно его практическое применение.

Предположим, некий нечистый на руку человек подделывает налоговые декларации (меняет суммы, фабрикует баланс и т. д.). Короче говоря, он лжет и выдумывает числа, не имеющие отношения к реальности. Начальные цифры он выбирает случайным образом.

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

Сверхбольшие и сверхмалые числа удобно записывать в экспоненциальном виде. Например, число 12 300 000 в экспоненциальном представлении выглядит так: 1,23 10. Мы записываем число от 1 до 10, умноженное на степень 10. Основное число называется мантисса[115]. Например, мантисса 853 100 000 равна 8,531:

По определению, мантисса не может быть меньше одного и не может быть больше или равна десяти[116]: 1 мантисса < 10.

Мантисса поможет нам сформулировать усовершенствованный вариант закона Бенфорда. Грубо говоря, закон гласит, что среди большого количества измерений около 30 % чисел имеют первую значащую цифру 1, то есть имеют мантиссу меньше 2.

Уточняя закон Бенфорда, мы можем присмотреться к первым двум цифрам большого количества измерений и задаться вопросом: с какой частотой мантисса будет, скажем, меньше 1,7? Вот другая формулировка того же вопроса: с какой частотой первые две цифры будут 10, 11, 12, 13, 14, 15 и 16?

В более общем виде: для любого числа m между 1 и 10 мы обозначим f(m) долю чисел, чья мантисса меньше m.

Например, f(2) – доля чисел, начинающихся на цифру 1. Величина f(3) означает долю чисел с начальной цифрой 1 и 2. Такая запись поможет понять, как возрастают частоты в законе Бенфорда.

Как использовать такую форму записи для обозначения доли измерений с начальной цифрой, скажем, 4?

• Заметим, что запись f(4) не означает, что начальная цифра равна 4. Это может быть также 1, 2 или 3.

• Точно так же запись f(5) означает, что первые цифры могут быть 1, 2, 3, 4.

• Чтобы выяснить, сколько чисел начинается на цифру 4, вычтем одну величину из другой: f(5) – f(4). Тогда мы исключим числа с начальной цифрой 1, 2, 3.

Есть две особые величины: чему равно f(1) и f(10)? Подумайте минуту, прежде чем читать дальше.

Вспомним: f(m) обозначает долю чисел с мантиссой меньше m. В то же время 1 m < 10. Что из этого следует?

• Нет ни одного числа с мантиссой меньше 1. Таким образом, f(1) = 0.

• Мантиссы всех чисел меньше 10. Таким образом, f(10) = 1 (или, если вам угодно, 100 %).

Между этими границами величина f(m) возрастает. Чем больше чисел с мантиссой меньше m, тем больше f(m).

Следующий шаг – понять, как f(m) зависит от m. Но вначале мы рассмотрим общий случай перехода из одной единицы измерения в другую.

Мы собрали тысячи измерений длин в километрах и увидели закон распределения первых цифр. Если мы переведем километры в мили, распределение не изменится. Измерения внутреннего валового продукта в долларах США дают примерно такую же частотность первых цифр. Ничего не изменится, если мы будем измерять ВВП в евро (или британских фунтах, или российских рублях). Но давайте присмотримся к переводу ярдов в футы.

Предположим, мы измеряем огромное количество расстояний в ярдах и в футах и изучаем распределение первых цифр. Как много величин имеют первую значащую цифру 2? Это множество включает и 2,1, и 28, и 0,213, и 299,8 ярда. В обозначениях, которые мы приняли в предыдущем разделе, доля величин такого рода по отношению ко всем измерениям[118] равна f(3) – f(2).

А теперь переведем наши измерения в футы. Иными словами, просто умножим всё на 3. 2,1 ярда равны 6,3 фута. Измерения в ярдах с первой значащей цифрой 2 превратятся в измерения с первой значащей цифрой от 6 до 9, не включая 9. Вы удивлены?

Вначале может показаться, что, если первая значащая цифра величин в ярдах равна 2, первая значащая цифра величин в футах будет равна 6. Это не так: 2,8 ярда равны 8,4 фута. Если мантисса измерений в ярдах находится в пределах от 2 до 3 (не включая 3), мантисса тех же измерений в футах будет в пределах от 6 до 9 (не включая 9).

Какая доля измерений имеет первую значащую цифру 6, 7 или 8? Ответ[119]: f(9) – f(6).

Близится кульминация: мы имеем дело с одними и теми же измерениями в разных единицах длины, поэтому доля измерений в ярдах с мантиссой 2 будет равна доле измерений в футах с мантиссой 6, 7 или 8. Иными словами, f(3) – f(2) в ярдах равно f(9) – f(6) в футах. Посмотрите на рисунок. Оба прямоугольника символизируют всю совокупность наших измерений: первый прямоугольник – в ярдах, второй прямоугольник – в футах. Серая область в первом прямоугольнике обозначает измерения с мантиссой 2. Соответствующая область во втором прямоугольнике обозначает измерения с мантиссой 6, 7 или 8.

Важно понимать, что обе закрашенные области идентичны! Так что доля измерений в ярдах с мантиссой 2 равна доле измерений в футах с мантиссой 6, 7 или 8.

Рассмотрим более общий случай. Вообразим, что мы собрали множество измерений и хотим выяснить, сколько из них имеют мантиссу меньше определенного числа a. Доля величин, удовлетворяющих этому условию, равна f(a).

Мы переводим результаты в другие единицы измерения. Пусть коэффициент будет равен числу b[120]. Иными словами, если длина объекта в одних единицах измерения равна 23,5, в других она будет равна 23,5 b.

Напомню, что f(a) равно доле величин с мантиссой от 1 до a, не включая a. Те же величины в других единицах имеют мантиссу строго меньше ab[121]. Их доля равна f(ab).

На языке формул тезис о равенстве долей величин с мантиссой меньше a в одних единицах и с мантиссой меньше ab в других единицах выглядит так:

f(a) = f(ab) – f(b).

Или:

f(ab) = f(a) + f(b). (*)

Новый вопрос: какого рода функция удовлетворяет этому правилу и условиям f(1) = 0 и f(10) = 1?

Некоторые математические операции можно проделать наоборот. Например, мы возводим в квадрат какое-нибудь число: 6 = 36. А теперь проделываем обратную операцию – извлекаем квадратный корень: Для положительных чисел операции возведения в квадрат и извлечения квадратного корня обратны друг другу. Операция, обратная возведению в степень, называется извлечением логарифма.

Например, 10 = 10 000. Мы проделываем наоборот операцию возведения в степень и применяем логарифмическую функцию[123]:

lg(10 000) = 4.

Можно воспринимать логарифмическую функцию как ответ на вопрос: «В какую степень возводить?» В какую степень нужно возвести 10, чтобы получить некое число? Скажем, какая степень 10 дает 1000? Поскольку 1000 = 10 10 10 = 10, ответ равен 3. Иными словами, lg(1000) = 3.

Несложно уяснить, что происходит, когда мы возводим 10 в степень, равную целому положительному числу, – мы просто перемножаем 10 заданное число раз:

Если мы посчитаем нули в одной из степеней 10, то поймем значение логарифма:

lg(1 000 000 000) = 9.

Возведение 10 в дробную степень несколько сложнее. Ключевая идея здесь – понять, чему равно произведение 10^m и 10.

Чему равно произведение 10 10? Не бойтесь, перемножать десятки просто. Давайте распишем нашу формулу:

Каков результат? Нет нужды перемножать! Просто посчитайте, сколько раз встречается 10 в правой части формулы: одиннадцать. Иными словами,

10 10 = 10¹¹.

Таким образом, для целых положительных степеней

10^m 10 = 10^{m +} .

Это тождество называется законом умножения степеней.

Ключевая идея вычисления дробной степени – применение данного закона для любых показателей степени. Давайте посмотрим, к чему это приведет.

Возьмем 10^0,5. Мы можем не знать, чему оно равно, но нам известно, чему равно произведение 10^0,5 10^0,5. А именно:

10^0,5 10^0,5 = 10^{0,5 + 0,5} = 10.

Если умножить 10^0,5 само на себя, получится 10. Таким образом, 10^0,5 равно квадратному корню из десяти[124]:

Так мы можем посчитать все степени 10. На рисунке вы видите график функции 10^х при x от 0 до 1.

При каком значении x выполняется условие 10^х = 2? При взгляде на график функции 10^х кажется, что подойдет x = 0,3. Если мы возьмем калькулятор, то выясним: 10^0,3 1,99526… Близко, но не равно точно 2. Чуть-чуть увеличим степень. Попробуем x = 0,301; результат 10^0,301 1,99986… Ближе, но все еще мимо цели. Нам нужно число немного больше. Величина x должна быть равна 0,30102999566398114… Это и будет log(2). (Вы уже встречали такое число раньше. Отыщите его!)

Закон умножения степеней 10^m 10 = 10^{m +} можно переформулировать для логарифмов. Посмотрим, как такое сделать. Допустим, a = 10^m и b = 10.

Чему равен десятичный логарифм a? Это степень, в которую нужно возвести 10, чтобы получить a. Иными словами, lg(a) = m. Аналогично lg(b) = n.

Чему равен логарифм произведения ab? Мы знаем, что a = 10^m и b = 10. Таким образом, ab = 10^{m +} . В какую степень нужно возвести 10, чтобы получить ab? Ответ: m + n. На языке математических символов это выглядит так: lg(ab) = m + n.

Подытожим:

lg(a) = m,

lg(b) = n,

lg(ab) = m + n.

Отсюда мы выводим закон сложения для логарифмов:

lg(ab) = lg(a) + lg(b). (**)

Похоже, мы уже встречали эту формулу…

Давайте подытожим то, что мы узнали из предыдущих разделов. Мы определили функцию f(m) как долю тех величин среди большого количества измерений, мантисса которых меньше m. Эта функция удовлетворяет трем условиям:

f(1) = 0,

f(10) = 1,

f(ab) = f(a) + f(b).

Потом мы обсудили логарифмы и выяснили следующее:

lg(1) = 0,

lg(10) = 1,

lg(ab) = lg(a) + lg(b).

Другими словами, значения f при 0 и 10 совпадает со значением десятичного логарифма от тех же величин. Кроме того, f и логарифм подчиняются одному и тому же правилу в соответствии с формулами (*) и (**). На основе этих фактов (и чисто технической оговорки, что функция f непрерывна) математики могут доказать, что f представляет собой логарифмическую функцию.

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

Какая доля измерений имеет первую значащую цифру 1? Сформулируем вопрос иначе: какая доля этих величин имеет мантиссу меньше 2? Ответ равен f(2) = lg(2) 0,3010 = 30,1 %.

Какая доля величин начинается с 9? Ответ равен f(10) – f(9), так как мы должны вычесть из общего количества величин те, первая значащая цифра которых меньше 9.

Это дает f(10) – f(9) = lg(10) – lg(9) 1 – 0,9542 = 0,0458 = 4,58 %.

Когда-то я задавал вопрос о значении f(1,7). Теперь можно уверенно ответить:

f(1,7) = lg(1,7) 0,23 = 23 %.

Глава 12

Алгоритм

Шеф-повара с фантазией редко руководствуются точными рецептами. Скорее, они следуют за вдохновением. А повара-новички покорно выполняют все указания поваренных книг.

Точно так же водителям с хорошей ориентацией на местности не нужны карты или детальные инструкции, как добраться до места назначения. А неопытным автомобилистам необходимы пошаговые указания.

В этом плане компьютеры похожи на новичков. Скажем, если нужно сложить несколько чисел, они скрупулезно выполняют операцию за операцией, руководствуясь инструкциями программистов. Эти инструкции называют алгоритмами[125]. Компьютерные алгоритмы окружают нас повсюду: они высчитывают проценты для банков, определяют разрывы страниц в текстовых документах, превращают цифровые данные на DVD-диске в кино, предсказывают погоду, рыщут по интернету в поисках рецепта, включающего заданные ингредиенты, и дают советы, сверяясь со спутниками GPS, когда мы ищем дом с хитрым адресом.

Первый математический алгоритм, который изучает большинство людей, – как складывать числа. Когда нужно просуммировать в столбик 25 и 18, мы знаем: вначале нужно к 5 прибавить 8 (и запомнить результат: 13), записать 3 в колонке единиц, а 1 держать в уме. Затем сложить 2 и 1, увеличить результат на 1 и записать 4 в колонке десятков. Получится 43.

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

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

Итак, перед нами встает проблема: имеется стопка тетрадей, перемешанных в хаотичном порядке, необходимо разложить их по алфавиту. Как это сделать наилучшим образом?

Начнем с простой, но неэффективной идеи. Допустим, у меня учится 100 студентов. Я беру из стопки первую тетрадку и смотрю, должна ли она идти первой по алфавиту. Каким образом? Я сравниваю имена на всех тетрадках с именем на этой тетрадке. Если не повезло и тетрадка по алфавиту не первая, я кладу ее в самый низ стопки и начинаю сначала. Я стану действовать так, пока не обнаружу первую по алфавиту тетрадку. Тогда я переложу ее в новую стопку, где тетрадки будут лежать упорядоченным образом.

Дальше я вернусь к неупорядоченной стопке – сейчастам 99 тетрадей – и, как и раньше, начну искать первую по алфавиту тетрадку. Я возьму тетрадку сверху, сравню со всеми остальными и положу в самый низ стопки, если она не подойдет. Когда я найду искомую тетрадку, я положу ее во вторую стопку снизу.

Теперь у меня есть «всего-навсего» 98 тетрадей, и я повторяю все по новой: ищу первую по алфавиту тетрадь и кладу ее в низ второй стопки.

Сколько времени это займет?

Основная операция заключается в том, чтобы сравнить два имени и решить, какое следует первым по алфавиту[126]. Мы будем оценивать эффективность алгоритма по количеству сравнений, которые необходимо провести. У меня 100 учащихся; как долго мне придется сопоставлять имена и решать, какое идет первым?

В неупорядоченной стопке из 100 тетрадей я сравниваю первую с 99 остальными. Необходимо проделать эту операцию со всеми 100 тетрадями (не исключено, что искомая лежит в самом конце). Поиск первой по алфавиту потребует максимум 100 99 = 9900 сопоставлений.

Я кладу свою находку во вторую стопку и повторяю процедуру с 99 неотсортированными тетрадями. Я сравниваю верхнюю тетрадь с 98 оставшимися. Поиск второй по алфавиту тетради потребует максимум 99 98 = 9702 сопоставления.

Третья тетрадь потребует максимум 98 97 сравнений, четвертая – максимум 97 96. Не исключено, что придется проделать 100 99 + 99 98 + 98 97 + … + 2 1 = 333 300 сравнений.

Мы проанализировали худший случай[127]. На каждой итерации мы нашли максимум из возможного числа операций и посчитали, сколько их всего потребуется. Несомненно, такой результат настраивает нас на пессимистический лад и показывает, насколько неэффективным был наш алгоритм. Давайте попробуем что-нибудь другое.

Мы снова начинаем со стопки из 100 тетрадей, перемешанных случайным образом. Берем первые две тетради. Если они идут не в правильном порядке, меняем их местами (первая станет второй, вторая – первой). Если порядок верный, оставляем все без изменений. Дальше смотрим на вторую и третью тетрадь. Если порядок верный, идем дальше. Если нет, меняем их местами. Так мы действуем по этому алгоритму, пока не доберемся до конца стопки. Один заход требует 99 сравнений.

Когда мы дойдем до конца стопки, тетради с именами из начала алфавита сместятся вверх, а тетради с именами в конце алфавита сместятся вниз. Но одного захода может быть недостаточно. В худшем случае первая по алфавиту тетрадь изначально лежала в самом низу, и в первом заходе мы переместили ее всего-навсего на 99-ю позицию. В этом случае сортировка потребует 99 операций[128].