Trouvez un polynôme dans deux ou trois requêtes
-
04-11-2019 - |
Question
La boîte noire de $ f (x) $ signifie que je peux évaluer le polynôme $ f (x) $ à tout moment.
Saisir: Une boîte noire de monic polynôme $ f (x) in mathbb {z} ^ + [x] $ de degré $ d $.
Production: Les coefficients $ d $ du polynôme $ f (x) $.
Mon algorithme: laisser
$$ f (x) = x ^ {d} + a_ {d-1} x ^ {d-1} + cdots + a_1 x + a_0 $$
Évaluez Polynomial $ Mathcal {f (x)} $ à $ d $ de nombreux points à l'aide de la boîte noire et obtenez un système d'équations linéaires. Maintenant, je peux résoudre le système d'équations linéaires pour obtenir les coefficients souhaités.
Cependant, dans ce cas, j'ai besoin de $ mathcal {o (d)} $ de nombreuses requêtes à la boîte noire. Je veux minimiser le nombre de requêtes. Existe-t-il un moyen de réduire le nombre de requêtes à seulement deux ou trois?
Pas de solution correcte