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

Содержание

Введение. 3

Глава 1. Целочисленные функции (теоретические факты) 4

I. Определения. 4

II. Связь с непрерывными функциями. 5

III. Количество целых чисел в интервалах: [a, b], [a, b), (a,b), (a, b] 7

IV. Спектры. 8

V. ‘Mod’: бинарная операция. 9

Глава 2. Целочисленные функции (применение к решению задач) 11

Литература. 28 Вве

дение

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

До недавнего времени для обозначения целой части вещественного числа использовалась запись . Но в начале 60-х годов Кеннет Э.Айверсон предложил в этом случае писать и дал удачное название этому обозначению: «пол». Для обозначения верхнего целого он предложил запись и назвал её «потолком», а для квадратных скобок нашёл новое применение. Предложенная Айверсоном нотация оказалась настолько удачной, что за рубежом старое обозначение уже практически не встречается. С появлением русского издания книги Р.Грэхем, Д.Кнут, О.Паташник «Конкретная математика» эта нотация становится популярной и в России.

Цель данной работы — получить представление и навыки в обращении с «полом» и «потолком».

Задачи работы:

1. Осветить теоретические аспекты данной темы:

· Дать определение функций «пол», «потолок»;

· Рассмотреть некоторые свойства этих функций;

· Установить связь с непрерывными функциями;

· Подсчитать количество целых чисел в заданных интервалах;

· Рассмотреть определение спектра и его свойства;

· Дать определение бинарной операции «mod» и рассмотреть приложение этой операции;

· Рассмотреть на примере, как можно вычислить сумму, содержащую «полы».

2. Показать, как теория применяется на практике при решении задач.

Глава 1. Целочисленные функции (теоретические факты)

I. Определения.

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

ëxû — наибольшее целое, меньше или равное x;

éxù — наименьшее целое, больше или равное x.

Из определения ясно, что , . Отсюда следует, что

(1)

В целых точках неубывающие функции и совпадают, т.е. Û — целое Û . А если они не совпадают, то они отличаются на 1, т.е.

[- не целое] (2)

Эта формула связывает все три обозначения Айверсона. Здесь и далее квадратные скобки используются для произвольного высказывания P в таком смысле:

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

, (3)

Из определений «пола» и «потолка» легко следуют свойства этих функций: и

(4)

Разность между и называется дробной частью x и обозначается

Иногда называется целой частью , поскольку .

Докажем следующее свойство рассматриваемых функций:

(5)

Так как равно либо 0, либо 1, то равно либо , либо .

II. Связь с непрерывными функциями.

Пусть — некоторая непрерывная монотонно возрастающая функция, обладающая тем свойством, что — целое число Þ — целое число. Тогда

(6)

и

(7)

всякий раз, когда определены функции,,.

Докажем, что

Случай 1: если , тогда .

Случай 2: если , тогда (в силу того, что функция монотонно возрастающая), а так как функция «пол» — не убывающая, то . Предположим, что , тогда существует такое число , что и (в силу непрерывности функции). Из условия следует, что — целое число. Это противоречит тому, что между и нет целых чисел. Значит, .

 Скачать реферат