Читайте также:
|
|
РЕКУРСИВНЫЕ АЛГОРИТМЫ И МЕТОДЫ ИХ АНАЛИЗА
Логарифмические тождества
При анализе рекурсивных алгоритмов достаточно часто используются логарифмические тождества, далее предполагается, что, 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 | Поможем написать вашу работу | Нарушение авторских прав |
<== предыдущая лекция | | | следующая лекция ==> |
показателей первого и второго класса | | | Рефлексивный анализ урока музыки и форм внеклассной музыкальной работы на педагогической практике |