Федеральное агентство по образованию

Государственное образовательное учреждение высшего профессионального образования
Вятский государственный гуманитарный университет

Математический факультет

Кафедра алгебры и геометрии

Выпускная квалификационная работа

Возвратные задачи

Выполнила:

студентка V курса математического факультета

Ковязина Юлия Николаевна

Научный руководитель:

кандидат физико-математических наук, доцент кафедры алгебры и геометрии И.А.Семенова

Рецензент:

ст. преподаватель кафедры алгебры и геометрии

А.Н.Семенов

Допущена к защите в государственной аттестационной комиссии

«___» __________2005 г. Зав. Кафедрой Е.М.  Вечтомов

«___»___________2005 г. Декан факультета В.И. Варанкина

Киров 2005

Содержание

Введение................................................................................................... 3

Глава 1..................................................................................................... 6

1.1 Задача о ханойской башне ......................................................... 6

1.2 Задача о разрезании пиццы........................................................ 7

1.3 Задача Иосифа Флавия............................................................. 10

Глава 2. Решение задач......................................................................... 19

Заключение............................................................................................ 41

Библиографический список................................................................... 42

 Введение

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

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

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

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

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

Тема «Возвратные последовательности» не является изолированной, нигде не используемой теорией. Наоборот, возвратные последовательности близки к школьному курсу математики (арифметическая и геометрическая прогрессии, последовательности квадратов и кубов натуральных чисел и т.д.), используются в высшей алгебре, геометрии, математическом анализе и других математических дисциплинах. Теория возвратных последовательностей составляет особую главу математической дисциплины, называемой исчислением конечных разностей; представляет собой частную главу о последовательностях.

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

Определение: Пусть имеется последовательность {un}:

u1, u2, u3,…, un, …  (1)

Если существует натуральное число k и числа a1, a2, a3, …,ak (действительные или мнимые) такие что, начиная с некоторого номера n и для всех следующих номеров

un+k=a1∙un+k-1 + a2∙un+k-2 +…+ak∙un при n ≥ 1 (2)

то последовательность (1) называется возвратной последовательностью порядка k , а соотношение (2) – возвратным (рекуррентным) уравнением порядка k.

Таким образом, зная k первых членов последовательности можно определить всю последовательность, т.е. вычислить любой наперед заданный член последовательности.

С помощью рекуррентных соотношений можно задать следующие последовательности:

1). Геометрическая прогрессия

un+1 = q∙un

2). Арифметическая прогрессия

un+1 = un + d

другой вид un+2 = 2∙un+1 − un

3). Последовательность чисел Фиббоначи

un+2 = un+1 +un

4). Последовательность квадратов натуральных чисел

un+1 = un + 2∙n + 1

другой вид un+3 = 3∙un+2 − 3∙un+1 + un

5). Последовательность кубов натуральных чисел

un+4 = 4∙un+3 − 6∙un+2 +4∙un+1 − un

6). Все периодические последовательности: u1, u2, …, uk+1, …

un+k = un.

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

7). Интегрирование простейших рациональных дробей IV типа

Обозначим Im=  , где t = x+

Im= ∙Im-1

8). Интеграл In=

In=∙In-2

9). Формула длины стороны при удвоении числа сторон правильного вписанного многоугольника

an= , при n ≥ 2

R – радиус описанной окружности

Если сторона a1 исходного правильного вписанного многоугольника задана, то an есть сторона многоугольника, полученного из исходного (n-1) кратным удвоением числа сторон.

10). Дифференциальные уравнения высших порядков

y(n) = f(x, y, y', y», …, y(n-1))

11). Определитель Вандермонда

n=∆(x1, x2, …, xn)=

∆ (x1, x2, …, xn) =(xn−x1)(xn-1−x1)…(x2−x1)∙∆(x2, x3, …,xn).

Глава 1


Информация о работе «Возвратные задачи»
Раздел: Математика
Количество знаков с пробелами: 54421
Количество таблиц: 10
Количество изображений: 14

Похожие работы

Скачать
35262
2
3

... то получим из них, путём почленного вычитания: un + 2 - un + 1 = un + 1 - un, или un + 2= 2un + 1 - un (5) - уравнение вида (2). Здесь k = 2, a1 = 2, a2 = -1. Следовательно, арифметическая прогрессия является возвратной последовательностью второго порядка. Пример 3. Рассмотрим старинную задачу Фибоначчи о числе кроликов. В ней требуется определить число пар ...

Скачать
26053
3
0

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

Скачать
60321
2
2

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

Скачать
228277
15
0

... возврата практически отсутствует, ссуда представляет собой фактически потери банка), 100% резерв от суммы основного долга.3. Проблемы и перспективы развития различных форм обеспечения возвратности кредита 3.1. Выбор формы обеспечения возвратности кредита в зависимости от финансового состояния заемщика. Сфера использования разнообразных форм обеспечения возвратности кредита, учитывая степень ...

0 комментариев


Наверх