Рубрики

ВОРОТА | GATE-CS-2006 | Вопрос 1

Рассмотрим полином p (x) = a0 + a1x + a2x 2 + a3x 3 , где ai ≠ 0 ∀i. Минимальное количество умножений, необходимое для оценки p на входе x:
(А) 3
(Б) 4
(С) 6
(D) 9

Ответ: (А)
Объяснение:
Объяснение фона:
Правило Хорнера для полиномиального деления — это алгоритм, используемый для упрощения процесса вычисления полинома f (x) при определенном значении x = x0 путем деления полинома на мономы (полиномы 1-й степени). Каждый моном включает в себя максимум одно умножение и одно сложение. Результат, полученный из одного монома, добавляется к результату, полученному из следующего монома, и так далее в виде накопительного сложения. Чтобы объяснить вышесказанное, давайте переписать полином в его расширенной форме;

f (x0) = a0 + a1x0 + a2x0 ^ 2 +… + беспокойство0 ^ n

Это также может быть записано как:

f (x0) = a0 + x0 (a1 + x0 (a2 + x0 (a3 +… + (an-1 + беспокойство0)….)

Алгоритм, предложенный этим правилом, основан на оценке мономов, сформированных выше, начиная
от одного в самой внутренней скобке и выйти, чтобы оценить мономы во внешнем
скобка.

Решение :
Используя правило Хорнера, мы можем написать многочлен следующим образом
a0 + (a1 + (a2 + a3x) x) x

В приведенной выше форме нам нужно сделать только 3 умножения


p = a3 X x    ------------ (1)

q = (a2 + p) X x  ---------(2)

r = (a1 + q) X x  ---------(3)

result = a0 + r 

Ссылка :
http://espressocode.top/horners-method-polynomial-evaluation/
Это решение предоставлено Nitika Bansal.
Тест на этот вопрос

Рекомендуемые посты:

ВОРОТА | GATE-CS-2006 | Вопрос 1

0.00 (0%) 0 votes