證明霍納功能（多項式估值）

Question

我完成了練習1-8 的算法設計手冊，第二版，由史蒂芬S. Skiena：

是否有說服力？

Answer 1

通常在感應證明中，您將步驟彼此分開。歸納步驟對我的口味來說太隱含了。我願意做這樣的：

1）對於n = 1個霍納（[A 0]，X）= A0

2）霍納（[A 0，...，A（N +1）]，x）= x * horner（[a1，...，a（n + 1）]，x）+ a0 = x * horner（[b0，...，bn]，x）+ a0其中BN =第（n + 1）

3）因此具有霍納對於n，霍納對於n + 1可與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循環直接如下。