Есть многочлен P(x) = a
n * x
n + a
n — 1 * x
n — 1 + ... + a
1 * x + a
0
Есть псевдокод, вычисляющий этот многочлен:
function horner(A, x)
p = A n
for i from n - 1 to 0
p = p * x + A i
return p
Нужно доказать правильность этого алгоритма.
Я делаю это так: инвариант цикла будет (P = P * x + A
i) and (n — 1 >= i >= 0). Инвариант будет истинным перед каждой итерацией. Условие завершение цикла i < 0, что у нас в коде достигается. Так как инвариант и условие завершение цикла истинны, то наш код правильный.
Здесь есть ошибки?
