Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 38
За 6 минут? Вот это действительно быстрое преобразование информации в знание.
с вашим дыханием вы вполне могли бы зарабатывать ловцом жемчуга, родись вы на сотню-другую лет раньше.
Вот зачем тут эта картинка?
Да может не всерьез человек сказал ) Что вы на него набросились
А при чем тут, тогда, сарказм?
ирония )
но ведь ирония и сарказм — это разные вещи.
Руководствуюсь определением в википедии.
— И, напоследок, задача, которую я разберу в следующем посте: у вас есть две строки одинаковой длины порядка 105 из букв A, T, G, C.
Похоже на геном… Чьи-то гены разбирать будем?
Похоже на геном… Чьи-то гены разбирать будем?
Скорее нет. На Харьковских сборах по программированию была задачка про короля и принца: нужно было узнать, является ли принц его сыном. Для этого требовалось вывести максимумальное число совпадающих символов при всех циклических сдвигах (например, для ATTA и TGAA это число — 3).
Не знаю, коррелирует ли это как-то с биологией. Думаю, что нет.
Не знаю, коррелирует ли это как-то с биологией. Думаю, что нет.
Конечно коррелирует…
Отцовство и определяется похожестью генов)
Отцовство и определяется похожестью генов)
это несложная задача — одну строку удваиваем, и ищем в ней вторую например используя «Префикс-функция. Алгоритм Кнута-Морриса-Пратта» e-maxx.ru/algo/prefix_function
Либо я не понял алгоритм, либо Вы не поняли задачу.
Например, есть строки ATTA и TGAA. Удвоили первую:
И вот ответ в задаче:
Например, есть строки ATTA и TGAA. Удвоили первую:
ATTAATTAИ вот ответ в задаче:
ATTAATTA
*TGAA***
Не дописал:
КМП «споткнётся» на символах T/G и не станет дальше проверять. Если бы требовалось найти сдвиг такой, что строки совпадут, да — КМП бы рулил.
КМП «споткнётся» на символах T/G и не станет дальше проверять. Если бы требовалось найти сдвиг такой, что строки совпадут, да — КМП бы рулил.
да… что-то я непонял задачу
теперья ее понял и вот мой вариант решения:
удвоить и первую и вторую строку и найти «наибольшую общую подпоследовательность» и поделить это число на 2
теперья ее понял и вот мой вариант решения:
удвоить и первую и вторую строку и найти «наибольшую общую подпоследовательность» и поделить это число на 2
Несколько лет назад пытался решить эту задачку с помощью БПФ:
www.spoj.pl/problems/VFMUL/
Но так и не смог добиться что бы умножение на БПФ заработало правильно. =) Думаю мб ещё раз попробовать…
www.spoj.pl/problems/VFMUL/
Но так и не смог добиться что бы умножение на БПФ заработало правильно. =) Думаю мб ещё раз попробовать…
Если будет плохо работать с double (хотя там в комментариях пишут, что получили ОК) — можно пробовать long double. А еще я в следующем топике расскажу, как писать FFT в целых числах.
Еще из оптимайзов по длинной арифметике есть следующий: сделать базу не 10, а, например 103. Тогда «длина» числа сокращается в три раза, а операции выполняются с такой же скоростью — это существенно.
Еще из оптимайзов по длинной арифметике есть следующий: сделать базу не 10, а, например 103. Тогда «длина» числа сокращается в три раза, а операции выполняются с такой же скоростью — это существенно.
Ага, с помощью такого оптимайза я решал предыдущую задачу:
www.spoj.pl/problems/MUL/
Там и O(N^2) работает.
У меня была проблема не со скоростью, а с тем, что результат умножения не верный получался.
www.spoj.pl/problems/MUL/
Там и O(N^2) работает.
У меня была проблема не со скоростью, а с тем, что результат умножения не верный получался.
Какое издевательское название у статьи
Здравствуйте Григорий Яковлевич!
Использовал как-то БПФ в реализации длинной арифметики, умножение чисел. Выгода по времени начиналась где-то с 1000 битных числел по основанию 32, т.е. для многочленов это с 32 коэфициентами.
Вопрос к автору: «На какой машине проводились тесты?» Указывать тайминг без спецификации оборудования не очень корректно.
ωa+ωb=ω(a+b)modn — опечатка
www.fftw.org
любят люди писать велосипеды…
любят люди писать велосипеды…
Хорошая статья! Хотя всё это уже знал из университетского курса, было интересно посмотреть на эволюцию программы на C++.
Неплохо было бы в конце статьи сослаться на книжки Кормена и др. «Алгоритмы: построение и анализ» и Уоррена «Алгоритмические трюки для программистов» для заинтересовавшихся темой.
Надеюсь, не забросите это дело и расскажете побольше об интересных применениях БПФ.
Неплохо было бы в конце статьи сослаться на книжки Кормена и др. «Алгоритмы: построение и анализ» и Уоррена «Алгоритмические трюки для программистов» для заинтересовавшихся темой.
Надеюсь, не забросите это дело и расскажете побольше об интересных применениях БПФ.
На отборочном туре facebook hackercup предшествующем онсайту сего мероприятия была задача которая решалась БПФ. Никогда не забуду эти 1.5 часа написания и отладки. Наизусть я эту штуку не знал, да еще голова болела адски, да еще с нуля писал, на яве. Но она прошла и я побывал в калифорнии ^_^
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Быстрое умножение многочленов при помощи преобразования Фурье — это просто