説明
このタスクでは、 N ポイント(x 1 、y 1
)、…、(x <�別の x i
の値を使用して多項式を補間することですこれらの点。ラグランジュ補間が何であるか知っていれば、このセクションをスキップすることができます。
多項式補間の目的は、(一意の)多項式の p(x)を構築することです。 p(x
i )= y i の N-1 すべての i
= 1 … N に対して これを行う1つの方法は、 N
ラグランジュ基底多項式を構築し、線形結合を形成することです。このような基底多項式は、以下のように定義される。
x 1 、…、x i-1 のポイントで l i
、x i + 1 、… 、x N は構造によって0であり、x i
に対して1であり、y i に設定し、y i
に設定します。今度は、N個のそのような多項式を0以外のすべての点で1つを除いて単純に追加して、目的の結果を得ることができます。したがって、最終的な解決策は次のとおりです。
チャレンジ
- 入力は任意の合理的なフォーマット(タプル、ポイント、セットなどのリスト)で N
データポイントで構成されます。 - 座標はすべて整数値になります
- 出力は任意の合理的な形式の多項式である:係数のリスト、多項式オブジェクトなど
- 出力が正確でなければならない – いくつかの解が有理係数を持つことを意味する
-
1/2
の書式設定は重要ではありません(1
の代わりに
2/2
または1%2
>など)を使用することができます。 - 無効な入力を処理する必要はありません(空の入力や x 座標が繰り返される入力など)。
テストケース
これらの例は、係数を降順にリストします(たとえば、 [1,0,0]
は多項式の x
2 に対応します)。
[(0,42)] -> [42]
[(0,3),(-18,9),(0,17)] -> undefined (you don't have to handle such cases)
[(-1,1),(0,0),(1,1)] -> [1,0,0]
[(101,-42),(0,12),(-84,3),(1,12)] -> [-4911/222351500, -10116/3269875, 692799/222351500, 12]
ベストアンサー