Ответы пользователя по тегу Алгоритмы
  • Для кого операция добавления элемента в середину медленнее — для List или для LinkedList?

    @Mercury13
    Программист на «си с крестами» и не только
    Если нужно искать точку, куда добавить (в LinkedList переместить итератор, в List переместить итератор ИЛИ отыскать индекс) — медленнее LinkedList из-за вопросов с кэшем.
    Если точка уже имеется и она в середине — медленнее List, просто из-за асимптотической сложности.
    Ответ написан
    3 комментария
  • Как решить задачу "Шестерки" с меньшими затратами памяти?

    @Mercury13
    Программист на «си с крестами» и не только
    Шаг 1. Что собой представляет 66666·6?
     ₃₃₃₃
     66666
    ×    6
    ------
    399996

    Таким образом, получается N+1 цифра: 3, N−1 девятка, и 6.

    Шаг 2. Что собой представляет 66666²?
         66666
        ×66666
    ----------
        399996
       399996
      399996
     399996
    399996
    ----------
    4444355556

    (Простите уж, был обломИЩЕ, так что вычислил на калькуляторе и без цифр переноса.)

    Могут быть вопросы, если очередная сумма перескочит за 100 и перенос будет двузначным — но нет, тут всё в порядке. Посчитаем (при достаточной длине кучи шестёрок):
    Десятая с конца (!) цифра — 9·9 + 6 + 8 [перенос] = 95, перенос 9
    Одиннадцатая — 9·10 + 6 + 9 = 105, перенос 10
    Двенадцатая — 9·11 + 6 + 10 = 115, перенос 11
    Так что без вопросов, всё остаётся как было.

    Дальше как-то сможете своими силами?
    Ответ написан
    Комментировать
  • Scratch задание Алгоритмика, как решить?

    @Mercury13
    Программист на «си с крестами» и не только
    Как я понял, робот смотрит вниз.
    Поверни вправо. Подумай, как надо двигаться, чтобы разрушить четыре блока, стоять в 3-й строке, 2-м столбце и смотреть вниз. Повтори четырежды.
    Ответ написан
    Комментировать
  • Будет ли работать бинарный поиск, если в массиве есть пробелы?

    @Mercury13
    Программист на «си с крестами» и не только
    Что такое вообще «пробелы»?
    1. Пробелы в исходном коде: за пределами закавыченных строк это только оформление и в исполнении не участвует. Ну и слова, разумеется, нужно разделять пробелами — как в паскалевском «packed array» или сишном «int main».
    2. Пропуски: не 1,2,3, а 1,4,5. Да, для этого бинарный поиск и предназначен: массив отсортирован, никаких других правил нет, найти или сам элемент, или место, куда вставить его.
    Например, ищем 7: 6 → больше, 13 → меньше, 12 → меньше. Не нашли; если нужно вставить — то после 6-ки.
    Ищем 1: 6 → меньше, 4 → меньше, 1 → попали.
    Ответ написан
    1 комментарий
  • Можете решать эту задачу?

    @Mercury13
    Программист на «си с крестами» и не только
    Изначально:
    1. У корня глубина 0.

    Команда ADD:
    1. вершина.предок = предок
    2. вершина.глубина = предок.глубина + 1

    Команда GET:
    1. Найти ту вершину, что глубже. Если у одной глубина 5, у другой 7 — подняться от второй на 2.
    2. А теперь параллельно и от первой, и от второй вершины поднимаемся вверх на единицу, пока не придём в одну и ту же вершину.

    Если хватит памяти — можно устроить какой-то кэш. Мой вариант — кэшировать предков порядка 1,2,4,8…
    Чтобы подняться от вершины на 30 единиц…
    1. Находим ближайшую степень двойки (16).
    2. Если эта степень есть в кэше — просто берём её.
    3. Иначе находим максимальную имеющуюся степень (например, 4). Заходим в эту вершину и рекурсивно поднимаемся от неё на 4, потом на 8, заполняя наш кэш.
    4. На оставшиеся 14 поднимаемся по тому же алгоритму.

    Чтобы найти общего предка двух вершин — у одной глубина 30, у другой 40.
    1. От той вершины, у которой 40, поднимаемся на 10 единиц. Алгоритм я привёл.
    2. Одинаковые? — тогда понятно.
    3. Имеют общего предка? — тогда понятно.
    4. Иначе поднимаемся на 1, 2, 4, 8, 16 единиц от каждой из них по указанному алгоритму, каждый из этих шагов при наличии кэша даст O(1). Находим последнюю НЕСОВПАДАЮЩУЮ глубину. Для них повторяем алгоритм.

    ВАРИАНТ КЭША ВТОРОЙ. Для вершины глубины 27=11010 кэшировать предков АБСОЛЮТНЫХ (то есть от корня!) глубин 16=1.0000, 24=11.000, 24 :) =110.00, 26=1101.0. Тогда при создании вершины весь кэш достаточно быстро строится на основе кэша вершины-предка.

    Чтобы подняться от вершины глубины 27 на расстояние, например, 5, нам нужна абсолютная глубина 27−5=22.
    Есть только 24 → действуем так. Выныриваем туда на 24, но там кэш совершенно негодный → а дальше нас проведёт кэш глубины 23. Так поднимаемся на 1 до 23-й и повторяем алгоритм.

    Чтобы найти общего предка двух вершин (их глубины, скажем, 27 и 42), точно так же уравниваем глубины. Затем поднимаемся до глубин 16, 24, 24, 26…, пока не найдём несовпадение. Идём в эти несовпадающие вершины, проходим от них к предку и повторяем алгоритм.
    Ответ написан
  • Какова будет грамматика для данного языка?

    @Mercury13
    Программист на «си с крестами» и не только
    L → EZUU M ZUUUUF
    M → ZUU M ZUUUU | S
    Для S грамматику вы уже придумали.
    Затем — не буду расписывать, они многословны, но просты — UZ → ZU

    А чтобы превратить Z в 0 и U в единицу, если i,n ∊ N+…
    Сделаем затравку…
    EZ → E0
    Ua → 1a
    cZ → c0
    UF → 1F
    …Уничтожим технические нетерминалы…
    E0 → 0
    1F → 1
    …И проведём волну!
    0Z → 00
    U1 → 11

    Вроде так.
    (Z = zero, U = unit)
    Ответ написан
    Комментировать
  • Как разбить числа по группам так, чтобы в группах находились близкие по значению числа?

    @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, а где бит.
    Ответ написан