Ответы пользователя по тегу Алгоритмы
  • Задача по олимпиаде?

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

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

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

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

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

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

    @Mercury13
    Программист на «си с крестами» и не только
    ВАРИАНТ 1. Расстояние приоритетнее кол-ва заправок.

    Моё решение — в каждой вершине хранить не просто цифру пройденного расстояния, а список: «расстояние/запас топлива/предыдущая вершина». И расстояние, и топливо не убывают.

    С этими списками можно делать такие операции:

    1. Добавить расстояние + израсходовать топливо. Для каждого элемента списка расстояние′ = расстояние + x, топливо′ = топливо − y. Если получается нехватка топлива — что ж, не повезло, этого элемента в списке не будет.
    2. Добавить расстояние + израсходовать топливо + заправиться. Аналогично, но оставляем один элемент — соответствующий наименьшему расстоянию, где хватает топлива. расстояние′ = расстояние + x, топливо′ = полный бак.
    3. Добавить очередной элемент в список. Тогда удаляем из списка те элементы, где расстояние не меньше, а запас топлива не больше.

    После этого на оптимальном маршруте проводим оптимизацию заправок.

    Если граф такой, что бывает много «ничьих» по расстоянию, приходится эти ничьи разруливать.
    1. Если есть несколько равноценных маршрутов — храним их ВСЕ.
    2. Например, можно заполучить все такие маршруты, и на каждом провести оптимизацию заправок.

    Можно также вместо расстояния хранить список «расстояние, кол-во заправок» с лексикографическим порядком на ней и другой операцией «прибавить+заправиться».

    ВАРИАНТ 2. Кол-во заправок приоритетнее расстояния.

    Аналогично первому, только роль расстояния играет пара «кол-во заправок, расстояние» с лексикографическим порядком на ней.
    Ответ написан
  • Как определять сложность алгоритма?

    @Mercury13
    Программист на «си с крестами» и не только
    Начнём с того, что такое символы Ландау (не того, немца Эдмунда Ландау) O(f(n)) и o(f(n)) при n→∞.
    g(n) = O(f(n)), если при достаточном n g(n)≤cf(n).
    g(n) = O(f(n)), если g(n)/f(n) → 0 при стремлении n→∞.
    Таким образом…
    • Символы Ландау отражают изменение чего-то (времени, памяти и т.д.) при n→∞.
    • Если, например, два цикла друг в друге и каждый по n — пишем O(n²). Например, для умножения матриц n×n:
    для i = 1…n
      для j = 1…n
        s = 0
        для k = 1…n
          s += a[i,k]·b[k,j]
        c[i,j] = s

    Тут три вложенных друг вы друга цикла по n — так что сразу же пишем O(n³).
    • Если g(n) = O(n), то g(n) = O(n²), потому мы не грешим против истины. Но если вдруг оказалось, что внутренний цикл — это извлечение из очереди и через эту самую очередь пройдут, например, 2n событий — внешний цикл выполняется O(n) раз и внутренний O(n) раз; оценка алгоритма сразу же превращается в O(n).
    • Константы мы, разумеется, выкидываем: и 2n², и 200n² = O(n²). Также выкидываем те части, чей порядок меньше, чем самый крупный: n²+n log n = O(n²). Кстати, потому мы и не пишем основание логарифма: логарифмы разных оснований отличаются множителем.
    • Но иногда константы важны. Скоростные методы умножения матриц имеют насколько большую константу при n2,81, что реально они начинают иметь смысл где-то со 100×100 (а то и крупнее). По той же причине живёт двоичный алгоритм поиска подстроки — он имеет крайне низкую константу при n² и ещё парочку полезных свойств.
    Ответ написан
  • Как описать неравномерное движение по кругу в виде функции?

    @Mercury13
    Программист на «си с крестами» и не только
    Нужно взять интеграл от функции c: C(t) = ∫c(t)dt,
    и тогда x = cos(Ct), y = sin(Ct).

    Если же функция настолько страшна, что интеграла не взять — тогда придётся решить дифур C'(t) = c(t,x,y).
    Пускай даже самым простым способом C(t+h) := C(t) + hc(t,x,y). Есть и более сложные способы, гуглите «методы Рунге-Кутты».
    Ответ написан
  • Как реализовать алгоритм движения по спирали?

    @Mercury13
    Программист на «си с крестами» и не только
    Я бы сделал примерно такую систему уравнений.

    r = sqrt(t)
    phi = a·r

    t — параметр, условное «время»; phi — полярный угол, r — длина радиус-вектора.
    Ну и, соотвественно, x = r cos phi, y = r sin phi.

    В общем, радиус (ну или угол) должен увеличиваться со скоростью квадратного корня.

    В этом деле есть физический смысл — это решение дифура r′(t)=1/r. Только двоечку и константу интегрирования упустил, ибо они нам как бы не нужны. Метод не точный, но если посмотреть на длину дуги спирали, там самый большой член квадратичный.

    Если нужен СОВСЕМ стабильный зазор (например, расположить по спирали какие-то кружочки), у меня есть рекуррентный алгоритм.
    Как написать алгоритм спирали?
    Ответ написан
  • Какая сложность алгоритма (относительно n)?

    @Mercury13
    Программист на «си с крестами» и не только
    O(n²), разумеется.
    Первый цикл выполняется O(n) раз, и второй O(n). Так что O(n²).
    Если быть точнее, те итерации, которые выполнятся,— это трапеция на квадрате n×n, никакого тебе O(n), O(n log n) и подобного не будет.
    Кстати, запись O(n/2) и O(n²/2) не имеет особого смысла — само определение символов Ландау говорит, что разница в константу не играет роли. По той же причине пишут O(n log n), не указывая, по какому основанию логарифм.

    UPD2. Запись O(n²) означает: «не превышает cn² при стремлении n→∞». Так что всё, что O(n), одновременно и O(n²). И «никакого тебе O(n)» означает, что оценку n² мы улучшить не можем.
    Ответ написан
  • Hash талица это асоциативный массив индексов и адрессов в памяти?

    @Mercury13
    Программист на «си с крестами» и не только
    Производительность хэш-таблиц — O(1) в среднем. Усреднённое по всем возможным наборам данных, если хэш-функция хорошо перемешивает.

    Хэш-таблица действует так. Допустим, у нас выпало значение хэш-функции 1234 и у нас в хэш-таблице 100 гнёзд. Тогда наш элемент где-то в гнезде 34. Когда расширим таблицу до 200 гнёзд, элемент останется в гнезде 34, а когда расширим до 1000 — он переедет в гнездо 234.

    Как разрешаются коллизии (два элемента в одном гнезде) — зависит от реализации: например, в гнезде могут быть связанные списки элементов.

    Для словарей, если тот строится раз и до конца своей (не)долгой жизни, можно применить и другой способ, совершенно неубиенный и дешёвый по памяти. Взять массив, построить и отсортировать. Бинарный поиск — O(log n).
    Ответ написан
  • Как работает метод кодирования 4B3T?

    @Mercury13
    Программист на «си с крестами» и не только
    Начинаем с какой-нибудь суммы, например, 2.
    биты 0000, сумма 2 — по таблице 0−0, от суммы отнимаем 1, получается 1.
    Приходят снова биты 0000, сумма 1 — по таблице уже +0+, к сумме прибавляем 2, получается 3.
    Вот так мы балансируем средний ток через канал связи на уровне нуля.
    Ответ написан
  • Как составить список пути используя алгоритм BFS?

    @Mercury13
    Программист на «си с крестами» и не только
    Вместо
    boolean[][] visited = new boolean[ROW][COL];

    надо сделать такое:
    static final byte DIR_UNKNOWN = 0;
    static final byte DIR_UP = 1;
    ...
    
    byte[][] bestDirection = new boolean[ROW][COL];  // изначально заполнено DIR_UNKNOWN


    for (int dir = DIR_UP; dir <= DIR_RIGHT; ++dir) {
      ...
      bestDirection[row][col] = dir;
    }

    Добравшись до финиша, делаем обратный ход. А именно: определяем, какой bestDirection у финиша, и если он, например, DIR_UP — смещаемся на 1 вниз. И так далее, пока не доберёмся до старта.

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

    @Mercury13 Куратор тега C++
    Программист на «си с крестами» и не только
    Я бы работал по такой формуле:

    result = ((original / max)1 / gamma) · 255

    Original — это полученное алгоритмом Ву значение (float или хотя бы short!)
    max — максимально возможное значение original. Для short, например, это 65535.
    gamma — традиционно 2,2.
    Ответ написан
  • Можно ли число представить в виде float?

    @Mercury13 Куратор тега C++
    Программист на «си с крестами» и не только
    Float содержит 23 бита мантиссы и неявную единицу. Порядок float запредельный и даже qword не упрётся в него.
    Это значит: всё, что дальше 23 бит от верхней единицы, должно быть нулём.

    bool isPreciseFloat(unsigned long long n)
    {
      // Простейшая проверка: стираем нижние 24 бита
      // Если в них вписываемся — ДА.
      unsigned long long n1 = n & ~((1ULL << 24) - 1);
      if (n1 == 0)
        return true;
    
      // Получаем верхнюю единицу
      // (можно также двоичным поиском, но я этого с листа не напишу)
      while (true) {
        unsigned long long n2 = n1 & (n1 - 1);
        if (n2 == 0)
          break;
        n1 = n2;
      }
    
      // Получаем маску всего, что ниже 23 бит от верхнего бита.
      n1 >>= 23;
      --n1;
    
      // Проверяем по маске
      return (n & n1) == 0;
    }


    Писал «с листа», могут быть ошибки.
    Ответ написан
  • Как отсортировать массив с зависимостями элементов друг от друга?

    @Mercury13
    Программист на «си с крестами» и не только
    Это так называемая «топологическая сортировка». Делается через последовательный поиск в глубину, начиная со всех возможных элементов.

    алг recurse(поссылке x : элемент, поссылке результат : список)
      если x.метка = чёрный
        возврат
      если x.метка = серый
        стоп ("найдена циклическая зависимость")
      x.метка := серый
      для всех y : зависимых от x
        recurse(y)
      x.метка := чёрный
      результат.добавить(x)
    
    алг main()
      для всех x : массив
        x.метка := белый
      result := []
      для всех x : массив
        recurse(x, result)


    Вкратце: проводим стандартный поиск в глубину, начиная со всех элементов, и при выходе вносим элемент в список.
    Ответ написан
  • Почему n^3 работает быстрей чем 2^n?

    @Mercury13
    Программист на «си с крестами» и не только
    Одно из двух.
    А. O(n³) и O(2n) — сложность каких-то алгоритмов.

    Читайте определение символов Ландау, и будет всё понятно.
    n³ = o(2n) при n→∞, что означает:

    lim{n→∞} n³ / 2n = 0.

    Что означает: при безграничном повышении n алгоритм, работающий за n³, будет иметь всё большее и большее преимущество перед конкурентом.

    Б. n³ и 2n — функции, которые нам надо вычислить.

    Сложность первой O(1) (всегда два умножения), сложность второй в общем случае — O(log n) (из-за того, что логарифмы от разных оснований отличаются на константу, а константу символы Ландау не учитывают, основание логарифма не пишут).

    UPD. Что значит «в общем случае»? Оценку могут увеличить различные второстепенные алгоритмы вроде выделения памяти и преобразования в десятичный вид, и уменьшить — то, что 2n можно вычислть сдвигом. Не забудьте, что сложность алгоритмов определяется при n→∞.
    Ответ написан
  • Как сформулировать алгоритм для визуального редактирования запросов?

    @Mercury13 Автор вопроса
    Программист на «си с крестами» и не только
    С вопросом 3 оказалось всё одновременно просто и сложно. Дырка — это НЕ тождественный TRUE, это нечто нейтральное к операциям до или после (что приоритетнее). Если OR — внешняя операция, AND — приоритетная, TRUE/FALSE — соотв. нейтральный элемент, то…
    A OR (B AND TRUE) OR C = A OR B OR C, то есть AND уходит
    (A AND B) OR (TRUE AND C) = (A AND B) OR C, то есть OR занимает место AND.
    Так что действительно получается наименее приоритетный из () AND () и AND.

    С вопросом 1 так пока и есть.

    С вопросом 2 задача оказалась похожа на алгоритм сортировочной станции. С одной стороны, у нас нет ни скобок, ни префиксных/постфиксных функций, ни правоассоциативных операций.

    С другой — для каждого элемента стека мы держим op, firstIndex и lastIndex (индексы начала/конца операнда).
    Для первого элемента кидаем (⌀, 1, 1). Или (⌀, 0, 0), если индексы с нуля.
    Для второго (AND, 2, 2).
    Когда попадается третий (OR, 3, 3), срабатывает условие, и мы делаем операцию «сброс AND», состоящую из трё1х вещей:
    1. Для первого lastIndex в случае TRUE делаем переход на второе firstIndex.
    2. Где-то записываем: у первого lastIndex переход в случае FALSE будет таким же, как и у второго lastIndex.
    3. Объединяем эти два элемента, присвоив второй lastIndex первому элементу.
    Ну и добавляем наш (OR, 3, 3) в стек — это делается всегда, независимо от того, сколько раз сработало условие сброса.
    Как сбросить OR — думаю, понятно.
    Таким образом, теперь наш стек будет такой: (⌀, 1, 2) (OR, 3, 3).
    Наш план: (+2 −?) (+? −?) …
    Наш список аналогов: (1, 2, FALSE)

    Четвёртый элемент уйдёт в стек, пятый вызовет сразу два сброса.
    Стек (⌀, 1, 4) (OR, 5, 5).
    План: (+2 −?) (+? −3) (+4 −?) (+? −?)…
    Наш список аналогов: (1, 2, FALSE), (3, 4, FALSE), (2, 4, TRUE)

    Когда список кончится, проводим операцию сброса, пока в стеке не останется (⌀, 1, 8), а затем заполним список аналогов с конца.
    Если вопросительный знак всё-таки остался — это будет +TRUE или −FALSE.
    Ответ написан
  • Что выполняют эти функции в коде?

    @Mercury13
    Программист на «си с крестами» и не только
    1. Найти «в лоб» НОД и похѣрить его.
    2. Найти «в лоб» НОК и отправить его туда же.
    Повторяю, обе функции крайне неэффективны, а их результат идёт в никуда. Как только управление пересечёт точку с запятой, переменная исчезнет.
    Ответ написан
  • Как сравнить точность аналитического алгоритма и его программной реализации?

    @Mercury13
    Программист на «си с крестами» и не только
    Есть вычитание близких чисел? Какие-нибудь циклы вроде СЛАУ больших порядков и решения дифуров? Знакопеременные ряды? Если нет, можно писать, что вклад машинной арифметики в точность алгоритма незначителен.
    А если есть, нужно исследовать, кто и как может многократно усилить ошибки округления.
    Ради эксперимента можно также сравнить результаты во float и double.

    Пример алгоритма, который аналитически устойчив, а вычислительно — нет: e−x «в лоб» при достаточно больших x. Связан он с тем самым вычитанием близких чисел: промежуточные члены ряды могут быть достаточно большие, а в результате выходит 0,0…01.

    UPD. Вот такую книжку нашёл: info.alnam.ru/book_clm.php?id=26
    Ответ написан
  • Как называется такая задача?

    @Mercury13
    Программист на «си с крестами» и не только
    Если считать, что любую передачу можно смотреть только целиком — это будет задача о заявках (=activity-selection problem).
    Решается жадным алгоритмом в таком виде. Берутся самые приоритетные передачи и решается классическая задача о заявках: берём ту, которая кончается раньше всех, затем ту, которая кончается раньше всех и не противоречит имеющейся… В «окна» тем же алгоритмом вставляют менее приоритетные, и т.д.

    Если считать, что можно бросать недосмотренные передачи — всё просто. При наступлении более приоритетной передачи переключаемся на неё.
    Ответ написан
  • Почему не совпадает сложность алгоритма?

    @Mercury13
    Программист на «си с крестами» и не только
    Это так называемая асимптотическая сложность — сложность при n→∞.

    Что никто не упомянул — так называемые символы Ландау.
    a(n) = o(b(n)), (читается «о малое», «меньшего порядка чем»), если lim{n→∞}a/b = 0
    a(n) = O(b(n)), (читается «о большое», «не большего порядка чем»), если a/b ограничено сверху (для дискретного n этого хватит, для непрерывного надо добавить «для какого-то n>N»).

    Два символа Дональда Кнута дополняют символы Ландау.
    a(n) = Ω(b(n)), если b(n) = O(a(n)). «Не меньшего порядка чем»
    a(n) = Θ(b(n)), если a(n) = O(b(n)) и b(n) = O(a(n)). «Такого же порядка».

    Ну а дальше идут простые пределы.
    • axn + bxn−1 + … = O(cxk + dxk−1 + …), если n ≤ k;
    • те же два многочлена o(·), если n < k.
    • те же два многочлена Θ(·), если n = k.
    Константа не важна: во-первых, при n→∞ меньшая сложность рано или поздно перевесит меньшую константу. Во-вторых, особенности реализации того или иного алгоритма на том или ином компиляторе/железе (больше/меньше команд, лучше/хуже с кэшем) эту константу могут варьировать в широких пределах;

    А значит, многочлен n(n−1)/2 = n²/2 − n/2 = Θ(n²).

    Да, и ещё: вы спутали асимптотический порядок самогó многочлена и асимптотическую сложность его вычисления. Первое, как я уже сказал, n². Сложность вычисления в лоб — n+const = O(n). А «не в лоб» — «за константу» , O(1).
    Ответ написан
  • Как изменить систему счисления из 0-f в 0-z-Z?

    @Mercury13
    Программист на «си с крестами» и не только
    Скорее всего, какой-то вариант BASE64.
    Ответ написан