Описание метода
Производящая функция последовательности {an}, n>=0 – формальный степенной ряд:
Переход от последовательностей к их производящим функциям позволяет заменить операции над последовательностями операциями над их производящими функциями.
Идея метода производящих функций состоит в том, что рекуррентное соотношение, определяющее последовательность {an}, переписывают как уравнение для ее производящей функции, это уравнение решают и по найденной производящей функции получают зависимость общего члена последовательности {an} от n.
Для того, чтобы получить алгебраические выражения для значения каждой переменной в зависимости от номера итерации необходимо преобразовать операции, изменяющие значения переменных, в рекуррентные соотношения вида:
где i – номер итерации
t – функция преобразования переменной v, принадлежащая множеству T
Vi-1 – значения переменных, полученные на предыдущей итерации
Vi – значения переменных, полученные на текущей итерации
Производящие функции (или выражения для vi) достаточно просто можно получить для присваиваний вида:
В этом случае для получения выражения для vi достаточно подставить выражения для всех остальных переменных в правую часть или найти производящую функцию для f.
Пользуясь методикой из [2] каждый оператор присваивания вида
где Fv(z) – производящая функция для переменной v
FV – множество производящих функций для переменных, принадлежащих множеству V
G – некоторая алгебраическая функция
Найти алгебраическое выражение (возможно содержащее в себе другие производящие функции) для производящей функции для f можно пользуясь линейностью производящих функций: производящая функция суммы равняется сумме производящих функций.
Для каждого из слагаемых существует следующий выбор:
- Производящую функцию можно определить непосредственно (например, если слагаемое представляет собой константу, умноженную на переменную) по таблице прозводящих функций из [2]
- Производящую функцию нельзя получить непосредственно. Например, ai - bi. В этом случае, необходимо подставить выражения для всех переменных (ai и bi), а затем найти производящую функцию для последовательности, которую генерирует это выражение при изменении i от 0 до бесконечности.
- Производящую функцию нельзя получить непосредственно (как в случае 2), но выражения для ai и bi (см. случай 2) невозможно получить без знания выражения для vi+1. В этом случае предлагаемый метод не работает.
Полученные выражения для переменных можно подставить в P, чтобы определить номер итерации на которой произойдет выход из цикла. Если данную задачу удается решить, то цикл может быть заменен вычислениями по формуле или просто подстановкой констант в случае, когда все параметры, входящие в выражения для результирующих переменных известны на этапе компиляции. Рассмотрим несколько примеров
1. Переменная, которая в каждой итерации умножается на константу и к результату прибавляется другая константа
Найдем производящую функцию для данной последовательности
Отсюда можно получить алгебраическое выражение для v в зависимости от номера итерации:
| для c1 = 1: |  |
(*) |
| для c1 <> 1: |  |
2. Линейная комбинация переменных
где k – номер переменной (переменные с номерами меньше k изменились в текущей итерации, с номером большим k – будут изменены позднее)
Применяя манипуляции, подобные использованным в предыдущем пункте, можно получить следующий результат:
Отсюда можно получить выражение для Vk(z), а из него – выражение для vki.
3. Многочлен от переменных, выражения для которых имеют вид (*)
Метод, применяемый в предыдущих примерах здесь не сработает, поэтому необходимо выполнить подстановку выражений для vji в данную формулу, что приведет к появлению многочлена от i:
Производящая функция для in не существует в простой форме, однако ее можно выразить через производящие функции для числа сочетаний:
Отсюда можно получить производящие функции для in:
| i1: |  |
| i2: |  |
и так далее.
Таким образом, производящая функция для vki будет иметь вид:
где ri – коэффициент при in в R(i), а Ii(z) – производящая функция для in.
