124
Возьмите калькулятор, посчитайте обе величины и убедитесь, что я не ошибся.
125
Слово алгоритм происходит от имени персидского математика Аль-Хорезми (IX в. н. э.).
126
Даже эту операцию можно разбить на еще более элементарные. Например, нужно решить, чью тетрадь положить первой – Алисы или Алекса. Я сравниваю первые буквы. Они совпадают. Тогда я сравниваю вторые буквы – они снова совпадают. Третья буква в имени Алисы – «и», третья буква в имени Алекса – «е». Следовательно, тетрадка Алекса должна идти первой.
127
Если мы вычислим среднестатистическое количество операций, то получим средний случай.
128
Описанную процедуру называют сортировкой пузырьковым методом. Диаграмма иллюстрирует один раунд алгоритма.
Обратите внимание: тетрадь A сместилась всего на одну позицию. Нам потребуется еще шесть раундов, чтобы она поднялась наверх.
129
Описанный метод называют сортировкой слиянием. Это хороший пример принципа «разделяй и властвуй»: сложная задача разбивается на несколько задач попроще, а затем решения объединяются.
130
Чарльз Понци – итальянский мошенник, создатель финансовой пирамиды в Бостоне в 1920 году. – Прим. пер.
131
Заметим, что пример не так прост, как кажется: первый раз слово «оскудение» обозначает состояние, а второй раз – процесс. – Прим. науч. ред.
132
Описание будет еще более точным, если мы формализуем процедуру соединения подмножеств, описанную выше.
133
Несколько простых примеров: НОД (10, 15) = 5; НОД (12, 16) = 4; НОД (13, 11) = 1; НОД (10, 20) = 10; НОД (17, 17) = 17.
134
Разложение на множители при поиске НОД (a, b) гораздо эффективнее, чем поиск делителей вплоть до меньшего из двух чисел a и b. Поиск простых множителей числа a потребует самое большее операций деления. Это значительное усовершенствование первоначального алгоритма, но в случае стозначных чисел даже наш новый метод становится уже чертовский сложной задачей.
135
Например, если a = 100 и b = 40, частное q = 2 и остаток c = 20. Иными словами, 100 – 2 × 40 = 20.
136
10 693 = 4 × 2220 + 1813.
137
2220 = 1 × 1813 + 407.
138
1813 = 4 × 407 + 185.
139
407 = 2 × 185 + 37.
140
В главе 6 мы познакомились с концепцией взаимно простых чисел. Вот альтернативное определение: число a взаимно простое с b, если НОД (a, b) = 1. Так как алгоритм Евклида позволяет эффективно вычислить НОД двух чисел, он также позволяет выяснить, являются ли два числа взаимно простыми.
141
Данный метод неэффективен, однако не безнадежен. Мы знаем, что 364 × 286 кратно тому и другому числу. Будем надеяться на то, что набредем на общее кратное поменьше.
142
Мы выведем эту формулу площади треугольника на основании того, что площадь прямоугольника со сторонами a и b равна a × b.
143
Вот другой способ вычислить площадь данного треугольника. Он расположен внутри прямоугольника площадью 8 × 12 = 96. Необходимо вычесть из того числа площади трех «лишних» прямоугольных треугольников. Посчитать их несложно. Площадь треугольника слева Площадь верхнего треугольника справа Площадь нижнего треугольника справа равна Общая площадь «лишних» треугольников 18 + 20 + 16 = 54. Вычитаем это число из площади прямоугольника и получаем искомую площадь нашего треугольника: 96 – 54 = 42.
144
Георг Пик (1859–1942) – австрийский математик, профессор Университета Карла-Фердинанда в Праге. – Прим. пер.
145
Как ни странно, некоторые из четырех центров могут лежать вне треугольника! Догадываетесь почему? Ответ – в конце главы.
146
Фрэнк Морли (1860–1937) – заведующий кафедрой в Университете Джонса Хопкинса в Балтиморе, главный редактор American Journal of Mathematics. Он доказал эту теорему в 1899 году, когда изучал свойства кривых, заданных кубическим уравнением. – Прим. пер.
147
Равнобедренным называют такой треугольник, где две стороны равны между собой.
148
Из теоремы Пифагора следует, что диагональ квадрата со стороной 1 равна √2. Дело в том, что диагональ квадрата рассекает его на два прямоугольных треугольника; длина их катетов равна 1, в то время как длина гипотенузы равна некоторой величине c. По теореме Пифагора c² = 1² + 1² = 2. Извлечение квадратного корня дает Об этом числе шла речь в главе 4.
149
Это доказательство было найдено Бхаскарой, индийским математиком XII века.
150
