Re: Декомпозиция полиномов
От: Eugene Sh Россия  
Дата: 23.12.08 18:07
Оценка: 55 (4)
Здравствуйте, Аноним, Вы писали:

Один подход уже написал Кодт
Автор: Кодт
Дата: 23.12.08


Есть еще один способ решить вторую задачу.
А>2) Даны полиномы P(x) и R(x) с целочисленными коэффициентами. Найти полином Q(x) такой, что Q(P(x))=R(x). Известно, что такой полином существует и имеет целочисленные коэффициенты.

Степень полинома Q определяется быстро — она равна (степень R) / (степень P)

Пусть степень Q равна n. Для задания всего полинома достаточно задать его значение в n+1 точке.
Начнем подставлять значения x=0,1,2,... в уравнение Q(P(x)) = R(x)
Среди значений P(0), P(1), P(2), ... рано или поздно найдется n+1 различных чисел. Это следует из того, что уравнение P(x) = A имеет конечное число корней для любого A.

Итак, у нас будет значение Q в n+1 точках. Далее, Q легко восстанавливается.
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.