адача
32. Пусть
выполнены соотношения (13)- (14),
то есть многочлены 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), (15)
где степень r(x) меньше m (при m=0 r(x)º0).
Решение. Представление (15) единственно. В дальнейшем нам удобно считать, что степень r(x) не выше m с возможно нулевыми коэффициентами при старших степенях x.
При
n£m имеем
(16)
Пусть
n>m. Введем обозначение
Отсюда
(17)
где
fn- 1(x) - многочлен, степени не выше n- 1. Если для fn- 1(x) найдено q1(x) и r1(x) - частное и остаток от деления на gm(x), то вместе с (15) и (17) это дает:
(18)
Если соотношения (16) рассматривать в качестве базы рекурсии, то равенства (18) определяют декомпозицию. Считаем, что в результате вычислений должен быть сформирован и возвращен составной вектор qr = [q r]T, где
q и r - соответственно векторы коэффициентов многочленов q(x) и r(x). Соответствующая программа-функция, реализующая эти идеи, выглядит так:
Замечание. Функция poldiv() возвращает составной вектор [q r]T, в котором второй компонент-вектор r может содержать “ведущие” нули. При необходимости эти нули можно погасить, то есть выделить из r подвектор, начинающийся с первого из ненулевых компонентов r. Сделать это можно, например, с помощью приведенной ниже рекурсивной функции nulera(u). Если все компоненты u равны нулю, то nulera(u) возвращает 0:
