説明

このタスクでは、 N ポイント（x ₁ 、y ₁
）、…、（x <�別の x _i
の値を使用して多項式を補間することですこれらの点。ラグランジュ補間が何であるか知っていれば、このセクションをスキップすることができます。

多項式補間の目的は、（一意の）多項式の p（x）を構築することです。 p（x
_i ）= y _{i の N-1 すべての i
= 1 … N に対して これを行う1つの方法は、 N
ラグランジュ基底多項式を構築し、線形結合を形成することです。このような基底多項式は、以下のように定義される。}

                          

x ₁ 、…、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
² に対応します）。

[(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]