3. Целочисленные функции

ЦЕЛЫЕ ЧИСЛА составляют костяк дискретной математики, и нам часто приходится округлять дробные или произвольные вещественные числа в целые. Наша цель в этой главе — получить представление и навыки в обращении с подобными округлениями и узнать кое-что об их замечательных свойствах.

3.1 ПОЛ/ПОТОЛОК: ОПРЕДЕЛЕНИЯ

Начнем с настила пола и перекрытия потолка — определений для любого вещественного числа х функций наибольшего и наименьшего целого:

Эти обозначения, как и названия „пол“ и „потолок" были введены в обиход Кеннетом Э. Айверсоном в начале 60-х годов [4, с. 12]. Он обнаружил, что наборщики вполне могли бы обойтись имеющимися литерами ‘[’ и ‘]’, срезав их верхушки и основания. Предложенные им обозначения стали настолько популярными, что теперь скобки „пола“ и „потолка" можно встретить в любой статье без какого-либо пояснения. До недавнего времени чаще всего использовалась запись для наибольшего целого а для функции наименьшего целого подходящий эквивалент отсутствовал. Впрочем, некоторые авторы пытались писать — затея, обреченная на провал.

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

Один из подходящих способов получить представление о функциях пол и потолок — разобраться в их графиках, которые располагаются лесенкой выше и ниже линии „перил“ :

К примеру, из данного графика видно, что

поскольку

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

(Мы пользуемся обозначением подразумевая под этим «тогда и только тогда») А если они не совпадают, то потолок ровно на 1 выше пола:

Если же сдвинуть диагональную линию вниз на единицу, то она целиком окажется под функцией пол, так что точно так же Объединяя эти наблюдения, получаем, что

И, наконец, данные функции являются отражениями друг друга относительно обеих осей:

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

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

Для того чтобы не просто довольствоваться графической иллюстрацией неких фактов, а действительно доказать свойства этих функций, особенно полезны следующие четыре правила:

(Во всех четырех случаях считается, что — целое, а х — вещественное число.) Правила (а) и (с) суть немедленные следствия определения (3.1); правила суть те же самые с той лишь разницей, что данные неравенства переставлены так, что оказывается в середине.

Целочисленное слагаемое можно вносить и выносить в/за скобки пола (или потолка):

(Действительно, правило утверждает, что это равенство эквивалентно неравенствам Но аналоги этой операции — типа вынесения за скобки постоянного множителя — в общем случае недопустимы. Так, когда Это значит, что скобки пола и потолка недостаточно гибки, - мы счастливы уже тогда, когда удается вообще отделаться от их присутствия либо что-то сделать при их наличии.

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

Эти правила легко доказываются. Например, если то наверняка так как . И наоборот, если то непременно так как

Было бы здорово, если бы все четыре правила в (3.7) так же легко запоминались, как и доказывались. Каждое неравенство без пола или потолка соответствует такому же неравенству с полом

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

Разность между называется дробной частью х и в приложениях возникает столь часто, что заслуживает собственного обозначения:

Иногда называется целой частью х, поскольку Если вещественное число х может быть записано в виде , где — целое число, то на основании можно заключить, что

Равенство (3.6) не выполняется, если — вещественное число. Но, вообще-то, для имеются всего лишь две возможности. Если записать в виде то получим . А поскольку то оказывается, что в некоторых случаях — это , а в остальных — это