Рекурсия (стр. 7 из 12)
Контрольные примеры.
Тогда искомая функция pn(n) может быть определена так:
Контрольные примеры.
3.19 Схема Горнера
Задача 25. Составить программу-функцию вычисления значений многочлена по схеме Горнера.
Решение. Пусть f(x) многочлен с вещественными или комплексными коэффициентами и v – вектор этих коэффициентов:
(8) 
(9)Вычисление f(x) в точке x по схеме Горнера проводится от самых внутренних скобок и далее в соответствии с представлением:
Отсюда ясно, как записать рекурсивный и не рекурсивный варианты алгоритмов вычисления f(x). Нас интересует только первый из них. Параметрами задачи можно считать вектор v и точку a для вычисления f(a). Тривиальный случай – многочлен нулевой степени: f(a) = a0. Декомпозиция получается из указанной выше расстановки скобок в записи f(x). Соответствующая программа-функция выглядит, например, так.
Контрольные примеры.
Замечание. Параметр n – это константа, равная степени многочлена. По вектору v она определяется однозначно. Однако в каждом рекурсивном вызове проводится перевычисление n. Избежать лишней вычислительной работы в подобных ситуациях можно двумя способами. Или определять такие константы заранее вне текста программы-функции или передавать их значения через дополнительные аргументы функции.
3.20 Деление многочлена на двучлен
Задача 26. Составить программу-функцию, по которой для многочлена (8) с коэффициентами, составляющими вектор (9) и двучлена x-x0 (x0- вещественное или комплексное число), вычисляется вектор c:
такой, что
и
Решение. Если в соотношении, связывающем многочлены f(x) и q(x), осуществить приведение к общему знаменателю и приравнивание коэффициентов при одинаковых степенях x, то для определения компонент вектора c получим следующую систему линейных уравнений.
Отсюда вытекает, что c = qu(v,x0), где рекурсивное определение функции qu() может выглядеть, например, так.
Контрольный пример.
Иными словами:
3.21 Произведение двух многочленов
Задача 27. Пусть коэффициенты многочленов fn(x) и gm(x) заданы компонентами векторов v и w:
(10) 
(11)Составить рекурсивную программу-функцию вычисляющую коэффициенты многочлена hn+m(x)=fn(x)×gm(x) и возвращающую их в виде компонентов вектора:
Решение. Поскольку
где
то вполне можно организовать рекурсию по параметру m- степени второго сомножителя. И в качестве решения может быть предложена следующая функция:
Ясно, что аналогично можно было бы реализовать рекурсию и по параметру n - степени первого сомножителя. В любом случае величины m и n определяют количество рекурсивных обращений. Поэтому в данной задаче рекурсию выгодно реализовывать по параметру со значением, равным min(n,m).
Контрольный пример.
3.22 Произведение биномов
Задача 28. Составить программу-функцию возвращающую коэффициенты многочлена g(x), который получается в результате перемножения биномов (x-vk): (k=0,1,…n-1; n³1):
Решение. Будем считать, что свободные члены биномов заданы в виде компонентов некоторого вектора v:
а результат вычислений должен возвращаться также в виде вектора. Поскольку 
то несложно организовать рекурсию по количеству перемножаемых биномов. Соответствующая программа функция могла бы выглядеть так:
Контрольный пример.
3.23 Деление многочлена на многочлен
Задача 29. Пусть выполнены соотношения (10)-(11), то есть многочлены fn(x) и gm(x) степеней n и m (n,m³0) соответственно заданы своими коэффициентами в виде компонентов векторов v и w. Пусть, далее, при m=0, то есть если gm(x) есть константа, gm(x)¹0. Составить программу-функцию нахождения частного q(x) и остатка r(x) при делении fn(x) на gm(x):
fn(x)=q(x)×gm(x)+r(x), (12)
где степень r(x) меньше m (при m=0 r(x)º0).
Решение. Представление (12) единственно. В дальнейшем нам удобно считать, что степень r(x) равна m-1 с возможно нулевыми коэффициентами при старших степенях x.
При m=0 решение задачи очевидно:
q(x)=fn(x)/w0,r(x)=0. (13)
Далее, при n<=m имеем
(14)Пусть n>m и q1(x) и r1(x) - частное и остаток от деления (fn(x)-an-1)/x на gm(x):
Из этого соотношения вытекает, что
Вместе с (12) это дает:
(15)Если соотношения (13)-(14) рассматривать в качестве базы рекурсии, то равенства (15) определяют декомпозицию. Считаем, что в результате вычислений должен быть сформирован и возвращен составной вектор qr=[qr]T, где q и r соответственно векторы коэффициентов многочленов q(x) и r(x). Соответствующая программа-функция, реализующая эти идеи, выглядит так:
Контрольные примеры.
Замечание. Функция poldiv() возвращает составной вектор [qr]T , в котором второй компонент-вектор r может содержать “ведущие” нули. При необходимости эти нули можно погасить, то есть выделить из r подвектор, начинающийся с первого из ненулевых компонент r. Сделать это можно, например, с помощью приведенной ниже рекурсивной функции nulera(u). Если все компоненты u равны нулю, то nulera(u) возвращает 0.
3.24 Разбиение целого на части
Задача 30. Составить программу-функцию подсчета количества x(m) разбиений натурального числа m, то есть его представления в виде суммы натуральных чисел.
Решение. Пусть, например, m=6. Тогда разбиениями m являются его представления в виде:
6;
5+1;
4+2, 4+1+1;
3+3, 3+2+1, 3+1+1+1;
2+2+2, 2+2+1+1, 2+1+1+1+1;
1+1+1+1+1+1;
Таким образом, x(m)=11 и понятно, что простым перебором возможных случаев уже при m>10 справиться с задачей достаточно сложно.
Для решения исходной задачи перейдем к рассмотрению обобщенной задачи.Составить программу-функцию подсчета количества P(m,n) разбиений натурального числа m со слагаемыми, не превосходящими n.Ясно, что x(m)=P(m,m). Поэтому, достаточно научиться вычислять значения функции P(m,n). Но для неё нетрудно выделить рекурсивную базу и указать правило декомпозиции. Сделать это можно исходя из следующих вполне прозрачных свойств этой функции.
1. P(m,1)=1 - существует только одно разбиение m, в котором слагаемые не превосходят единицы, а именно: m=1+1+…+1.
2. P(1,n)=1 - число единица имеет только одно представление при любом n.
3. P(m,n)=P(m,m) при n>m- слагаемые, большие m в разбиениях отсутствуют.
4. P(m,m)=P(m,m-1)+1 - существует лишь одно разбиение со слагаемым равным m. Все иные разбиения имеют слагаемые не превосходящие m-1.
5. P(m,n)=P(m,n-1)+P(m-n,n) (n<m). Обоснование этого соотношения проводится так. Все разбиения m на сумму слагаемых, не превосходящих n можно разбить на два непересекающихся класса: суммы, не содержащие n в качестве слагаемого и суммы, содержащие такое n. Количество элементов первого класса равно P(m,n-1), а количество элементов второго класса подсчитаем так. Без учета слагаемого n суммы элементов второго класса равны m-n. Значит их общее количество равно P(m-n,n) и, следовательно, общее количество элементов второго класса также равно этой величине. Тем самым свойство 5 установлено.