1-8へのアルゴリズム設計マニュアルソリューション

Question

私は現在、アルゴリズムの設計マニュアルSteven S. Skienaによって読んでいます。本のコンセプトのいくつかは、私が7年近く使用していないものです。私が大学にいる間でも、私のクラスメートの何人かがこれらの証拠のいくつかを思いついたかを理解することは困難でした。今、私は完全に練習の一つに立ち往生しています。助けてください。

この質問に答えて、あなたのBaseケースに何を使用するのか、それぞれのステップがなぜ有効で正しいのかを証明する理由を説明してください。これはたくさん聞いているかもしれませんが、実際にこれを行う方法を理解するのに役立つ必要があります。

ありがとうございます！

正し 質問の証明：

1-8。多項式を評価するための以下のアルゴリズムの正確さを証明する。 $$ P（x）は= a_nx_n + A_N-1x_n-1 +⋯+ a_1x + A_0

が

&function horner(A,x) 
    p=A_n 
    for i from n−1 to 0 
      p=p∗x+Ai 
    return p$ 

ところで、オフトピック$$：申し訳ありませんがみんな、私が正しく数学の書式設定を追加するかどうかはわかりません数式のために。私は各セクションの周りにaddign '$'を試しました。それがなぜ機能していないのか分かりません。

Answer 1

https://cs.stackexchange.com/これはおそらく良いでしょう。また、私は$$フォーマットが一部のStackExchangeサイトでのみ動作することを確信しています。しかし、とにかく、このアルゴリズムが各ステップで何をしているのか考えてみてください。

私たちはp = A_nで始まります。

次に、p = p*x + A_{n-1}とします。これは何をしていますか？我々は今p = x*A_n + A_{n-1}を持っています。

もう一度試してみます。 p = p*x + A_{n-2}だからp = (x^2)*A_n + x*A_{n-1} + A{n-2}（ここではx^2はもちろんxを2のべき乗にすることを意味します）。

ここから取得できます。