Ключевое слово
13 | 12 | 2019
Новости Библиотеки
Шахматы Онлайн
Welcome, Guest
Username: Password: Remember me

TOPIC: алгоритмические задачки

алгоритмические задачки 30 Апр 2011 19:35 #61

  • Vladimirovich
  • Vladimirovich's Avatar
  • OFFLINE
  • Инквизитор
  • Posts: 82129
  • Thank you received: 1164
  • Karma: 82
PP написал(а):
Если кто не слышал, тут очень много задачек есть
projecteuler.net/index.php?section=problems
Не слышал. Спасибо
Каждому - своё.
Last Edit: 08 Нояб 2014 07:29 by Vladimirovich.

алгоритмические задачки 30 Апр 2011 19:37 #62

  • PP
  • PP's Avatar
  • OFFLINE
  • Боярин
  • Posts: 24546
  • Thank you received: 156
  • Karma: 4
Vladimirovich написал(а):
Не слышал. Спасибо
Можно выбрать интерсную для всех и порешать на форуме если найдется достаточное число интересующихся.

алгоритмические задачки 02 Май 2011 07:15 #63

  • PP
  • PP's Avatar
  • OFFLINE
  • Боярин
  • Posts: 24546
  • Thank you received: 156
  • Karma: 4
projecteuler.net/index.php?section=problems&id=79
A common security method used for online banking is to ask the user for three random characters from a passcode. For example, if the passcode was 531278, they may ask for the 2nd, 3rd, and 5th characters; the expected reply would be: 317.

The text file, keylog.txt, contains fifty successful login attempts.

Given that the three characters are always asked for in order, analyse the file so as to determine the shortest possible secret passcode of unknown length
Для безопасности банковских операций в интернете, пользователя просят ввести 3 случайных символа из пароля. Например, если пароль пользователя 531278, его могут попросить ввести 2ой, 3ий и 5ый символ; ожидаемый ответ 317. Текстовый файл projecteuler.net/project/keylog.txtkeylog.txt содержит 50 успешных попыток входа в систему. Зная, что символы всегда упорядочены в порядке возрастания, надо проанализировать файл и определить наикоротчайший возможный пароль неизвестной длины.
Last Edit: 08 Нояб 2014 07:30 by Vladimirovich.

алгоритмические задачки 02 Май 2011 07:28 #64

  • Vladimirovich
  • Vladimirovich's Avatar
  • OFFLINE
  • Инквизитор
  • Posts: 82129
  • Thank you received: 1164
  • Karma: 82
73162890
Каждому - своё.

алгоритмические задачки 02 Май 2011 08:30 #65

  • PP
  • PP's Avatar
  • OFFLINE
  • Боярин
  • Posts: 24546
  • Thank you received: 156
  • Karma: 4

алгоритмические задачки 02 Май 2011 11:47 #66

  • Vladimirovich
  • Vladimirovich's Avatar
  • OFFLINE
  • Инквизитор
  • Posts: 82129
  • Thank you received: 1164
  • Karma: 82
Кстати, я так понимаю, сложнее не получить ответ, а формализовать его так, чтобы заложиться на все возможные варианты - одинаковые цифры на разных позициях, недостаточно данных и т.д.

В предположении, что каждая цифра встречается в пароле только один раз, а в списке частичных паролей встречается как минимум один раз, надо фактически получить сортировку массива.
Хотя, как сейчас подумалось, для создания оптимального алгоритма есть резервы поработать.
Каждому - своё.

алгоритмические задачки 02 Май 2011 15:52 #67

  • PP
  • PP's Avatar
  • OFFLINE
  • Боярин
  • Posts: 24546
  • Thank you received: 156
  • Karma: 4
Если убрать условие наикоротчайшести, то задачи станет супер сложной имхо. Так как понадобиться бороться с циклами итд. Можно подумать о переформулировке кстати и попробовать решить усложенный вариант.

алгоритмические задачки 06 Май 2011 21:54 #68

  • PP
  • PP's Avatar
  • OFFLINE
  • Боярин
  • Posts: 24546
  • Thank you received: 156
  • Karma: 4
Такую задачку услышал.
В заданной строке найти коротчайшую подстроку содержащую заданный набор символов.
Например нам даны символы (е,т,н)
В строке: е-рейтинг является полнейшей билебердой, коротчайшей является выделенная часть.

Отредактировано PP (2011-05-07 05:35:39)

алгоритмические задачки 07 Май 2011 02:47 #69

  • Автор: procrastinator
  • Автор: procrastinator's Avatar
А если даны символы (е,р,й), то что будет решением?

алгоритмические задачки 07 Май 2011 23:39 #70

  • PP
  • PP's Avatar
  • OFFLINE
  • Боярин
  • Posts: 24546
  • Thank you received: 156
  • Karma: 4
Тогда е-рейтинг является полнейшей билебердой
Вот еще пример. Набор символов (х,р,и,с,т,о,с). Строка
отцвели уж давно. хризантемы в саду, но любовь все живет

Отредактировано PP (2011-05-08 03:46:13)

алгоритмические задачки 08 Май 2011 07:45 #71

  • Vladimirovich
  • Vladimirovich's Avatar
  • OFFLINE
  • Инквизитор
  • Posts: 82129
  • Thank you received: 1164
  • Karma: 82
Попробум тупо - создадим словарик 33 массивчик a. Запомним число букав в словарике.
Поставим там 1 для нужных символов
Поехали по строке - если a!=1 - игнор
Если 1, то ставим символ в итоговую строку, в словарике на a ставим ну 2

Доезжаем до конца. Если строка итоговая имеет достаточно букав, то получилось.

Каждому - своё.

алгоритмические задачки 08 Май 2011 19:47 #72

  • PP
  • PP's Avatar
  • OFFLINE
  • Боярин
  • Posts: 24546
  • Thank you received: 156
  • Karma: 4
Не совсем понял Ваше решение, а как гарнтируется каратчайшесть? И что будет если некоторые символы повторяются? Например символы (а,б,а,с). Строка: Одна баба сказала слава богу. Или Вы предлагаете тупо найти все возможные решения, а потом выбрать самое короткое?

алгоритмические задачки 09 Май 2011 07:27 #73

  • Vladimirovich
  • Vladimirovich's Avatar
  • OFFLINE
  • Инквизитор
  • Posts: 82129
  • Thank you received: 1164
  • Karma: 82
PP написал(а):
Не совсем понял Ваше решение, а как гарнтируется каратчайшесть?
Кратчайшесть?... Будет найдено ровно столько символов, сколько требуется.

PP написал(а):
И что будет если некоторые символы повторяются?
Да, надо немного поменять.
Изначально массив словаря содержит количество нужных букв
Например (а,б,а,с) - будет (2,1,............., 1, ............)
При нахождении нужной буквы делаем -- в нужной позиции.
Как только останутся все нули, значит все нашли

(2,1,............., 1, ............)
Одна баба сказала слава богу
(1,1,............., 1, ............)
Одна баба сказала слава богу
(1,0,............., 1, ............)
Одна баба сказала слава богу
(0,0,............., 1, ............)
Одна баба сказала слава богу
(0,0,............., 0, ............)
Все
Каждому - своё.

алгоритмические задачки 09 Май 2011 07:48 #74

  • PP
  • PP's Avatar
  • OFFLINE
  • Боярин
  • Posts: 24546
  • Thank you received: 156
  • Karma: 4
Vladimirovich написал(а):
Кратчайшесть?... Будет найдено ровно столько символов, сколько требуется.
Я наверное туплю, но мне кажется что если бы строка была слава богу одна баба сказала, то Вашим алгоритмом мы найдем слава б, а не баба с. Тоесть надо повторять процесс опять сдвинувшись в начальной позиции на следующую позицию из словарика?

алгоритмические задачки 09 Май 2011 07:54 #75

  • Vladimirovich
  • Vladimirovich's Avatar
  • OFFLINE
  • Инквизитор
  • Posts: 82129
  • Thank you received: 1164
  • Karma: 82
PP написал(а):
Я наверное туплю, но мне кажется что если бы строка была слава богу одна баба сказала, то Вашим алгоритмом мы найдем слава б, а не баба с. Тоесть надо повторять процесс опять сдвинувшись в начальной позиции на следующую позицию из словарика?
Нет. Цикл идет по самой строке. O(N)
А из словарика мы берем точечно, по коду символа.
Каждому - своё.

алгоритмические задачки 09 Май 2011 08:00 #76

  • Vladimirovich
  • Vladimirovich's Avatar
  • OFFLINE
  • Инквизитор
  • Posts: 82129
  • Thank you received: 1164
  • Karma: 82
(2,1,............., 1, ............)
слава богу одна баба сказала
(2,1,............., 0, ............)
слава богу одна баба сказала
(1,1,............., 0, ............)
слава богу одна баба сказала
(0,1,............., 0, ............)
слава богу одна баба сказала
(0,0,............., 0, ............)
Каждому - своё.

алгоритмические задачки 09 Май 2011 08:01 #77

  • PP
  • PP's Avatar
  • OFFLINE
  • Боярин
  • Posts: 24546
  • Thank you received: 156
  • Karma: 4
Vladimirovich написал(а):
Нет. Цикл идет по самой строке. O(N)
Дошло.

алгоритмические задачки 09 Май 2011 14:28 #78

  • Автор: procrastinator
  • Автор: procrastinator's Avatar
А я по-прежнему туплю. Мне кажется, что предложенный алгоритм найдет первое вхождение данных символов, да и то не обязательно самое короткое. Если та баба еще и заикается:\
ссслава богу одна баба сказала, то подстрока начнется с первой с, а не с третьей.
Навскидку, динамическое программирование должно находить решение за О(n^2). Ничего лучше с наскоку придумать не смог.

алгоритмические задачки 09 Май 2011 18:08 #79

  • Vladimirovich
  • Vladimirovich's Avatar
  • OFFLINE
  • Инквизитор
  • Posts: 82129
  • Thank you received: 1164
  • Karma: 82
procrastinator написал(а):
А я по-прежнему туплю. Мне кажется, что предложенный алгоритм найдет первое вхождение данных символов
Это так и есть. Был запрошен кратчайший....
Каждому - своё.

алгоритмические задачки 30 Сен 2011 17:07 #80

  • PP
  • PP's Avatar
  • OFFLINE
  • Боярин
  • Posts: 24546
  • Thank you received: 156
  • Karma: 4
Простенькое. Как быстро проверить если число является степенью двойки?

алгоритмические задачки 30 Сен 2011 17:31 #81

  • Vladimirovich
  • Vladimirovich's Avatar
  • OFFLINE
  • Инквизитор
  • Posts: 82129
  • Thank you received: 1164
  • Karma: 82
PP написал(а):
Простенькое. Как быстро проверить если число является степенью двойки?
Если в тупую, то цикл по разрядности числа x==(0x01i)
Если чего хитрое есть... надо подумать
Каждому - своё.

алгоритмические задачки 30 Сен 2011 17:47 #82

  • PP
  • PP's Avatar
  • OFFLINE
  • Боярин
  • Posts: 24546
  • Thank you received: 156
  • Karma: 4
Vladimirovich написал(а):
Если в тупую, то цикл по разрядности числа
Это да, но можно без цикла. В одну строчку.

алгоритмические задачки 30 Сен 2011 18:06 #83

  • Alexander
  • Alexander's Avatar
  • OFFLINE
  • Боярин
  • Posts: 10151
  • Thank you received: 103
  • Karma: 11
побитовое and для чисел x и x-1

алгоритмические задачки 30 Сен 2011 18:43 #84

  • PP
  • PP's Avatar
  • OFFLINE
  • Боярин
  • Posts: 24546
  • Thank you received: 156
  • Karma: 4
Alexander написал(а):
побитовое and для чисел x и x-1
Можно сказать, что правильно, но надо про х=0 не забыть.

алгоритмические задачки 30 Сен 2011 19:07 #85

  • Alexander
  • Alexander's Avatar
  • OFFLINE
  • Боярин
  • Posts: 10151
  • Thank you received: 103
  • Karma: 11
А x=0 это какая степень двойки?

алгоритмические задачки 30 Сен 2011 19:48 #86

  • PP
  • PP's Avatar
  • OFFLINE
  • Боярин
  • Posts: 24546
  • Thank you received: 156
  • Karma: 4
Alexander написал(а):
А x=0 это какая степень двойки?
Так в том то и дело, что никакая. Поэтому надо: х !(x (x-1))

алгоритмические задачки 21 Янв 2012 12:10 #87

  • Vladimirovich
  • Vladimirovich's Avatar
  • OFFLINE
  • Инквизитор
  • Posts: 82129
  • Thank you received: 1164
  • Karma: 82
habrahabr.ru/blogs/algorithm/136691/
На симпозиуме по дискретным алгоритмам ACM на этой неделе группа исследователей из MIT представила новый алгоритм быстрого преобразования Фурье sFFT (Sparse Fast Fourier Transform), который на некоторых задачах может быть в десятки или сотни раз быстрее классического БПФ.
Преобразование Фурье предполагает получение коэффициентов («амплитуд») при разложении исходной функции на элементарные составляющие — гармонические колебания с разными частотами. Быстрое преобразование Фурье позволяет ускорить этот процесс за счёт разделения вектора коэффициентов на два вектора, рекурсивном вычислении ДПФ для них, и объединении результатов в одно БПФ. Считается, что метод БПФ предложен в 1805 году Гауссом и переоткрыт в 1965 году, после чего нашёл широкое применение с распространением современных компьютеров. В последние 50 лет предпринималось немало попыток повысить эффективность БПФ, например, FFTW.
Новый алгоритм MIT, как заявляется, работает быстрее FFTW. Сравнение приводится в научной работе, а также на странице проекта.

Алгоритм sFFT (Sparse Fast Fourier Transform) создан на основе двух существующих фильтров (фильтр Гаусса и фильтр Чебышева) и нацелен на то, чтобы быстро найти фрагменты с «разреженным» сигналом (sparse signal) и определить исходную амплитуду в каждом из них. Сигнал разбивается на фрагменты (rapid sampling) до тех пор, пока не останется разреженный сигнал с единственной амплитудой. А уже там новый алгоритм выявляет её в 10 тыс. раз быстрее классического БПФ.

Такой метод не является универсальным, и сейчас учёные пытаются определить, в каких конкретно приложениях он даст наибольшую прибавку в производительности.
Страница проекта конечно так себе.... groups.csail.mit.edu/netmit/sFFT/
Каждому - своё.
Last Edit: 08 Нояб 2014 07:38 by Vladimirovich.

алгоритмические задачки 22 Янв 2012 09:44 #88

  • Автор: infolio
  • Автор: infolio's Avatar
Преобразование Фурье предполагает получение коэффициентов («амплитуд») при разложении исходной функции на элементарные составляющие — гармонические колебания с разными частотами. Быстрое преобразование Фурье позволяет ускорить этот процесс за счёт разделения вектора коэффициентов на два вектора, рекурсивном вычислении ...
да простит меня ГИ и все ув. Квантофорумчане, но м.б. это тот самый случай, когда при вычислениях (логарифмических, тригонометрических и т.п. функций, в т.ч. комплекснозначных с ТРЕБУЮЩЕЙСЯ точностью) всего-навсего достаточно определиться с требующейся точностью=дискретностью конечной Вселенной, и тогда сложения и умножения, например в ОДНОМЕРНЫХ координатах комплексной плоскости возможны с большей скоростью (не обязательно аппаратно или таблично, с использованием или без 100ричной системы счисления). З павагай

алгоритмические задачки 14 Нояб 2012 07:15 #89

  • PP
  • PP's Avatar
  • OFFLINE
  • Боярин
  • Posts: 24546
  • Thank you received: 156
  • Karma: 4
Топ 10 алгоритмов
www.uta.edu/faculty/rcli/TopTen/topten.pdf
Last Edit: 08 Нояб 2014 07:38 by Vladimirovich.

алгоритмические задачки 14 Нояб 2012 07:28 #90

  • Vladimirovich
  • Vladimirovich's Avatar
  • OFFLINE
  • Инквизитор
  • Posts: 82129
  • Thank you received: 1164
  • Karma: 82
PP написал(а):
Топ 10 алгоритмов
Интересно. Хотя я не думаю, что это самы сложные

P.S На всякий случай - PDF теперь тоже можно грузить на форум
Каждому - своё.
Last Edit: 09 Апр 2019 05:19 by Vladimirovich.
Moderators: Grigoriy
Рейтинг@Mail.ru

Научно-шахматный клуб КвантоФорум