Дипломная работа: Целочисленные функции
Название: Целочисленные функции Раздел: Рефераты по математике Тип: дипломная работа | ||||||||||||||||||
Федеральное агентство по образованию Государственное общеобразовательное учреждение высшего профессионального образования Вятский государственный гуманитарный университет Математический факультет Кафедра алгебры и геометрии Выпускная квалификационная работа «Целочисленные функции» Выполнила: студентка Научный руководитель: старший преподаватель Семёнов А.Н.
Рецензент:
Допущена к защите в ГАК Зав. кафедрой Вечтомов Е.М.
« »
Киров 2005 Содержание Введение. 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 Целые числа составляют костяк дискретной математики, и на практике часто приходится округлять дробные или произвольные вещественные числа до целых. До недавнего времени для обозначения целой части вещественного числа Цель данной работы — получить представление и навыки в обращении с «полом» и «потолком». Задачи работы: 1. Осветить теоретические аспекты данной темы: · Дать определение функций «пол», «потолок»; · Рассмотреть некоторые свойства этих функций; · Установить связь с непрерывными функциями; · Подсчитать количество целых чисел в заданных интервалах; · Рассмотреть определение спектра и его свойства; · Дать определение бинарной операции «mod» и рассмотреть приложение этой операции; · Рассмотреть на примере, как можно вычислить сумму, содержащую «полы». 2. Показать, как теория применяется на практике при решении задач. Глава 1. Целочисленные функции (теоретические факты)Договоримся через ëx û — наибольшее целое, меньше или равное x ; éx ù — наименьшее целое, больше или равное x . Из определения ясно, что
В целых точках неубывающие функции
Эта формула связывает все три обозначения Айверсона. Здесь и далее квадратные скобки используются для произвольного высказывания P в таком смысле: Функции
Из определений «пола» и «потолка» легко следуют свойства этих функций:
Разность между Иногда Докажем следующее свойство рассматриваемых функций:
Так как II. Связь с непрерывными функциями. Пусть
и
всякий раз, когда определены функции Докажем, что Случай 1: если Случай 2: если Докажем, что Случай 1: если Случай 2: если Рассмотрев
Например, при III. Количество целых чисел в интервалах: [a, b], [a, b), (a,b), (a, b]. Будем рассматривать указанные интервалы при условии Если a
и b
— целые числа, тогда интервал [a
, b
) содержит ровно
Поэтому интервал [a
, b
) содержит ровно Рассмотрим промежуток [a
, b
]. Имеем Рассмотрим (a
, b
), причём Подытожим установленные факты:
(9) Спектр некоторого вещественного числа a определяется как бесконечное мультимножество целых чисел: Spec (a
) = { Если Действительно, если предположить, что Пусть
Говорят, что спектры образуют разбиение всех целых положительных чисел, если любое число, отсутствующее в одном спектре, присутствует в другом; но никакое число не содержится одновременно в обоих. Пусть Если m
и n
— целые положительные числа, то неполное частное от деления n
на m
равно
Это определение можно распространить на произвольные вещественные числа:
при Дробную часть числа x
можно представить как Самым важным алгебраическим свойством операции ‘mod’ является распределительный закон:
Доказательство следует из (11):
Приложение операции ‘
mod
’:
разложение n
предметов на m
групп как можно более равномерных. Решение этого вопроса даёт тождества, справедливые при целых
Доказательство этих фактов можно найти в книге Р.Грэхем, Д.Кнут, О.Паташник «Конкретная математика» на с.106-108. Если в (15) заменить n
на ëmx
ûи применить правило (8), то получим тождество, которое справедливо при любом вещественном x
и натуральном
Глава 2. Целочисленные функции (применение к решению задач)Задача 1. Всякое натуральное число представимо в виде: Решение: Тогда Ответ: Задача 2. Как выглядит формула для ближайшего целого к заданному вещественному числуx ? В случае «равновесия» — когда x лежит ровно посередине между целыми числами — приведите выражение, округляющее результат: a) в сторону увеличения, т.е. до éx ù; b) в сторону уменьшения, т.е. до ëx û. Решение: Пусть вещественное число a) В этом случае до Û b) В этом случае до Û Ответ: a) Задача 3. Вычислите Решение:
Ответ: Задача 4. Докажите, что Доказательство:
Отсюда Итак, Задача 5. Доказать, что если f
(x
) — непрерывная, монотонно убывающая функция и f
(x
) — целое Þx
— целое, тогда Доказательство: 1 случай:
если 2 случай:
если Если Что и требовалось доказать. Задача 6. Решите рекуррентность при целом
Решение: Покажем, что База: Переход: пусть для некоторого номера Докажем, что
Что и требовалось доказать. Задача 7. Докажите принцип ящиков Дирихле: если n предметов размещены по m ящикам, то некоторый ящик должен содержать не меньше чем én / m ù предметов, а некоторый ящик должен содержать не более чем ën / m û. Решение: Предположим, что каждый ящик содержит меньше, чем én
/
m
ù предметов. Тогда наибольшее количество предметов в каждом ящике — это Значит, существует ящик, который содержит не менее чем én / m ù предметов. Предположим, что нет ящика, в котором не более, чем ën
/
m
û предметов, т.е. каждый ящик содержит более чем ën
/
m
û предметов. Тогда наименьшее количество предметов в каждом ящике — Значит, существует ящик, который содержит не более чем ën / m û предметов. Что и требовалось доказать. Задача 8. Покажите, что выражение Решение: 1 случай: x = (4k - 1)/2, k ÎZ Тогда Получим 2 случай:
x
¹
(4k
-1)/2, k
ÎZ, тогда Получим Итак, данное выражение округляет числа до ближайшего целого; в случае «равновесия» — когда x лежит ровно посередине между целыми числами — данное выражение округляет число в сторону чётного. Задача 9. Докажите, что Доказательство: Пусть Покажем, что Имеем Û Û Û Û Û Û Что и требовалось доказать. Задача 10. Пусть α
и β
— вещественные положительные числа. Докажите, что Spec(α
) и Spec(β
) образуют разбиение всех целых положительных чисел тогда и только тогда, когда α
и β
иррациональны и Решение: Пусть α и β — вещественные положительные числа. Докажем, что если Spec(α
) и Spec(β
) образуют разбиение всех целых положительных чисел, то α
и β
— иррациональные числа и Spec(α
) и Spec(β
) образуют разбиение всех целых положительных чисел, тогда
Þ Þ Þ Þ Рассмотрим Þ Докажем, что α
и β
иррациональны. Так как Если α
и β
оба рациональны, т.е. существует такое целое число m
, что Но никакое число не содержится одновременно в двух спектрах, образующих разбиение всех целых положительных чисел. Следовательно, α и β — иррациональны. Докажем обратное: если α
и β
иррациональны и
Так как и Отсюда получаем:
Получаем, что Что и требовалось доказать. Задача 11. Докажите, что Доказательство: · если тогда Получаем верное равенство · если Правая часть имеет вид: Преобразуем левую часть:
Получили, что Задача 12. Имеется ли аналогичное (16) тождество, в котором вместо «полов» используются «потолки»? Решение: Тождество (16) Аналогичное тождество для потолков получается из тождества (14) émx
ù = = Итак, получили тождество аналогичное данному:
Задача 13. Докажите, что Доказательство: При делении числа на 2 возможны только два различных остатка: либо 0, либо 1. · если · если Следовательно, равенство Найдём аналогичное выражение для Поскольку Так как При делении числа на 3 возможны только три различных остатка: либо 0, либо 1, либо 2. Если Если Если Решая систему
Итак, получаем следующую формулу:
Задача 14. Какому необходимому и достаточному условию должно удовлетворять вещественное число Решение: При любом вещественном Еслиb
— целое число, то функция Если b
— не целое число, то при Итак, если Ответ: b — целое число. Задача 15. Найдите сумму всех чисел, кратных x
, в замкнутом интервале [a
, b
], при Решение: Числа, кратные
Нам нужно вычислить следующую сумму:
В этой сумме
Задача 16. Покажите, что n
-й член последовательности 1,2,2,3,3,3,4,4,4,4,5,5,5,5,5,… равен Решение: В этой последовательности чисел меньших Оценим n :
Û Û Û Û Û Û Þ Следовательно, Задача 1 7 . Найдите и докажите связь между мультимножествами Spec(α ) и Spec(α /(α +1)), где α — некоторое положительное вещественное число. Решение: Число элементов в Spec(α ), которые не превосходят n :
Число элементов в Spec(α /(α +1)), которые не превосходят n :
Итак, получили, что Покажем на основе этого, что чисел равных При Пусть в Spec( Что и требовалось доказать. Ответ: чисел равных Задача 18. На шахматной доске Решение: Радиус окружности равен Горизонтальных прямых, не являющихся сторонами квадрата — ( Вертикальных прямых, не являющихся сторонами квадрата — ( Окружность каждую из указанных прямых пересекает в двух точках. Она не проходит через углы клеток. Действительно, если предположить, что данная окружность проходит через какой-нибудь угол клетки, то существуют такие целые числа Каждую клетку окружность пересекает в двух точках, а каждая точка пересечения принадлежит двум клеткам. Следовательно, окружность проходит через столько клеток доски, сколько имеется точек пересечения её с прямыми: Ответ: Задача 19 . Говорят, что f (x ) является репликативной функцией, если f
( при каждом целом положительном m . Укажите, какому необходимому и достаточному условию должно удовлетворять вещественное число c , чтобы функция f (x ) = x +c являлась репликативной. Решение: f (x ) = x +c — репликативна Û Û Û Û Ответ: ЛитератураР.Грэхем, Д.Кнут, О.Паташник. Конкретная математика. М.: «Мир» 1998. С 88- 124. |