Новини освіти і науки:

G+

Тлумачний словник
Авто
Автоматизація
Архітектура
Астрономія
Аудит
Біологія
Будівництво
Бухгалтерія
Винахідництво
Виробництво
Військова справа
Генетика
Географія
Геологія
Господарство
Держава
Дім
Екологія
Економетрика
Економіка
Електроніка
Журналістика та ЗМІ
Зв'язок
Іноземні мови
Інформатика
Історія
Комп'ютери
Креслення
Кулінарія
Культура
Лексикологія
Література
Логіка
Маркетинг
Математика
Машинобудування
Медицина
Менеджмент
Метали і Зварювання
Механіка
Мистецтво
Музика
Населення
Освіта
Охорона безпеки життя
Охорона Праці
Педагогіка
Політика
Право
Програмування
Промисловість
Психологія
Радіо
Регилия
Соціологія
Спорт
Стандартизація
Технології
Торгівля
Туризм
Фізика
Фізіологія
Філософія
Фінанси
Хімія
Юриспунденкция

Рекурсія

Листок завдань №2.

1. Модифікації Фібоначчі

A) Розв’язати рекурентне рівняння, що призводить до узагальнення чисел Фібоначчі.

, ,

Відповідь подати з використанням чисел Фібоначчі.

B) “Фібоначчі третього порядку”.

Розв’язати рівняння

2. Написати рекурсивну функцію, що визначає мінімальний елемент масиву. Оцінити складність алгоритму та порівняти з нерекурсивним випадком.

3*.

Теорема. Нехай , , -- деяка функція. Нехай

причому інтерпритується як або .

Тоді можна обмежити наступним чином.

1) Якщо для деякого сталого , тоді

1) Якщо , тоді

3) Якщо для деякого сталого , і крім того, починаючи з деякого , для деякого , тоді

Використовуючи попередню теорему, оцінити складність у наступних випадках.

D) чи можна застосувати теорему до співвідношення ? Аргументувати.

E) для якого найбільщого значення алгоритм є асимптотично швидшим за , якщо , ?

F) показати, що теорему не можна застосувати до співвідношення

Примітка. 1) для великих і деякого .

2) для великих і деяких , .

4. Ханойські вежі

Ханойська вежа (також Вежа Брахми або Вежа Лукаса, іноді в множині Ханойські вежі) — це математична гра абоголоволомка. Утворена трьома стрижнями і кількома дисками різних розмірів, які можна насунути на будь-який стрижень. Початковий стан головолмки має два порожніх стрижні і всі диски на третьому в монотонно спадному порядку з низу до гори, так утворюється побудова, що нагадує вежу.

Ціллю головоломки є перенести весь стос дисків на інший стрижень, дотримуючись таких правил:

§ За раз можна рухати лише один диск.

§ Кожен крок полягає в перенесенні верхнього диска з одного зі стрижнєв і насування його на інший зверху інших дисків, які вже можуть бути присутніми на другому стрижні.

§ Диск не можна класти з гори меншого диска.

Оцінити складність наступного алгоритму. (Складність операції “перекласти” -- ).

Функція Ханой(n);

begin

Ханой(n-1);

Перекласти;

Ханой(n-1);

End;

5. Написати рекурсивну функцію, що визначає суму елементів масиву. Оцінити складність алгоритму та порівняти з нерекурсивним випадком.

<== попередня сторінка	\|	наступна сторінка ==>
Guide to Case Analysis	\|	Match the way of forming the plural and the noun.

Не знайшли потрібну інформацію? Скористайтесь пошуком google:

Генерація сторінки за: 0.004 сек.