Codegolf — Рациональная Полиномиальная Интерполяция

Объяснение

В этом задании вам будет предоставлен набор Н очки (х₁, да₁),…,(х_Н, да_Н) с отчетливым х_я значения, и ваша задача — интерполировать полином через эти точки. Если вы знаете, что такое интерполяция Лагранжа, вы можете пропустить этот раздел.

Цель полиномиальная интерполяция заключается в построении (уникального) многочлена р(х) со степенью Н-1 (для более высоких степеней существуют бесконечные решения), для которых р(х_я) = у_я для всех я = 1…Н. Один из способов сделать это — построить Н Полиномы базиса Лагранжа и образуют линейную комбинацию. Такой базисный полином определяется следующим образом:

Как вы можете видеть, если вы оцените л_я в точках х₁,…,х_я-1 ,х_{я +1},…_,х Н_{это 0 по построению и 1 для x}я_{, умножая на y} я_{изменит только значение в точке x} я_{и установите его на y}я

. Теперь, имея N таких многочленов, которые равны 0 в каждой точке, кроме одной, мы можем просто сложить их и получить желаемый результат. Итак, окончательное решение будет:

• Испытание ввод будет состоять из Н
• точки данных в любом разумном формате (список кортежей, точки, набор и т. д.)
• все координаты будут иметь целочисленное значение
• вывод будет полиномом в любом разумном формате: список коэффициентов, полиномиальный объект и т. д.
• результат должен быть точным - это означает, что некоторые решения будут иметь рациональные коэффициенты

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

  instead of [1,0,0] форматирование не имеет значения( 1/2 for 1 % 2 или
• и т. д.), если это разумно вам не придется обрабатывать недопустимые входные данные (например, пустые входные данные или входные данные, где х

координаты повторяются)

Тестовые случаи 1 corresponds to the polynomial В этих примерах коэффициенты перечислены в порядке убывания (например,²):

х

Париж/GP, 14 байт

 
 
 
 æc 
 
 
 

Берет два списка y and x в качестве ввода. Выводит полином.

[Попробуйте онлайн!][TIO-jbggy7a1]

Париж/GP, 35 байт, без встроенной

Берет два списка · and ↙ в качестве ввода. Выводит список коэффициентов.

Попробуйте онлайн!

Зачислить, 25 байт

Попробуйте онлайн!

Монадическая ссылка принимает массив длины 2 (например, Ḣ‡ḟ¹‡,€-÷_Ḣ¥€§æc/§₱W€$↙·Ṫ ) as input. The first element of the array is list of x value, the second is list of y value. Output as list of coefficient in increasing degree.

Потому что @HyperNeutrino забыл обернуть числа в рациональную оболочку, если они вычисляются в списке (Попробуйте онлайн!) аргумент должен быть жестко запрограммирован в коде.

[y1, ..., yn] is necessary because HyperNeutrino make some mistake in implementing [x1, ..., xn] Не знаю (или это особенность? Не уверен)

Эквивалентный код Mathematica:

Попробуйте онлайн!

где [y1, ..., yn] and [x1, ..., xn] список координат. Это печатает полином.

Что Enlist имеет для этого испытания:

• Встроенная поддержка рациональных чисел.
• Свертка polinterpolate (my feature request)