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