Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
2.2 СУММЫ И РЕКУРРЕНТНОСТИ
Итак, мы разобрались, как выражать суммы с помощью того или иного причудливого обозначения. Но как надо действовать для нахождения значения той или иной суммы? Один из способов - заметить, что существует тесная связь между суммами и рекуррентностями. Сумма
эквивалентна рекуррентности
при . (2.6)
(Считайте, что — не просто отдельное число, а их последовательность, определенная для всех )
Следовательно, можно вычислять суммы в замкнутой форме, используя для этого методы решения рекуррентных соотношений в замкнутой форме, которые изучались в гл. 1.
К примеру, если есть некая постоянная плюс некое кратное n, то сигма-рекуррентность (2.6) приобретает следующий общий вид:
при . (2.7)
Действуя так же, как в гл. 1, мы находим, что , и т.д., а вообще искомое решение может быть записано в виде
, (2.8)
где и — коэффициенты при основных параметрах .
Репертуарный метод подсказывает попробовать подставить вместо простые функции от n в надежде найти такие постоянные параметры , при которых решение особенно просто. Подстановка дает , откуда
.
Подстановка дает , откуда
.
А подстановка дает , откуда
.
и мы получаем . Просто как дважды два.
Итак, если мы хотим вычислить сумму
то сигма-рекуррентность (2.6) сводится к (2.7) c , и ответом будет .
И обратно, многие рекуррентности могут быть сведены к суммам; в силу этого специальные методы вычисления сумм, которые мы изучим позже в этой главе, будут полезны и при решении рекуррентных соотношений, справиться с которыми иначе было бы трудно. Подходящий пример - рекуррентность, связанная с задачей о ханойской башне:
при .
(Еще проще:
Ее можно привести к частному случаю (2.6), если поделить обе части на :
при .
Теперь можно положить , получая
при .
Отсюда вытекает, что
(Обратите внимание, что член с не включен в эту сумму.) Сумма геометрической прогрессии будет выведена в этой главе позднее – она окажется равной . Следовательно, .
В этом выводе мы перешли от к заметив, что исходное рекуррентное соотношение можно было поделить на . Эта уловка — частный случай общего метода, с помощью которого фактически любую рекуррентность вида
(2.9)
можно свести к сумме. Суть данного метода состоит в том, чтобы домножить обе части на суммирующий множитель :
.
При этом множитель подбирается столь искусно, чтобы сделать равным . А теперь, если положить , то получим сигма-рекуррентность
.
Следовательно,
и решением исходной рекуррентности (2.9) является
(2.10)
(Величина сокращается, так что она может быть чем угодно, кроие нуля.)
Например, при n = 1 мы получаем
Но хватит ли нам сообразительности, чтобы найти требуемое ? Нет проблем: достаточно развернуть соотношение чтобы выяснить, что искомым суммирующим множителем является дробь
(2.11)
или любое подходящее кратное этой величины. В частности, для рекуррентности, связанной с задачей о ханойской башне, и ; общий метод, который мы только что вывели, утверждает, что является подходящим кандидатом на роль множителя, если мы хотим свести рекуррентность к сумме. Для того чтобы обнаружить сей множитель, не нужно искры вдохновения.
Как всегда, надо соблюдать осторожность, чтобы не поделить на нуль. Метод суммирующего множителя срабатывает всегда, когда все и все не равны нулю.
Применим эти соотношения к рекуррентности, которая возникает в связи с анализом «быстрой сортировки» — одного из наиболее популярных методов внутренней сортировки данных в компьютере. Среднее число выполняемых «быстрой сортировкой» шагов сравнения, когда она применяется к элементам данных, расположенным в случайном порядке, удовлетворяет рекуррентному соотношению
при ; (2.12)
(«Быстрая сортировка» была придумана Хоаром в 1962 г. [339].)
М-да... Это выглядит гораздо страшнее, чем встречавшиеся до сих пор рекуррентности: сюда входит сумма всех предыдущих величин, да еще деление на n. Попытка вычислить несколько первых значений даст нам кое-какую информацию (), но не избавит от чувства страха.
Однако сложность соотношения (2.12) можно снижать постепенно, сперва избавившись от деления, а затем - от знака Реализуя эту идею, домножим обе части рекуррентности на n, получив соотношение
при ;
а если заменим на , то
при ;
Теперь можно вычесть второе равенство из первого, и знак пропадает
, при
Между прочим, это соотношение справедливо и при , поскольку . Итак, исходное рекуррентное соотношение для сводится к гораздо более простому:
, при .
Явный прогресс. Теперь мы в состоянии подключить к делу суммирующий множитель, поскольку полученное рекуррентное соотношение имеет вид (2.9) с и и . Общий метод, изложенный на предыдущей странице, подсказывает нам, что нужно домножить все рекуррентное соотношение на нечто, кратное величине
(Мы начинали с в рекуррентности и основательно потрудились, чтобы избавиться от нее. Но затем после применения суммирующего множителя мы пришли к другой Так что же, суммы — это хорошо, или плохо, как?)
Тогда, согласно (2.10), решением является
Оставшаяся сумма очень похожа на величину, которая часто возникает в приложениях. В действительности она возникает столь часто, что заслуживает специального названия и специального обозначения:
(2.13)
Буква происходит от слова «harmonic», так что — это гармоническое число. Оно названо так потому, что -я гармоника, извлекаемая из скрипичной струны,—это основной тон, производимый струной длиной от длины исходной струны.
Изучение «быстрой сортировки» — рекуррентности (2.12) — можно завершить приведением к замкнутому виду, если мы сможем выразить через . Сумма в нашей формуле для есть
Ее можно без особого труда связать с суммой , заменив k на k-1 и изменив граничные условия:
Польный порядок! Найдена сумма, необходимая для завершения решения (2.12): среднее число выполняемых «быстрой сортировкой» сравнений, когда она применяется к n случайно расположенным элементам данных, есть
(2.14)
(А с правописанием польный беспорядок.)
И, как водится, убедимся в правильности первых значений: .
3 Целочисленные функции
Целые числа составляют костяк дискретной математики, и нам часто приходится округлять дробные или произвольные вещественные числа в целые. Наша цель в этой главе — получить представление и навыки в обращении с подобными округлениями и узнать кое-что об их замечательных свойствах.
3.1 ПОЛ/ПОТОЛОК: ОПРЕДЕЛЕНИЯ
Начнем с настила пола и перекрытия потолка — определений для любого вещественного числа х функций наибольшего и наименьшего целого:
(3.1)
= наибольшее целое, меньшее или равное х;
= наименьшее целое, большее или равное х.
Эти обозначения, как и названия «пол» и «потолок», были введены в обиход Кеннетом Э. Айверсоном в начале 60-х годов [4, с. 12]. Он обнаружил, что наборщики вполне могли бы обойтись имеющимися литерами '[' и ']', срезав их верхушки и основания. Предложенные им обозначения стали настолько популярными, что теперь скобки «пола» и «потолка» можно встретить в любой статье без какого-либо пояснения. До недавнего времени чаще всего использовалась запись '[х]' для наибольшего целого х, а для функции наименьшего целого подходящий эквивалент отсутствовал. Впрочем, некоторые авторы пытались писать ']х[' — затея, обреченная на провал.
Помимо многозначности в обозначениях, существует неоднозначность в существе этих функций. Так, в некоторых калькуляторах имеется функция INT, определяемая как при положительном х и как: при отрицательном х. Вероятно, создатели таких калькуляторов хотели, чтобы их функция INT удовлетворяла соотношению INT(—х) = —INT(x). Но мы останемся приверженцами наших функций пол и потолок, поскольку они обладают гораздо более привлекательными, чем это, свойствами.
Один из подходящих способов получить представление о функциях пол и потолок — разобраться в их графиках, которые располагаются лесенкой выше и ниже линии «перил» f (х) = х:
3
-3
f(x)0))
x
f(x)=x
x=e
x=-e
1
2
-3
-2
-1
3
-2
-1
1
2
К примеру, из данного графика видно, что
поскольку е = 2.71828....
Глядя на эту графическую иллюстрацию, можно отметить ряд фактов относительно полов и потолков. Прежде всего, поскольку функция пол лежит на и под диагональной линией f(x)= х, то; точно так же. (Впрочем, это и так ясно из определения.) В целых точках обе эти функции совпадают:
(Мы пользуемся обозначением подразумевая под этим «тогда и только тогда».) А если они не совпадают, то потолок ровно на 1 выше пола:
(3.2)
Если же сдвинуть диагональную линию вниз на единицу, то она целиком окажется под функцией пол, так что ; точно так же Объединяя эти наблюдения, получаем, что
. (3.3)
И, наконец, данные функции являются отражениями друг друга относительно обеих осей:
(3.4)
Таким образом, каждая из них легко выражается через другую. Это обстоятельство позволяет объяснить, почему функция потолок прежде не имела собственного обозначения. Но потолки встречаются столь часто, что заслуживают специальных знаков отличия, точно так же, как нами были присвоены специальные обозначения возрастающим, равно как и убывающим, степеням. У математиков издавна есть синус и косинус, тангенс и котангенс, секанс и косеканс, максимум и минимум – а теперь у нас есть как пол, так и потолок.
Для того чтобы не просто довольствоваться графической иллюстрацией неких фактов, а действительно доказать свойства этих функций, особенно полезны следующие четыре правила:
(3.5)
(Во всех четырех случаях считается, что n - целое, а х - вещественное число.) Правила (а) и (с) суть немедленные следствия определения (3.1); правила (b) и (d) суть те же самые с той лишь разницей, что данные неравенства переставлены так, что n оказывается в середине.
Целочисленное слагаемое можно вносить и выносить в/за скобки пола (или потолка):
, n — целое. (3.6)
(Действительно, правило (3.5(a)) утверждает, что это равенство эквивалентно неравенствам Но аналоги этой операции—типа вынесения за скобки постоянного множителя — в общем случае недопустимы. Так, , когда n = 2 и x = 1/2. Это значит, что скобки пола и потолка недостаточно гибки,— мы счастливы уже тогда, когда удается вообще отделаться от их присутствия либо что-то сделать при их наличии.
Оказывается, что имеется много случаев, когда скобки пола и потолка излишни и их можно либо вставлять, либо удалять — как нам угодно. Так, любое неравенство между вещественными и целыми числами равносильно неравенству с полом или потолком между целыми числами:
(3.7)
Эти правила легко доказываются. Например, если х < n, то наверняка так как . И наоборот, если , то непременно x< n, так как и
Было бы здорово, если бы все четыре правила в (3.7) так же легко запоминались, как и доказывались. Каждое неравенство без пола или потолка соответствует такому же неравенству с полом или потолком, но нужно дважды подумать, прежде чем решить, которое из двух годится.
Разность между х и называется дробной частью х и в приложениях возникает столь часто, что заслуживает собственного обозначения:
(3.8)
Иногда называется целой частью х, поскольку х =+{х}. Если вещественное число х может быть записано в виде х = n+, где n —целое число, а , то на основании (3.5(a)) можно заключить, что n = и ={х}.
Равенство (3.6) не выполняется, если n — вещественное число. Но, вообще-то, для имеются всего лишь две возможности. Если х и у записать в виде х = +{х} и у = +{у}, то получим = А поскольку , то оказывается, что в некоторых случаях — это а в остальных — это + 1.
3.4 «MOD»: БИНАРНАЯ ОПЕРАЦИЯ
Если m и n — целые положительные числа, то частное от деления n на m равно . Полезно обзавестись достаточно простым обозначением и для остатка от этого деления — обозначим его через 'n mod та'. Основная формула
позволяет выразить n mod m в виде . Это можно распространить на целые отрицательные числа, а фактически — на произвольные вещественные числа:
(3.21)
Тем самым 'mod' оказывается бинарной операцией точно так же, как являются бинарными операции сложения и вычитания. Неформально математики издавна использовали понятие mod, вычисляя разные величины по модулю 10, по модулю 2 и т.п., но оно утвердилось лишь в последние двадцать лет формально. Понятие— старое, обозначение —новое.
Когда х и у — вещественные положительные числа, смысл х mod у можно легко уловить интуитивно. Вообразим себя бегущими по кругу с длиной окружности у, точкам которой приписаны вещественные числа из интервала [0, у). Если, взяв старт в точке 0, пробежать некоторое расстояние х по окружности, мы остановимся в точке х mod у. (А пока мы бегаем, точка 0 встретится нам раз.)
Когда же х или у отрицательны, нужно внимательно вникнуть в определение, с тем чтобы точно выяснить, что в этом случае означает х mod у. Вот некоторые примеры с целыми x и у:
Число после 'mod' называется модулем, но никто пока еще не придумал, как назвать число перед 'mod'. В приложениях модуль обычно положителен, но данное выше определение сохраняет смысл и когда модуль отрицателен. В обоих случаях величине х mod у лежит между нулем и модулем:
А как насчет у = 0? Определение (3.21) оставляет этот вопрос открытым, с тем чтобы избежать деления на нуль, но для полноты можно положить
х mod 0 = х. (3.22)
Подобное соглашение сохраняет свойство х mod у всегда отличаться от х на величину, кратную у. (Может показаться более естественным сделать эту функцию непрерывной в 0, полагая x mod 0 = = 0. Однако в гл.4 увидим, что это сделало бы ее менее полезной. Непрерывность — не самая важная сторона операции mod.)
Мы уже сталкивались с одним замаскированным частным случаем операции mod, когда записывали число х в виде суммы его целой и дробной частей: х = + {х}. Дробная часть может быть записана также как х mod 1, потому что
х = + х mod 1 .
Обратите внимание, что в этой формуле круглые скобки не нужны: считается, что знак mod связывает операнды сильнее, чем знаки сложения или вычитания.
При определении операции mod использовалась функция пол, в то время как функция потолок не удостоилась равного внимания. Быть может, стоило бы воспользоваться функцией потолок для определения аналога операции mod типа операции
х mumble у = у — х;
(mumble — нечто невразумительное,— Ред.). в случае нашей аналогии с кругом это соответствует расстоянию, которое нужно добежать бегуну, преодолевшему расстояние х, чтобы попасть в исходную точку 0. Конечно же, необходимо более подходящее название, нежели 'mumble'. Но нашлось бы подходящее приложение — наверняка найдется и соответствующее название.
Самым важным алгебраическим свойством операции mod является распределительный закон:
с(х mod у) = (сх) mod (су) (3.23)
при любых вещественных с, х и у. (Те, кто предпочитает, чтобы знак mod связывал операнды слабее, чем знак умножения, могут и здесь убрать круглые скобки в правой части.) Этот закон легко получается из определения (3.21), так как
,
если (случаи с нулевыми модулями тривиальны). Четыре предыдущих примера с ±5 и ±3 дважды иллюстрируют этот закон при с = -1. Тождество типа (3.23) действует успокаивающе, ибо оно позволяет надеяться, что операция 'mod' определена надлежащим образом.
В оставшейся части этого раздела рассмотрим одно приложение операции 'mod', в котором она оказывается весьма полезной, хотя и не играет центральной роли. Рассматриваемая задача часто возникает в тех многочисленных ситуациях, когда надо разложить n предметов на m групп как можно более равномерно.
Предположим, например, что мы располагаем n короткими строками текста line 1, line 2 ..., которые хотелось бы разместить в m колонках. По эстетическим соображениям желательно, чтобы по высоте эти колонки располагались в убывающем порядке (фактически — в невозрастающем порядке), причем высота колонок должна быть примерно одинаковой—никакие две колонки не должны отличаться друг от друга более чем на одну строку текста. Если 37 строк текста разбиваются на пять колонок, то предпочтительно такое их размещение, как справа:
|
8 |
8 |
8 |
8 |
5 |
8 |
8 |
7 |
7 |
7 |
|
|
line 1 line 2 |
line 9 line 10 |
line 17 line 18 |
line 25 line 26 |
line 33 line 34 |
line 1 line 2 |
line 9 line 10 |
line 17 line 18 |
line 25 line 26 |
line 33 line 34 |
|
|
line 3 line 4 |
line 11 line 12 |
line 19 line 20 |
line 27 line 28 |
line 35 line 36 |
line 3 line 4 |
line 11 line 12 |
line 19 line 20 |
line 27 line 28 |
line 35 line 36 |
|
|
line 5 line 6 |
line 13 line 14 |
line 21 line 22 |
line 29 line 30 |
line 37 |
line 5 line 6 |
line 13 line 14 |
line 21 line 22 |
line 29 line 30 |
line 37 |
|
|
line 7 line 8 |
line 15 line 16 |
line 23 line 24 |
line 31 line 32 |
line 7 line 8 |
line 15 line 16 |
line 23 line 24 |
line 31 line 32 |
К тому же желательно распределить строки по колонкам следующим образом: вначале решается, сколько строк войдет в первую колонку, затем мы переходим ко второй, третьей и так далее — ведь именно таков порядок чтения. Распределение строк текста ряд за рядом обеспечило бы нас требуемым числом строк в каждой колонке, однако порядок их чтения оказался бы нарушенным. (Мы получили бы нечто подобное размещению справа, но в 1-й колонке оказались бы строки 1, 6, 11, ..., 36 вместо строк 1, 2, 3,..., 8.)
Хотя план размещения ряд-за-рядом неприемлем, он позволяет выяснить, сколько строк поместится в каждой колонке. Если n не кратно m, то в процессе размещения ряд-за-рядом выясняется, что удлиненные колонки должны вмещать а укороченные — строк каждая; в результате будет ровно n mod m удлиненных колонок (и, как выясняется, ровно n mumble m укороченных).
Теперь обобщим терминологию и поговорим о 'предметах' и 'группах' вместо 'строк' и 'колонок'. Только что мы выяснили, что первая группа должна вмещать предметов; следовательно, можно попробовать следующую схему последовательного распределения: для распределения n предметов по m группам при m > 0 поместить предметов в одну группу, а затем рекурсивно применить ту же самую процедуру для того, чтобы разместить n' = n - оставшихся предметов в m' = m — 1 прочих группах.
К примеру, если n = 314 и m = 6, то распределение происходит по такой схеме:
|
Оставшиеся предметы |
Оставшиеся группы |
|
|
314 |
6 |
53 |
|
261 |
5 |
53 |
|
208 |
4 |
52 |
|
156 |
3 |
52 |
|
104 |
2 |
52 |
|
52 |
1 |
52 |
Схема работает — мы получаем группы практически неизменного размера, несмотря на то, что делитель изменяется.
А почему она работает? В общем случае можно предположить, что n = gm + r, где q = и r = n mod m. Если r = 0, то процесс размещения прост: мы помещаем = q предметов в первую группу и заменяем n на n' = n - q, оставляя n' = qm' предметов для размещения в остальных m' = m - 1 группах. Если же r > 0, мы помещаем = q + 1 предметов в первую группу и заменяем n на n' = n – q – 1, оставляя n' = qm' + r – 1 предметов для последующих групп. Новый остаток r' заменяется на r' = r – 1, но q остается без изменений. Отсюда следует, что получится r групп с q + 1 предметами, за которыми следуют m – r групп с q предметами.
Сколько же предметов окажется в k-й группе? Для ответа на этот вопрос нам нужна формула, которая бы давала при kn mod m и в противном случае. Нетрудно убедиться, что требуемым условиям удовлетворяет формула
поскольку она сводится к q + , если, как и в предыдущем абзаце, записать n в виде n = qm + r (здесь q = . Получаем, что = [kr], если
Следовательно, можно записать следующее тождество, которое выражает разбиение n на m как-можно-более-равных частей в невозрастающем порядке:
. (3.24)
Это тождество справедливо при любом целом положительном m и при любом целом n (положительном, отрицательном или равном нулю). Мы уже сталкивались со случаем m = 2 в (3.17), правда, записанном в несколько ином виде:
Если бы мы пожелали, чтобы все части располагались в неубывающем порядке — когда меньшие группы предшествуют большим, — можно было бы действовать тем же способом, но с предметами в первой группе, получая соответствующее тождество:
. (3.25)
Тождества (3.25) и (3.24) можно обращать одно в другое, пользуясь либо соотношением (3.4), либо тождеством из упр. 12.
Теперь, если в (3.25) заменить n на и применить правило (3.11) для удаления полов внутри полов, то получится тождество, которое справедливо при любом вещественном х:
(3.26)
Это до некоторой степени удивительный результат, ибо функция пол является целочисленной аппроксимацией вещественнозначной величины — тем не менее, отдельное приближение слева равняется сумме их целой компании справа. Если считать, что — это, грубо говоря, в среднем, то левая часть, грубо говоря, равна примерно , в то время как правая часть — это приблизительно . Но сумма всех этих грубых приближений оказывается величиной точной!