algorithm - 证明霍纳函数（多项式评估）

Question

我完成了 Steven S. Skiena的《算法设计手册》第二版中的练习 1-8：

有说服力吗？

Answer 1

通常在归纳证明中，您将步骤彼此分开。归纳步骤对我来说太隐晦了。我会这样做：

1)对于 n = 1 角([a0], x) = a0

2)角([a0,...,a(n+1)], x) = x * 角([a1,...,a(n+1)], x) + a0 = x * 角( [b0,...,bn], x) + a0，其中 bn = a(n+1)

3)因此对于 n 有 horner，对于 n+1 的 horner 可以用 2) 计算

你的证明很好，但正如我所说 - 归纳步骤应该明确强调 - 在单独的证明步骤中，n+1 的解决方案如何从 n 的解决方案（在你的情况下为 m）遵循。

Answer 2

我记得的方式是将 P(x) 写为：

P(x) = a_0 + x(a_1 + x(a_2 + ... + x(a_{n-1} + x a_n)) ... ))

for 循环直接从该处开始。

Answer 3

使用循环不变量

• 这是Daniel Schhelpher使用循环不变量的证明

使用感应

1. 归纳假设

2. 基本情况

3. 感应步骤

4. 结论