Решение задачи с многочленом

@Mufasa85 · Регистрация: 20.09.2021

Студворк — интернет-сервис помощи студентам

Уважаемые магистры Python.

Помогите помочь и решить задачу, доселе мне невиданную. Не могу даже подступить к решению.
Задача во вложении. Ввод - вывод не самая принципиальная часть.
Файл с задачей во вложении.

@eaa · 26.09.2021, 21:17

условие задачи, тут принято прикладывать в виде текста

@Mufasa85 · 26.09.2021, 22:54 **[ТС]**

Даны n различных чисел a_i (2≤n≤6, ∣∣a_i∣∣≤10⁹).
Найдите минимальное k, для которого существует многочлен f(x)=b₀+b₁x+…+b_k*x^k и перестановка p чисел от 1 до n, что f(p_i)=a_i.
Обратите внимание, что в одном запуске необходимо обработать несколько тестовых наборов.

Формат ввода
В первой строке записано число t (1≤t≤100) — количество тестовых наборов.
Далее следуют описания тестовых наборов. Каждый тестовый набор занимает 2 строки. В первой строке записано число n (2≤n≤6). Во второй строке записаны n чисел a_i. Все a_i различны.

Формат вывода
Для каждого тестового набора выведите требуемое значение k в отдельной строке.

@Catstail · 27.09.2021, 09:21

Если совсем тупо, то можно попробовать так. Точек всего n<6. Это менее 120 перестановок. Меняем степень полинома от 1 до n. Для каждой степени ищем аппроксимирующий полином методом МНК (понадобится метод Гаусса или, если хотим все делать в целых числах - метод Крамера). В крайнем случае точки должны "лечь" на полином степени n (теорема Лагранжа). Интересно, откуда задача?

@u235 · 27.09.2021, 21:38

Вопрос ко всем:
Я не понимаю, что такое полином от перестановки? Объясните на примере, если можно.
Перестановка чисел от 1 до 3 (например) это упорядоченный набор, например (1,2,3) или (2,1,3) и т.д.. Как вычислить значение полинома одной переменной от такого набора чисел?
Что значит i-я перестановка? первая это какая? а вторая?

@eaa · 27.09.2021, 23:41

система линейных уравнений получается

например для:
n = 3
a = [-505, -592, -679]

нужно проверить такие системы и найти минимальное k

Code
1
2
3
4
5
6
f(1) = -505, f(2) = -592, f(3) = -679
f(1) = -505, f(3) = -592, f(2) = -679
f(2) = -505, f(1) = -592, f(3) = -679
f(2) = -505, f(3) = -592, f(1) = -679
f(3) = -505, f(1) = -592, f(2) = -679
f(3) = -505, f(2) = -592, f(1) = -679

Добавлено через 13 минут
Mufasa85, numpy можно подключать?

@Catstail · 28.09.2021, 07:07

u235, я понял так, что для x=[1,2,3,...n] нужно всеми способами переставить a_i. И для каждой перестановки искать полином. Выше я немного ошибся: для n=6 перестановок будет, конечно, 720.

@u235 · 28.09.2021, 08:40

eaa, Catstail, спасибо за пояснения и пример.

Сообщение от eaa

например для:
n = 3
a = [-505, -592, -679]

Я так понимаю, что максимально возможное значение k==2, т.е. парабола по трем точкам.
А минимальное - 1, и это будет в том случае, если числа а упорядочены по возрастанию или убыванию:

Code
1
2
3
f(1) = -505, f(2) = -592, f(3) = -679
или
f(3) = -505, f(2) = -592, f(1) = -679

Ну и разница между числами должна быть константой.
т.е. проверить на k=1 просто..

@solnce · 03.11.2021, 19:14

решил задачу? Мучаюсь с ней, не могу написать нормальное решение. Пришлешь пожалуйста свое?

@eaa · 04.11.2021, 08:33

для ускорения на 100 тестах нужен прекалк,
ну и подсчет вести по другому так как на каждом шаге меняется не более 6 переменных.

Добавлено через 1 минуту
я решение давно уже удалил, тк не было "фидбека" от ТС.

@Paul1298 · 26.05.2023, 08:33

Mufasa85, решил?

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Web (WebAssembly): Реализация движения на Box2D v3 - трение и коллизии с повёрнутыми стенами 8Observer8 20.02.2026 Содержание блога Box2D позволяет легко создать главного героя, который не проходит сквозь стены и перемещается с заданным трением о препятствия, которые можно располагать под углом, как верхнее. . .	Конвертировать закладки radiotray-ng в m3u-плейлист damix 19.02.2026 Это можно сделать скриптом для PowerShell. Использование . \СonvertRadiotrayToM3U. ps1 <path_to_bookmarks. json> Рядом с файлом bookmarks. json появится файл bookmarks. m3u с результатом. # Check if. . .	Семь CDC на одном интерфейсе: 5 U[S]ARTов, 1 CAN и 1 SSI Eddy_Em 18.02.2026 Постепенно допиливаю свою "многоинтерфейсную плату". Выглядит вот так: https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=11617&stc=1&d=1771445347 Основана на STM32F303RBT6. На борту пять. . .	Камера Toupcam IUA500KMA Eddy_Em 12.02.2026 Т. к. у всяких "хикроботов" слишком уж мелкий пиксель, для подсмотра в ESPriF они вообще плохо годятся: уже 14 величину можно рассмотреть еле-еле лишь на экспозициях под 3 секунды (а то и больше),. . .
И ясному Солнцу zbw 12.02.2026 И ясному Солнцу, и светлой Луне. В мире покоя нет и люди не могут жить в тишине. А жить им немного лет.	«Знание-Сила» zbw 12.02.2026 «Знание-Сила» «Время-Деньги» «Деньги -Пуля»	SDL3 для Web (WebAssembly): Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 12.02.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами и вызывать обработчики событий столкновения. . . .	SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 11.02.2026 Содержание блога Библиотека SDL3 содержит встроенные инструменты для базовой работы с изображениями - без использования библиотеки SDL3_image. Пошагово создадим проект для загрузки изображения. . .

@Mufasa85 0 / 0 / 0 Регистрация: 20.09.2021 Сообщений: 5

	Решение задачи с многочленом 26.09.2021, 20:56. Показов 2914. Ответов 10 Метки нет (Все метки) Уважаемые магистры Python. Помогите помочь и решить задачу, доселе мне невиданную. Не могу даже подступить к решению. Задача во вложении. Ввод - вывод не самая принципиальная часть. Файл с задачей во вложении. Миниатюры 0

@eaa Status 418 4584 / 2350 / 601 Регистрация: 26.11.2017 Сообщений: 5,262 Записей в блоге: 3
	26.09.2021, 21:17
	условие задачи, тут принято прикладывать в виде текста 1

@Mufasa85 0 / 0 / 0 Регистрация: 20.09.2021 Сообщений: 5
	26.09.2021, 22:54 [ТС]
	Даны n различных чисел a_i (2≤n≤6, ∣∣a_i∣∣≤10⁹). Найдите минимальное k, для которого существует многочлен f(x)=b₀+b₁x+…+b_kx^k и перестановка p чисел от 1 до n, что f(p_i)=a_i. Обратите внимание, что в одном запуске необходимо обработать несколько тестовых наборов. Формат ввода* В первой строке записано число t (1≤t≤100) — количество тестовых наборов. Далее следуют описания тестовых наборов. Каждый тестовый набор занимает 2 строки. В первой строке записано число n (2≤n≤6). Во второй строке записаны n чисел a_i. Все a_i различны. Формат вывода Для каждого тестового набора выведите требуемое значение k в отдельной строке. 0

@Catstail Супер-модератор 38174 / 21109 / 4307 Регистрация: 12.02.2012 Сообщений: 34,711 Записей в блоге: 14
	27.09.2021, 09:21
	Если совсем тупо, то можно попробовать так. Точек всего n<6. Это менее 120 перестановок. Меняем степень полинома от 1 до n. Для каждой степени ищем аппроксимирующий полином методом МНК (понадобится метод Гаусса или, если хотим все делать в целых числах - метод Крамера). В крайнем случае точки должны "лечь" на полином степени n (теорема Лагранжа). Интересно, откуда задача? 1

@u235 5516 / 2869 / 571 Регистрация: 07.11.2019 Сообщений: 4,759
	27.09.2021, 21:38
	Вопрос ко всем: Я не понимаю, что такое полином от перестановки? Объясните на примере, если можно. Перестановка чисел от 1 до 3 (например) это упорядоченный набор, например (1,2,3) или (2,1,3) и т.д.. Как вычислить значение полинома одной переменной от такого набора чисел? Что значит i-я перестановка? первая это какая? а вторая? 0

@Catstail Супер-модератор 38174 / 21109 / 4307 Регистрация: 12.02.2012 Сообщений: 34,711 Записей в блоге: 14
	28.09.2021, 07:07
	u235, я понял так, что для x=[1,2,3,...n] нужно всеми способами переставить a_i. И для каждой перестановки искать полином. Выше я немного ошибся: для n=6 перестановок будет, конечно, 720. 1

@solnce 0 / 0 / 0 Регистрация: 02.11.2021 Сообщений: 2
	03.11.2021, 19:14
	решил задачу? Мучаюсь с ней, не могу написать нормальное решение. Пришлешь пожалуйста свое? 0

@eaa Status 418 4584 / 2350 / 601 Регистрация: 26.11.2017 Сообщений: 5,262 Записей в блоге: 3
	04.11.2021, 08:33
	для ускорения на 100 тестах нужен прекалк, ну и подсчет вести по другому так как на каждом шаге меняется не более 6 переменных. Добавлено через 1 минуту я решение давно уже удалил, тк не было "фидбека" от ТС. 0

@Paul1298 0 / 0 / 0 Регистрация: 11.11.2021 Сообщений: 1
	26.05.2023, 08:33
	Mufasa85, решил? 0