Открытая форма и закрытая форма

Question

Как можно преобразовать открытую форму повторения в эквивалентную закрытую форму. Кроме того, каковы некоторые часто используемые закрытые формы, которые обычно используется эффективно.

Answer 1

Я думаю, вы говорите о рекурсивных функциях и математике.

например. рассмотрим следующую сумму рекурсивной функции

sum(0) = 0
sum(i) = sum(i-1) + i

эта форма не закрыта. Закрытая форма - sum(n) = (n+1)*n/2, где вы используете только основные операции, такие как + - * /, power, а иногда и факториал.

На ваш вопрос, как преобразовать формулу открытой формы в закрытую форму. Ответ: Не существует общего правила для преобразования всей открытой формы в закрытую форму, потому что некоторые открытые формы не имеют эквивалентных закрытых форм. Вы можете обратиться к Конкретная математика для серьезного рассмотрения этого предмета. Основная цель книги - преобразовать большое семейство рекурсивных функций / открытых форм в их закрытые формы.

Answer 2

открытая форма обычно задается как уравнение, которое необходимо решить.Например,

a(0) = 1            -- base case
a(n) = b * a(n-1)   -- recurrence relation

Чтобы преобразовать его в закрытую форму , вы решаете рекуррентное соотношение .В этом случае повторное замещение до достижения базового варианта дает вам

a(n) = b * a(n-1) = b * b + a(n-2) = ... = b * b * ... * b * a(0) = b^n

Это более эффективно, поскольку мощности можно оценить за логарифмическое время в n (то есть пропорционально лог1015 * n ), тогда как исходное отношение рекуррентности занимает линейное время в n .

Существует много методов, используемых для решения отношений рекуррентности.Некоторые примеры можно найти в статье Википедии .Важно понимать, что не все рекуррентные отношения могут быть решены, однако - фактически, большинство не может быть решено (именно поэтому программирование важно!)