Ответы пользователя по тегу Алгоритмы
  • Как разбить числа по группам так, чтобы в группах находились близкие по значению числа?

    @Mercury13
    Программист на «си с крестами» и не только
    Это называется кластеризация, и самый ходовой метод для неё — K-means.
    Ответ написан
    2 комментария
  • Сложность алгоритмов для определения подстроки в строке?

    @Mercury13
    Программист на «си с крестами» и не только
    H = |haystack|, n = |needle|, a — размер алфавита.
    Примитивный алгоритм: предобработки нет, работа в среднем 2H, максимум O(Hn).
    Типичные быстрые алгоритмы: предобработка O(n) или O(n+a), работа в среднем <H, максимум O(Hn).
    Автоматные алгоритмы: предобработка O(na) или O(n+a), работа =H.
    Существуют СТРАШНЫЕ алгоритмы с работой в среднем <H и максимум O(H), где применяются — не знаю.
    Если нужно проводить несколько поисков одной «иголки» в разных «стогах», нужна всего одна предобработка.
    Ответ написан
    Комментировать
  • Как работает Hmac?

    @Mercury13
    Программист на «си с крестами» и не только
    HMAC — это так называемая имитовставка.
    То есть нечто среднее между хэш-функцией и электронной подписью.
    Тот, кто изменил сообщение и не знает ключа, НЕ МОЖЕТ подделать имитовставку — в отличие от хэш-функции.
    Но ключ подписи и проверки ОДИН И ТОТ ЖЕ — в отличие от электронной подписи.

    В современных веб-службах имитовставка используется для одного из вариантов аутентификации: сообщения закрыты прочным транспортным протоколом, но нет возможности проверить, тот ли человек на другом конце провода. Для этого подписываем всё тело запроса, и сервер, владеющий тем же ключом, сможет убедиться, что запрос сформирован нужным человеком.
    Ответ написан
    7 комментариев
  • Как найти слово, гарантированно отсутствующее в наборе?

    @Mercury13 Автор вопроса
    Программист на «си с крестами» и не только
    Придумал, причём тупо. Комбинаторикой высчитываем, какой длины (по принципу Дирихле) должно быть наше слово: например, если у нас цифры от 0 до 9 и 125 строк, достаточно взять трёхзначные. Вот мы берём 126 битов (ну или 128 для круглого счёта), из наших чисел берём только трёхзначные и начинаем заполнять биты. Есть, например, 025 — вот в 25-й бит и суём единичку. После этого остаётся найти в битовой маске ноль и преобразовать в нашу строку: на 45-м месте — значит, 045.
    Ответ написан
    Комментировать
  • Как правильно оценить сложность алгоритма O(n)?

    @Mercury13
    Программист на «си с крестами» и не только
    f(x) = O(g(x)) при x→y — это так называемый символ Ландау.
    И означает, что при x, достаточно близких к y, f(x)<k·g(x). Так что 2x или 1000x — извините, не важно.

    Отсюда же запись O(log n) — ведь разные логарифмы отличаются на константу, которую символы Ландау съедают.

    Чем символы Ландау интересны программистам?
    1. Кэшами, быстрым процессором, «хитрым» программированием и прочим на больших наборах данных можно выиграть, например, в разы. Порядком сложности алгоритма — намного, намного больше.
    2. Пока закон Мура действовал, объёмы данных росли экспоненциально — так что быстро доходило до того, что программу начинали использовать на наборах данных, для которых она просто не предназначалась.
    3. Практически приемлемые алгоритмы обычно имеют небольшую сложность — например, до O(n³). И, например, линейный алгоритм за приемлемое время обработает миллионы элементов, n log n — сотни тысяч, n² — тысячи, n³ — сотни.
    4. Программисты отлаживают на небольших наборах данных, которые можно обработать вручную. Так что разница между отладочными и боевыми данными бывает большая — а значит, порядок сложности должен влиять сильнее, чем остальные факторы.
    Ответ написан
    1 комментарий
  • Как выполнить размещение k элементов из n?

    @Mercury13
    Программист на «си с крестами» и не только
    Будут повторы?
    Если не будет — то достаточно отсортировать char’ы и использовать числовой алгоритм.
    Если будут — ищите «размещения с повторами», и тоже сортируйте.
    Ответ написан
    Комментировать
  • Где и как используют деревья в программировании?

    @Mercury13
    Программист на «си с крестами» и не только
    1. Нечто, действительно имеющее древовидную форму — например, деревья каталогов на дисках, деревья сцен в 3D, деревья принятия решений.
    2. Деревья поиска — структуры данных, позволяющие добавлять-убирать объекты и позволяющие быстрый поиск по ключу. Например, словари всякие, индексы БД.
    3. Так называемая куча — структура данных, позволяющая добавлять-убирать объекты и поддерживающая минимальный элемент в этом множестве. Используется как вспомогательная в каких-нибудь алгоритмах.
    4. Двоичное разбиение пространства в 3D — известный способ сортировки от дальних к ближним.

    Кроме того, деревья могут не существовать в памяти, а только подразумеваться — в синтаксических разборах, теоретико-игровых обсчётах. Хотя один из вариантов промежуточного хранения разобранной формулы, чтобы потом по ней проводить многократные расчёты — дерево (но чаще используют обратную польскую запись).
    Ответ написан
    Комментировать
  • Какое максимальное количество операций в бинарном поиске?

    @Mercury13
    Программист на «си с крестами» и не только
    ceil(log2(n + 1))

    Поскольку ответов на каждый конкретный вопрос возможны три штуки (больше/меньше/угадал), тупая оценка количеством битов невозможна, надо учитывать зависимости между этими ответами.

    Доказательство.
    Докажем обратное: за k шагов можно угадать 2k−1 чисел.

    БАЗА. 1 угадывается с первого раза. 2 с первого раза уже не угадаешь.

    ШАГ. k → k+1. Другими словами, нам известно, что 2k−1 угадать можно, а 2k уже нельзя.
    Берём центральное, и остаётся 2k−1 слева и 2k−1 справа. → n = 2·(2k−1)+1 = 2k+1−1
    Если n = 2k+1 или больше, хоть в одной половинке будет 2k, что, по предположению индукции, невозможно.
    Ответ написан
    4 комментария
  • Какой алгоритм используется в пакетных менеджерах?

    @Mercury13
    Программист на «си с крестами» и не только
    Циклических зависимостей (B → C → B) обычно не бывает. Но вам нужен самый тупой поиск — например, в глубину.
    Ответ написан
    3 комментария
  • Почему выполнение программы ускоряется?

    @Mercury13
    Программист на «си с крестами» и не только
    Потому что у вас неэффективный алгоритм вычисления НОД, работающий на вычитании, а не на делении с остатком.
    Естественно, НОД(1,6) = НОД(1, 6−1=5) = НОД(1, 5−1=4) = НОД(1, 4−1=3) = НОД(1, 3−1=2) = НОД(1, 2−1=1) = НОД(1, 1−1=0) = 1
    НОД(2,6) = НОД(2, 6−2=4) = НОД(2, 4−2=2) = НОД(2, 2−2=0) = 2
    С арифметическим переполнением никак не связано. Просто даже в результате переполнения получились немаленькие числа.

    Как надо: НОД(1,6) = НОД(6, 1%6=1) = НОД(1, 6%1=0) = 1
    Аналогично для НОД(6,2) — в общем, сходится довольно быстро.
    Ответ написан
    Комментировать
  • Можете помочь с алгоритмом сортировки?

    @Mercury13
    Программист на «си с крестами» и не только
    1. Вам свезло, что длина массива — ровно 8, то есть степень двойки. Ваш алгоритм никак не приспособлен к тому, что на очередном шаге длина массива окажется нечётной.
    2. Я не знаю, как происходит слайсинг массивов и передача параметров в Go, но надо проверять, насколько много перевыделения лишней памяти.
    3. Опять свезло — левая и правая половинки расходуются очень равномерно: один слева — один справа. Если взять отсортированный массив { 1, 2, 3, 4, 5, 6, 7, 8 }, когда сначала расходуем левую половинку, потом правую — должно заглючить. На самом деле слияние массивов содержит ещё больше всяких условий, и на каждом сравнении мы кладём в результирующий массив не два элемента из разных массивов, а один — меньший. И соответственно сдвигаем один из индексов-кареток.
    Ответ написан
    3 комментария
  • Как найти машинную бесконечность?

    @Mercury13
    Программист на «си с крестами» и не только
    Важный вопрос: есть ли неявная единица и денормализованные числа?
    Считаем, что всё-таки есть, порядок несмещённый, записан дополнительным кодом, денормализованное число записывается 10…00 в порядке. (А то всяко бывает, в нашем родном float порядок смещён на 01…11).
    Тогда максимальное число, которое можно записать, равняется 1,1…1112·22^13−1.
    Ну а бесконечность — примерно 2·22^13−1 = 22^13.
    Wolfram Alpha говорит, что это 1,091·102466.
    Ответ написан
    5 комментариев
  • В каком случае программа выдает ложный результат?

    @Mercury13
    Программист на «си с крестами» и не только
    T = 4, X = 2, N = 1. Получаются 2 минуты, хотя надо четыре.
    Надо не ceilDiv(nt, x), a t·ceilDiv(n,x).
    Ну и с такими ограничениями ceilDiv(n, x) = (n + x - 1) / x, без дробной арифметики.
    (Собирая всё в одно выражение, не забывайте скобки!)
    Ответ написан
    3 комментария
  • Как решить задачу на or?

    @Mercury13
    Программист на «си с крестами» и не только
    Это невозможно.
    Пусть у нас есть массив, состоящий НЕ ЦЕЛИКОМ из нулей и содержащий хоть один ноль.
    Возьмём любой ненулевой элемент a и про-XOR’им с ним все элементы массива.
    Ноль переместился в другое место, а результаты нашей операции a[i] xor a[j] не изменились.
    Получается, что первый массив неотличим от второго, и нули в них в разных местах.

    Например: массив 0 1 2 3 неотличим от массива 1 0 3 2.
    0 xor 1 = 1 … 1 xor 0 = 1
    0 xor 2 = 2 … 1 xor 3 = 2
    0 xor 3 = 3 … 1 xor 2 = 3
    1 xor 2 = 3 … 0 xor 3 = 3
    1 xor 3 = 2 … 0 xor 2 = 2
    2 xor 3 = 1 … 3 xor 2 = 1
    Ну а 0 xor 0, 1 xor 1, 2 xor 2 и 3 xor 3 всегда были нулями.

    ------------------

    В версии с OR — берём a[0] or a[i], поддерживая AND этих сумм и подсчитывая, сколько раз этот самый AND среди наших сумм встречается.
    1) Если числа, превышающие AND, встречаются столько раз, сколько [ну, подсчитайте, сколько чисел от 0 до N−1 будут иметь все эти биты] — отбросим наше 0-е число, а также проверенные числа, чья сумма НЕ совпадает с AND, и начнём сначала.
    ПРИМЕР: 2 3 4 0 1
    2 or 3 = 5, AND=5
    2 or 4 = 6, AND=2 — бит 2 тут будут иметь только 2 и 3, отбрасываем 2, 3 и 4.

    Если AND встречается 2k−1 раз (k — кол-во битов в AND), оставим ТОЛЬКО ЭТИ случаи и снова начнём сначала.
    ПРИМЕР: 2 1 0 3
    2 OR 1 = 3, AND=3
    2 OR 0 = 2, AND=2
    2k−1=1, и нам хватает одной встречи числа 2 — оставляем 2 и 0.

    Остались три числа — действуем по стандартному алгоритму.
    Осталось одно число — оно 0.
    Остались два числа — одно 0, другое некий бит. Мы должны найти число, этого бита не имеющее. Снова проходим по результату предыдущего обхода, суммируя сначала с одним, потом с другим. Видим разницу — понятно, где 0, а где бит.
    Ответ написан
  • Как сделать алгоритм?

    @Mercury13
    Программист на «си с крестами» и не только
    Пусть минимальный простой делитель a.
    Тогда минимальный делитель a (будь мин.делитель составной — нашёлся бы меньший), максимальный — x/a (по сходной причине), x=91·a².
    Кроме того, 91 = 7·13, и потому a <= 7.
    2²·91 и 3²·91 до четырёхзначного явно не дотягивают.
    А вот следующее — a=5 — даёт 2275 = 5²·7·13.
    Также должно подойти a=7, x=7³·13=4459.
    (Раз тут математика, часто запрещён даже калькулятор, потому попытался написать так, как думал бы человек без калькулятора)
    Ответ написан
    Комментировать
  • В чём главное отличие информации от ключей?

    @Mercury13
    Программист на «си с крестами» и не только
    Информация в деревьях — это…
    • ключи (то есть string в map<string, int>)
    • любая информация, которую программист прицепил на элементы дерева (то есть int в map<string, int>)
    • информация, которая служит, чтобы поддерживать само дерево и его сбалансированность: указатели, флаг R/B…
    Ответ написан
    Комментировать
  • Существует ли структура данных «расширяемая 2D-таблица»?

    @Mercury13 Автор вопроса
    Программист на «си с крестами» и не только
    Пока остановился на таком механизме.
    Есть два одномерных массива — оглавление строк и оглавление столбцов, два одномерных массива — задействованность строк/столбцов, а также двухмерный массив — буфер.

    a[i,j] := buffer[rowIndex[i−i0], colIndex[j−j0]]

    Если в rowIndex[i−i0] замечен маркер незадействованности, находим незадействованную строку и прописываем её в оглавлении.
    Чтобы меньше перевыделять памяти, перевыделение идёт импульсами и с запасом. Например, хотим 20 строк, а выделяем сразу на 30.
    Такой массив способен только расширяться, но этого мне хватает.
    Ответ написан
    Комментировать
  • Как понять условие задачи?

    @Mercury13
    Программист на «си с крестами» и не только
    Подобный вывод используется, чтобы было понятно, что вы способны, если нужно, вычислить с точностью до обыкновенной дроби, но в длинную арифметику (а дроби бывают длинные) не лезть. Ибо реализации длинной арифметики различаются по эффективности от ЯП к ЯП, а в некоторых вообще нет штатной (внешние библиотеки в олимпиадном программировании запрещены).

    Числа P и Q высчитываем с точностью до остатка от деления на Z := 109+ 7.

    Авторы обещают, что Q mod Z ≠ 0. Z — простое. Тогда НОД(Q mod Z, Z) = 1. Так называемый расширенный алгоритм Евклида (гуглите!) позволяет подобрать такие числа, чтобы m(Q mod Z) + nZ = 1.

    Ваша задача — вывести ((P mod Z) · m) mod Z. Специально указал дважды mod Z: первое у вас будет при работе с числом P, второе — при генерации вывода.

    Почему так? Возьмём вместо здоровенного Z цифру поменьше, 17. Если у вас получился результат 100/400, при расчётах выйдет цифра 15/9, и 9·2+17·(−1) = 1, и ваша задача — вывести (15·2) mod 17 = 13.

    Если же у вас получилось, например, 35/140, при расчётах получается 1/4, 1·(−4)+17·1 = 1, и вы должны вывести (1·(−4)) mod 17 = 13. То есть: независимо от того, насколько сократимая дробь у вас получилась, вы получите один и тот же результат. Тут надо уточнить: там, где возможен отрицательный числитель, нужен не обычный % из Си++, а (a % Z; если получилось отрицательное — добавь Z).

    Ну а арифметических переполнений просто не допускайте, Z = 109 + 7 позволяет умножать в типе long long и не уходить в переполнение.

    UPD. То, что Z — простое, даёт несколько выгод. Часто результат бывает круглый, и простота требует честно считать остаток, а не угадывать. Ну и побочек меньше.
    Ответ написан
    3 комментария
  • Задача по олимпиаде?

    @Mercury13
    Программист на «си с крестами» и не только
    ОПРЕДЕЛЕНИЕ. Беспорядок — а) чёрный блин внизу; б) белый блин на чёрном, чёрный на белом.

    ТЕОРЕМА. Переворот исправляет не более одного беспорядка.
    ДОКАЗАТЕЛЬСТВО. Ни в переворачиваемой стопке, ни в оставшейся как был беспорядок, так и остаётся. У нас есть шанс исправить один беспорядок — тот, в который мы залезли лопатой.

    СЛЕДСТВИЕ. Оценка снизу — количество беспорядков.

    ТЕОРЕМА. Эта граница достижима.
    БАЗА ИНДУКЦИИ. У нас 0 беспорядков. Все блины белые — реально нужно 0 ходов.
    ШАГ ИНДУКЦИИ. Доказано, что граница достижима для 0…N−1 беспорядков. Пусть теперь беспорядков N.
    Если количество беспорядков нечётно, вверху будет чёрный блин. Перевернём всю стопку, кроме нижних белых блинов. Теряем одним ходом один беспорядок, а для N−1 граница достижима.
    Если количество беспорядков чётно, вверху белый блин. Поскольку беспорядков не 0, белые блины лежат на чёрных. Перевернём белую группу (теряем один беспорядок) и получаем вверху чёрный блин. Теряем одним ходом один беспорядок, а для N−1 граница достижима.

    АЛГОРИТМ. Подсчитать количество беспорядков в стопке, вывести его. O(N).
    Ответ написан
    Комментировать
  • Как называется этот алгоритм сортировки?

    @Mercury13
    Программист на «си с крестами» и не только
    Я это называю «сортировка в три строки». А так это сильно упрощённый алгоритм сортировки выбором.
    Ответ написан
    Комментировать