algorithm - 多項式を描く

Question

私は多項式形式を持っています：

w(x) = a +b(x-x1) + c(x-x1)^2*(x-x2) + d(x-x1)^2*(x-x2)^2+....

この多項式を数えるための高速アルゴリズムを知っている人はいますか？

この多項式を描きたいのですが、最初に値を数えなければなりませんが、それに対する速くて面白い方法を見つけることができません。

Answer 1

多項式全体を反復するよりも高速なアルゴリズムはないと思います。あなたの説明からは、用語を形成する規則が正確に何であるかが明らかではないため、解決策を提供することはできませんが、自分で考え出すとさらに良い.

私が見るところ、連続する各項の x 依存部分は、これまでに得たものに別の単項式を掛けることによって形成されます。その場合は、サイクルの反復間で値を保持します。

Answer 2

、、、、a、b、x、、x1などの式の個々の要素を取得するパーサーを記述します。2*+^()

次に、Shunting-yard アルゴリズムを使用して、式を逆ポーランド記法に変換します。

次に、スタックまたはツリーを使用して評価します。

同じ式を何度も評価するつもりなら、共通の部分式を削除したいかもしれません (例えばx - x1、複数回繰り返し、一度だけ計算するかもしれません)。それを行う方法もあります。しかし、そこに行く前に、そのような最適化なしで得られるものが本当に十分でないかどうかをまず確認してください。