Курсовая работа по «Методам решений рекуррентных соотношений»

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования

«ПЕРМСКИЙ ГУМАНИТАРНО-ПЕДАГОГИЧЕСКИЙ УНИВЕРСИТЕТ»

МАТЕМАТИЧЕСКИЙ ФАКУЛЬТЕТ

Кафедра высшей математики

 

 

 

Курсовая работа по дисциплине

МЕТОДЫ РЕШЕНИЯ РЕКУРРЕНТНЫХ СООТНОШЕНИЙ

 

                              

 

 

 

 

 

 

 

 

Пермь

2014

Введение

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

Здесь можно представить очень краткую (на 2-3 предложения) историческую справку и характеристику современного состояния исследуемого вопроса.

Методы исследования. В работе использованы методы анализа

теоретической информации, дискретной математики, построения и анализа

алгоритмов, теории автоматов

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

Если последовательность чисел или функций конечна, то для нахождения значений функций (например, суммы, произведения или n-ого члена) используется арифметический цикл, т.е. цикл, в котором заранее известно число повторений. Трудность при решении таких задач представляет нахождение самой рекуррентной формулы. Я предлагаю ученикам общий подход к получению рекуррентной формулы, опираясь на метод математической индукции.

Цель исследования – изучение методов решения некоторых рекуррентных соотношений.

В связи с поставленной целью необходимо решить следующие задачи:

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

Объектом курсового исследования являются рекуррентные соотношения.

Предмет исследования – методы их решения.

 
 

1.​ Основные понятия

1.1.​ Примеры задач, приводящих к рекуррентным соотношениям

Рассмотрим некоторые задачи, приводящие к рекуррентным соотношениям.

Одной из них является - Числа Фибоначчи. Итальянский математик Фибоначчи привел следующую задачу: пара кроликов раз в месяц дает приплод из двух крольчат (самки и самца), причем навоженные крольчата через два месяца после рождения уже приносят приплод. Сколько кроликов появиться через год, если в начале года была одна пара кроликов?

Из условия задачи следует, что через месяц будет две пары кроликов. Через два месяца приплод даст только первая пара кроликов, и получиться 3 пары. А еще через месяц приплод дадут и исходная пара, и пара кроликов, проявившая два месяца тому назад. Поэтому всегда будет 5 пар кроликов.

Обозначим через f(n)количество пар кроликов по истечении nмесяцев сначала ода. Мы видим что через n+1 месяцев будет f(n) еще сколько новорожденных пар кроликов, сколько было в конце месяца n-1, то есть еще f(n-1)пар кроликов. Иными словами, имеет место рекуррентное соотношение

f(n+1)=f(n)+f(n-1)

Так как по условию f(0)=1 иf(1)=2, то последовательность находим f(2)=3, f(4)=8 и т.д. Числа f(n) называется числами Фибоначчи.

Задача о Ханойской башне. Рассмотрим головоломку под названием ханойская башня, которую придумал французский математик Эдуард Люка в 1883г. Башня представляет собой восемь дисков, нанизанных в порядке уменьшения размеров на один из трех колышков (рис. 1)

 

 

 

Рис.1. Ханойская башня

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

Пусть f(n)-минимальное число перекладываний nдисков с одного колышка на другой по правилу Люка. Очевидно, что f(0)=0,f(1)=1,а f(2)=3.В случае трех дисков, два верхних диска переносятся на один из колышков, затем переносится третий диск на него помещаются два других. Таким образом, общее правило перемещений заключается в следующем. Сначала перемещается n-1 меньших дисков на один из колышков-этоf(n-1) перекладываний. Затем перекладывают самый большой диск-это одно перекладывание, и, наконец,n-1меньших дисков переносятся на самый большой диск-это еще f(n-1)перекладываний. Получается, что n(n дисков можно за 2f(n-1)+1 перекладываний.

Вместе с тривиальным решением при n=0,получаем два равенства:

f (0) = 0

f (n)=2 f (n -1) +1 при п> 0

Совокупность равенств такого типа называется рекуррентностью (также в литературе встречается термин возвратное соотношение или рекурсивная зависимость) Полностью задать рекуррентное соотношение-значит задать начальные условия и зависимость общего члена от предыдущих.

Еще одна задача-задача о разрезании пиццы. Задача имеет геометрический характер: сколько кусков пиццы можно получить, делая n прямоугольных разрезов ножом? Или каково максимальное число f(n)областей, на которые плоскость делится nпрямыми? Впервые эта задача была решена в 1826 г. швейцарским математиком Якобом Штейнером.

Плоскость без прямых(n=0)-это одна плоскость-f(0)=1.

 

Рис.2                                   Рис.3                                  Рис.4

Плоскость с одной прямой (n=1)-две области-f(1)=2 (рис.2).

Плоскость с двумя прямыми (n=2)-четыре области-f(2)=4 (рис.3).

Когда добавляется третья прямая (рис.4), то она может рассекать самое большое три старые области вне зависимости от того, как расположены первые две прямые. Таким образом, f(3)=4+3=7-самое большое что можно сделать. Очередная k-я прямая(приn) увеличивает число областей на k,при этом она рассекает k предыдущих областей, пересекая прежние прямые в k-1различных точках. Две прямые могут пересекаться не более чем в одной точке. Поэтому n-я прямая может пересекать n-1 предыдущих прямых не более чем в n-1 различных точках. Следовательно, должно выполняться неравенство kn. Получаем верхнюю границу

f (n) £ f (n -1) + n при n >0

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

Учитывая тривиальное решение при n=0, получаем полное задание рекуррентного соотношения

f(0) = 1

f(n) = f (n -1) + n приn > 0

 

Задача Иосифа Флавия.  Иосиф Флавий-известный историк первого века. По легенде он выжил благодаря своей математической одаренности. В составе отряда из 41 иудейского воина он был загнан римлянами в пещеру. Предпочитая самоубийство плену, воины выстроились в круг и решили последовательно убивать каждого третьего, пока в живых не останется ни одного человека. Иосиф, наряду со своими единомышленниками посчитал такой конец бессмысленным и вычислил безопасные места в порочном круге для себя и своих товарищей.

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

Рис.5.Случай для 10 человек

 

В результате номер уцелевшего J(10)=5.

Обобщим случай для любого четного количества человек. Пусть первоначально имеется 2nлюдей. После первого перехода круга остаются нечетные номера, и следующий переход начинается с номера 3, причем, количество людей в круге становиться в 2 раза меньше. Это равносильно тому, что в круге присутствуют nчеловек, с той лишь разницей, что номер каждого присутствующего удваивается и уменьшается на 1. Следовательно, для четного случая получаем равенство

J(2n)=2J(n)-1,при п≥ 1

В нечетном случае человек с номером 1исключаеться сразу после номера 2n, и получаем ситуацию с n людьми, но в этот раз номера оставшихся удваиваются и увеличиваются на 1. Таким образом, получаем равенство для нечетного количества человек

J(2n+1)=2J(n)+1,при п≥ 1

Объединяя два равенства и учитывая начальное условие J(1)=1, составляем рекуррентное соотношение

J(1)=1

J(2n)=2J(n)-1, при п≥ 1                   (3)

J(2n+1)=2J(n)+1, при п≥ 1

Составим таблицу для разных значений n (количество человек, стоящих в круге)

n	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20
J(n)	1	1	3	1	3	5	7	1	3	5	7	9	11	13	15	1	3	5	7	9

Проверим: J (20) = 2J (10) -1= 2 × 5 -1= 9.

Для того, чтобы решить соотношение (3) сгруппируем значения nпо степеням 2(таблица ниже), то в каждой группе J(п) всегда будет начинаться с 1, а затем увеличиваться на 2.

Степень 2
n	1	2     3	4 5 6 7	8 9 10 11 12 13 14 15	16 17 18 19 20 21 22 ...
J(n)	1	1     3	1 3 5 7	1 3 5 7 9 11 13 15	1 3 5 7 9 11 13 ...

 

Таким образом, записывая количество человек в виде n=2m+1, где 2m- наибольшая степень 2, не превосходящая n, а 1-остаток. То решение задач будет выглядеть следующим образом

J (2m + l) = 2l +1, m ³ 0, 0 £ l < 2m (38)

1.2.​ Понятие рекуррентного соотношения

Рекуррентные соотношения (от лат. recur-rens, род, падеж recurrentis - возвращающийся) - однотипные формулы, которые связывают между собой идущие друг за другом элементы некоторой последовательности (это может быть последовательность чисел, функций и т. д.). В зависимости от природы объектов, связанных рекуррентные соотношения, эти соотношения могут быть алгебраическими, функциональными, дифференциальными, интегральными и т. п.

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

Пример:

Последовательность 2,4,8…,2n является решением для соотношения f(n+2)=3f(n+1)-2f(n)

Доказательство:

Общий член последовательности имеет вид f(n)=. Значит, f(n+2)=,f(n+1)=.При любом n имеет место тождество =3-2. Следовательно, при подстановке последовательности в формулу f(n+2)=3f(n+1)-2f(n),соотношение выполняется тождественно. Значит, является решением указанного соотношения.

Рекуррентное соотношение имеет порядок. Рекуррентное соотношение имеет порядок k, если оно позволяет выразитьf(n+k) черезf(n), f(n+1),.…,f(n+k-1).

Пример:

f(n+2)=f(n) f(n+1)-3(n+1)+1- рекуррентное соотношение второго порядка.

f(n+3)=6f(n) f(n+2)+f(n+1)- рекуррентное соотношение третьего порядка.

 Если задано  рекуррентное соотношение k-го порядка, то ему могут удовлетворить бесконечно много последовательностей, так как первые k элементов последовательности можно задать произвольно-между ними нет ни каких соотношений. Но если первые kчленов заданы, то все остальные элементы определяются однозначно.

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