В "конкретной математике" Кнута, в параграфе про задачу Иосифа Флавия при разборе рекуррентного соотношения используется(как он назван в книге) репертуарный метод. Но рассмотрен он на одном примере и как-то неясно и не строго. Может ли кто-нибудь доходчиво объяснить суть метода(алгоритм его действий)? Статей по этому методу в инете не нашел, но может плохо искал.
Asvald Там ничего сложного, принцип следующий: у нас есть функция f(n, a_{1},...,a_{k}) (где a_{1},...,a_{k} - параметры), заданная рекурсивным соотношением. Предполагаем, что эта функция линейна в параметрах, то есть f = A1(n)*a_{1} + ... + AK(n)*a_{k} Рассматривая A1(n),...,AK(n) как неизвестные, получаем линейное уравнение с k переменными. Чтобы его решить, ищем k комбинаций (f, a_{1},...,a_{k}), подставляем их поочередно в линейное уравнение и получаем систему из k линейных уравнений относительно k переменных. Решаем ее и находим A1(n),...,AK(n) и соответственно общий вид f. Если принцип все еще плохо понятен, вспомни школьное упражнение, когда начинают проходить графики функций. На миллиметровой бумаге нарисована система координат и прямая. Задача: найти функцию, описывающую эту прямую. Решение - предполагаем, что функция линейна в х, то есть f(x,a,b) = a*x + b Теперь берем(из рисунка) две какие-нибудь комбинации (f, x), получаем два линейных уравнения относительно a и b и решаем их. То есть идея точно та же самая, просто здесь у нас рекурсивное отношение вместо рисунка Попробуй сделать упражнение 16. P.S. народ, как правильно - рекуррентный или рекурсивный?
Stiver Только непонятно, почему этот стандартный подход был назван репертуарным. Мне лично больше нравится термин рекуррентное сооотношение, а вот метод численной реализации данного соотношения можно уже назвать рекурсивным. ЗЫ А вобче метод рекуррентных соотношений + метод производящих функций - мощнейший математический аппарат в комбинаторной математике.
crypto This approach illustrates a surprisingly useful repertoire method for solving recurrences. First we find settings of general parameters for which we know the solution; this gives us a repertoire of special cases that we can solve. Then we obtain the general case by combining the special cases. (Knuth, Concrete Mathematics) Вот почему - "repertoire of special cases" )
Stiver Это можно назвать и так: "от частных случаев - к общему". Почему репертуарный, все равно непонятно. Я слышал про репертуарный метод в психологии, есть здесь аналогии? ЗЫ Похоже калька переводчика вошла в обиход.
