Начало
Рабочее место участника
| Выбрать соревнование | Задачи | Послать решение | Результаты проверки | Статистика по задачам | Вопросы и ответы | Результаты соревнования | Состояние сервера | Изменить данные | Управление командой | Помощь |
Задачи
2765. Умножение полиномов с помощью DFT
Учебные задачи: АиСД. Полиномы, матрицы| 01/09/2007 | Алгоритмы и структуры данных. Полиномы и матрицы (D) |
Ограничения: время – 250ms/500ms, память – 128MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
Написать функцию для умножения полиномов с помощью DFT (изменить int -> double и не делать округление).
Сравнить время и точность вычисления для N=1000, N=10000, N=100000 с квадратичным алгоритмом. В качестве коэффициентов полиномов задать все 1.
В качестве решения отправить текстовый файл с таблицей, в которой для каждого N будет указано время выполнения в мкс алгоритма умножения через DFT и квадратичного алгоритма, максимум абсолютной ошибки DFT по сравнению с квадратичным алгоритмом.
Пример текстового файла
1000 101 1001 1.0000e-10 10000 200 10002 1.5000e-9 100000 305 100003 2.5000e-8
