Студопедия  
Главная страница | Контакты | Случайная страница

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатика
ИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханика
ОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторика
СоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансы
ХимияЧерчениеЭкологияЭкономикаЭлектроника

Методы решения рекурсивных соотношений

Читайте также:
  1. C) Методы стимулирования поведения деятельности
  2. I. ЗАДАЧИ ДЛЯ САМОСТОЯТЕЛЬНОГО РЕШЕНИЯ
  3. II. Для решения следующих задач используйте формулы для сочетаний
  4. II. Методы и источники изучения истории; понятие и классификация исторического источника.
  5. II. Методы исследования
  6. II. Методы исследования
  7. II. МЕТОДЫ, ПОДХОДЫ И ПРОЦЕДУРЫ ДИАГНОСТИКИ И ЛЕЧЕНИЯ
  8. II. МЕТОДЫ, ПОДХОДЫ И ПРОЦЕДУРЫ ДИАГНОСТИКИ И ЛЕЧЕНИЯ
  9. II. Обоснование целесообразности решения проблемы программно-целевым методом
  10. II. Формы и методы деятельности по утверждению трезвости

РЕКУРСИВНЫЕ АЛГОРИТМЫ И МЕТОДЫ ИХ АНАЛИЗА

Логарифмические тождества

При анализе рекурсивных алгоритмов достаточно часто используются логарифмические тождества, далее предполагается, что, a > 0, b > 0, c > 0, основание логарифма не равно единице:


в записи Q(ln(x)) основание логарифма не существенно, если он больше единицы, т.к. константа скрывается обозначением Q.

Можно показать, что для любого

Методы решения рекурсивных соотношений

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

а) Метод индукции

Метод состоит в том, что бы сначала угадать решение, а затем доказать его правильность по индукции. Пример:

f(0)=1 f(n+1)=2*f(n)

Предположение: f(n)=

Базис: если f(n)= , то f(0)=1, что выполнено по определению.

Индукция: Пусть f(n)= , тогда для n+1 f(n+1)= 2 * =

Заметим, что базис существенно влияет на решение, так, например:

Если f(0)=0, то f(n)=0;

если f(0)=1/7, то f(n)=(1/7)* ; если f(0)=1/64, то f(n)=(2)

б) Метод итерации (подстановки)

Суть метода состоит в последовательной подстановке – итерации рекурсивного определения, с последующим выявлением общих закономерностей:

Пусть f(n)=3*f(n/4)+n, тогда:

f(n)=n+3*f(n/4)=n+3*[n/4+3*f(n/16)]=n+3*[n/4+3{n/16+3*f(n/64) }],

и раскрывая скобки, получаем:

f(n)=n+3*n/4+9*n/16+27*n/64+…+ *n/

Остановка рекурсии произойдет при , в этом случае последнее слагаемое не больше, чем

, то окончательно:




Дата добавления: 2015-01-12; просмотров: 32 | Поможем написать вашу работу | Нарушение авторских прав

<== предыдущая лекция | следующая лекция ==>
показателей первого и второго класса| Рефлексивный анализ урока музыки и форм внеклассной музыкальной работы на педагогической практике

lektsii.net - Лекции.Нет - 2014-2024 год. (0.008 сек.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав