Алгоритмы, структуры данных


         

Производящую функцию нельзя получить непосредственно.


  • Производящую функцию нельзя получить непосредственно. Например, 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.

    Содержание  Назад  Вперед