Федеральне агентство з освіти
Державне освітня установа вищої професійної освіти
Вятський державний гуманітарний університет
Математичний факультет
Кафедра алгебри і геометрії
Випускна кваліфікаційна робота
Зворотні задачі
Виконала:
студентка V курсу математичного факультету
Ковязіна Юлія Миколаївна
Науковий керівник:
кандидат фізико-математичних наук, доцент кафедри алгебри та геометрії І.А.Семенова
Рецензент:
ст. викладач кафедри алгебри і геометрії
А.Н.Семенов
Допущена до захисту в державної атестаційної комісії
В«___В» __________ 2005 р. Зав. Кафедрою Е.М. Вечтомов
В«___В» ___________2005 р. Декан факультету В.І. Варанкіна
Кіров 2005
Зміст
3
Глава 6
1.1 Задача про Ханойські вежі ................................................. ........ 6
1.2 Задача про розрізуванні піци ................................................. ....... 7
1.3 Завдання Йосипа Флавія ........................................... .................. 10
Глава 2. Рішення задач ................................................ ......................... 19
41
Бібліографічний список ............................................. ...................... 42
Введення
Дискретна математика в даний час грає велику роль в розробці принципів роботи комп'ютера, тому робота комп'ютера являє собою виконання послідовності дискретних кроків, що приводять до вирішення поставленого перед комп'ютером задачі.
Розглянута мною тема В«Поворотні завданняВ» є невеликою частиною дискретної математики, тому дана тема на сьогоднішній момент є не менш актуальною.
Мета моєї роботи - вивчити наявний теоретичний і практичний матеріал по даній темі і застосувати його до вирішення завдань.
Дана робота складається з вступу, двох розділів і висновку. У вступі наводяться приклади рекурентних співвідношень, за допомогою яких можна задати деякі послідовності, а так ж рекурентні співвідношення, які можуть використовуватися при вирішенні завдань. В першій главі описуються три задачі: задача про Ханойські вежі, завдання про розрізуванні піци і завдання Йосипа Флавія, а також доводяться деякі факти, які в літературі пропонуються для самостійного докази. Друга глава присвячена вирішенню завдань на дану тему. У висновку робляться висновки про виконану роботу і вказуються подальші перспективи.
В основі рішення зворотних задач лежить ідея зворотності (або рекурентності), згідно з якою рішення всієї задачі залежить від вирішення тієї ж самої задачі менших розмірів.
Тема В«Поворотні послідовності В»не є ізольованою, ніде не використовуваної теорією. Навпаки, поворотні послідовності близькі до шкільного курсу математики (Арифметична і геометрична прогресії, послідовності квадратів і кубів натуральних чисел і т.д.), використовуються у вищій алгебрі, геометрії, математичному аналізі та інших математичних дисциплінах. Теорія зворотних послідовностей складає особливу главу математичної дисципліни, званої обчисленням кінцевих різниць; являє собою приватну главу про послідовностях.
Таким чином, поворотні послідовності є справжньою маленькою теорією, закінченою, простий, ясною.
Визначення: Нехай є послідовність {u n }:
u 1 , u 2 , u 3 , ..., u n , ... (1)
Якщо існує натуральне число k і числа a 1 , a 2 , a 3 , ..., a k (дійсні або уявні) такі що, починаючи з деякого номера n і для всіх наступних номерів
u n + k = a 1 в€™ u n + k-1 + a 2 в€™ u n + k-2 + ... + a k в€™ u n при n ≥ 1 (2)
то послідовність (1) називається поворотній послідовністю порядку k, а співвідношення (2) - зворотним (рекурентним) рівнянням порядку k.
Таким чином, знаючи k перших членів послідовності можна визначити всю послідовність, тобто обчислити будь-який наперед заданий член послідовності.
За допомогою рекурентних співвідношень можна задати наступні послідовності:
1). Геометрична прогресія
u n +1 = q в€™ u n
2). Арифметична прогресія
u n +1 = u n + d
інший вид u n +2 = 2 в€™ u n +1 - u n
3). Послідовність чисел Фіббоначі
u n +2 = u n +1 + u n
4). Послідовність квадратів натуральних чисел
u n +1 = u n + 2 в€™ n + 1
інший вид u n +3 = 3 в€™ u n +2 - 3 в€™ u n +1 + u n
5). Послідовність кубів натуральних чисел
u n +4 = 4 в€™ u n +3 - 6 в€™ u n +2 +4 в€™ u n +1 - u n
6). Всі періодичні послідовності: u 1 , u 2 , ..., u k +1 , ...
u n + k = u n .
Також рекурентні співвідношення можуть використовуватися при вирішенні завдань (зокрема, при доказі рівностей):
7). Інтегрування найпростіших раціональних дробів IV типу
Позначимо I m =, де t = x +
I m = в€™ I m-1
8). Інтеграл I n =
I n = в€™ I n-2
9). Формула довжини сторони при подвоєнні числа сторін правильного вписаного багатокутника
a n =, при n ≥ 2
R - радіус описаного кола
Якщо сторона a 1 вихідного правильного вписаного багатокутника задана, то a n є сторона многокутника, отриманого з вихідного (n-1) кратним подвоєнням числа сторін.
10). Диференціальні рівняння вищих порядків
y ( n ) = f (x, y, y ', y В», ..., y ( n -1) )
11). Визначник Вандермонда
О” n = О” (x 1 , x 2 , ..., x n ) =
О” (x 1 , x 2 , ..., x n ) = (x n x 3 , ..., x n ).
Глава 1
1.1. Задача про Ханойські вежі
Розглянемо спочатку маленьку витончену головоломку під назвою Ханойські вежі, яку придумав французький математик Едуард Люка в 1883 р. Вежа являє собою вісім дисків, нанизаних в порядку зменшення розмірів на один з трьох кілочків. Завдання полягає в тому, щоб перемістити всю вежу на один з інших кілочків, переносячи кожен раз тільки один диск, і не поміщаючи більший диск на менший.
Будемо вирішувати цю задачу в загальному вигляді, тобто подивимося, що буде в разі n дисків.
Будемо говорити, що T n є мінімальне число перекладань, необхідних для переміщення n дисків з одного кілочка на інший за правилами Люка.
Розглянемо крайні випадки: Т 0 = 0, T 1 = 1, T 2 = 3, T 3 = 7. Експеримент з трьома дисками дає ключ до загальним правилом переміщення n дисків: спочатку ми переміщаємо (n-1) менших дисків на будь-який з кілочків (що вимагає Т n -1 перекладань), потім перекладаємо найбільший диск (одне перекладання) і, нарешті, поміщаємо (n-1) менших дисків наз...
