Как стать автором
Обновить

Комментарии 38

НЛО прилетело и опубликовало эту надпись здесь
За 6 минут? Вот это действительно быстрое преобразование информации в знание.
НЛО прилетело и опубликовало эту надпись здесь
с вашим дыханием вы вполне могли бы зарабатывать ловцом жемчуга, родись вы на сотню-другую лет раньше.
image
Вот зачем тут эта картинка?
Да может не всерьез человек сказал ) Что вы на него набросились
А при чем тут, тогда, сарказм?
ирония )
но ведь ирония и сарказм — это разные вещи.
НЛО прилетело и опубликовало эту надпись здесь
Руководствуюсь определением в википедии.
— И, напоследок, задача, которую я разберу в следующем посте: у вас есть две строки одинаковой длины порядка 105 из букв A, T, G, C.

Похоже на геном… Чьи-то гены разбирать будем?
Скорее нет. На Харьковских сборах по программированию была задачка про короля и принца: нужно было узнать, является ли принц его сыном. Для этого требовалось вывести максимумальное число совпадающих символов при всех циклических сдвигах (например, для ATTA и TGAA это число — 3).

Не знаю, коррелирует ли это как-то с биологией. Думаю, что нет.
Конечно коррелирует…
Отцовство и определяется похожестью генов)
Просто думаю, что там всё-таки не циклические сдвиги, а что-нибудь другое. Например, где-нибудь квадраты вылезут (количество совпадающих A в квадрате, умножить на 17 плюс еще-что-нибудь).
это несложная задача — одну строку удваиваем, и ищем в ней вторую например используя «Префикс-функция. Алгоритм Кнута-Морриса-Пратта» e-maxx.ru/algo/prefix_function
Либо я не понял алгоритм, либо Вы не поняли задачу.
Например, есть строки ATTA и TGAA. Удвоили первую:
ATTAATTA
И вот ответ в задаче:
ATTAATTA
*TGAA***

Не дописал:
КМП «споткнётся» на символах T/G и не станет дальше проверять. Если бы требовалось найти сдвиг такой, что строки совпадут, да — КМП бы рулил.
да… что-то я непонял задачу
теперья ее понял и вот мой вариант решения:
удвоить и первую и вторую строку и найти «наибольшую общую подпоследовательность» и поделить это число на 2

А как ответ восстанавливать?
загнал меня в тупик:) надо что-то придумать…
Нет, эта задача не решается КМП. Кстати, контест был посвящен БПФ полностью, можно попрактиковаться: высшая и юниорская лиги на зеркале.
Несколько лет назад пытался решить эту задачку с помощью БПФ:
www.spoj.pl/problems/VFMUL/

Но так и не смог добиться что бы умножение на БПФ заработало правильно. =) Думаю мб ещё раз попробовать…
Если будет плохо работать с double (хотя там в комментариях пишут, что получили ОК) — можно пробовать long double. А еще я в следующем топике расскажу, как писать FFT в целых числах.
Еще из оптимайзов по длинной арифметике есть следующий: сделать базу не 10, а, например 103. Тогда «длина» числа сокращается в три раза, а операции выполняются с такой же скоростью — это существенно.
Ага, с помощью такого оптимайза я решал предыдущую задачу:
www.spoj.pl/problems/MUL/
Там и O(N^2) работает.

У меня была проблема не со скоростью, а с тем, что результат умножения не верный получался.
Какое издевательское название у статьи
Здравствуйте Григорий Яковлевич!
эй, то что автор топика освоил содержание первых двух курсов университета, ещё не делает его учёным! освоить линейную алгебру и математический анализ может каждый!
Использовал как-то БПФ в реализации длинной арифметики, умножение чисел. Выгода по времени начиналась где-то с 1000 битных числел по основанию 32, т.е. для многочленов это с 32 коэфициентами.
Вопрос к автору: «На какой машине проводились тесты?» Указывать тайминг без спецификации оборудования не очень корректно.
Я указывал, на самом деле, лишь для относительного сравнения.
Проводились на Core 2 Duo E4500 2.2GHz 2M Cache + 2GB. Вроде так.
ωa+ωb=ω(a+b)modn — опечатка
Спасибо, fixed
Я лично люблю в учебных целях — развивает мозг и выпрямляет руки.
Да и на олимпиадах библиотеки особо не поюзаешь. К тому же всегда интересно, как работает. Иногда даже можно какую-нибудь функцию обогнать.

Хорошая статья! Хотя всё это уже знал из университетского курса, было интересно посмотреть на эволюцию программы на C++.

Неплохо было бы в конце статьи сослаться на книжки Кормена и др. «Алгоритмы: построение и анализ» и Уоррена «Алгоритмические трюки для программистов» для заинтересовавшихся темой.

Надеюсь, не забросите это дело и расскажете побольше об интересных применениях БПФ.
На отборочном туре facebook hackercup предшествующем онсайту сего мероприятия была задача которая решалась БПФ. Никогда не забуду эти 1.5 часа написания и отладки. Наизусть я эту штуку не знал, да еще голова болела адски, да еще с нуля писал, на яве. Но она прошла и я побывал в калифорнии ^_^
Зарегистрируйтесь на Хабре, чтобы оставить комментарий

Публикации

Истории