Задать вопрос
Ответы пользователя по тегу Алгоритмы
  • Как понять в коде сложность алгоритма?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Так или иначе придется считать количество операций. Иногда это просто, когда там тупо вложенные циклы с фиксированным количеством итераций. Иногда придется пораскинуть мозгами. Например, можно понять сколько уровней будет у рекурсивного вызова и как много операций на каждом уровне происходит. Логарифмы обычно вылезают от деления данных пополам. Когда просят сделать что-то быстрее то надо подумать а нельзя ли тут применить какую-то структуру данных. Например, можно ли BST заменить хеш таблицей.
    Ответ написан
    Комментировать
  • В чем логическая ошибка сигсегва?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Проблема в том, что "214" - это строковая константа. Поэтому char *num = "214"; инициализурует указатель num адресом этой константы. Сама эта константа, видимо, лежит в read only памяти. Поэтому когда вы в алгоритме попытаетесь что-то в массив записать, программа упадет.

    Если вы внимательно почитаете вывод компилятора (желательно с ключем "-Wall"), то он вам про это выдаст варнинг:
    main.cpp:54:17: warning: ISO C++ forbids converting a string constant to ‘char*’ [-Wwrite-strings]


    Надо делать так:
    char num[] = "214";

    Ну еще у вас там в коде ошибка с непроставленным где надо +1 у index. Разворачивать надо кусок правее только что увеличенного элемента. А вы разворачиваете вместе с ним. Поэтому ваша программа еще и повиснет.

    Ну и первую перестановку ваш код не выводит.

    И последнее, вместо for (; index != -1;) лучше использовать while (index != -1)
    Ответ написан
    2 комментария
  • Как вернуть первые N максимальных элементов из массива без сортировки массива?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Есть такой алгоритм. Называется quickSelect. Фактически, это обрезанный quickSort, где после выбора ведущего элемента и разбивки массива работа продолжается только в той половине, где находится раздел между первыми K элементами и остальными N-K.

    Пусть у вас N элементов в массиве и надо вернуть K минимальных. Тогда сортировка будет работать за O(N log N), а quickselect за O(N) в среднем*. В худшем случае может быть и квадратичное время работы, но этот случай практически невозможен, если реализация испольует случайные числа для выбора ведущего элемента.

    Если же вы боитесь этого худшего случая, или считаете себя самим невезучим человеком за всю историю человечества (или боитесь, что злой хакер взломает генератор случайных чисел и передаст вашей программе специально составленный массив, чтобы ее подвесить), то есть другой алгоритм, всегда работающий за O(n log k). При маленьких k - может быть даже быстрее первого алгоритма.

    Суть его в том, чтобы в куче (heap aka priority queue) поддерживать пока найденные K минимальных элементов. При этом куча будет на максимум. Сначала туда кладутся первые k элементов массива, а потом каждый следующий вытесняет максимальный элемент в куче, если он его меньше.

    * Вообще говоря, можно заставить quickselect и quicksort работать идеально всегда, если использовать алгоритм Блюма-Флойда-Пратта-Ривеста-Тарьяна, который ищет медиану за O(n). Но на практике этот алгоритм не применятеся, потому что у него такая константа, что там на логарифм хватит и еще на квадрат останется.
    Ответ написан
    2 комментария
  • Как в проходе графа DFS создать массив маршурутов до нужной вершины?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Это вам полный перебор нужен.

    При выходе из функции очищайте пометку visited. При входе добавляйте вершину в массив/стек/список. Там будет храниться пройденный путь. При выходе из функции - убирайте последнюю вершину из пути. Если зашли в конечную вершину - выводите этот стек с вершинами.

    Еще проблемы - visited и массив пути должны быть одни на все рекурсивные вызовы. Или они должны быть глобальными или передавайте их по ссылке рекурсивно.
    Ответ написан
    2 комментария
  • Какие разработчики работают с алгоритмами?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    К сожалению, алгоритмы применяются не очень часто, а во многих областях - практически не применяются. Могу лишь сказать, что чем фундаментальнее проект, тем больше там алгоритмов.

    Например браузер. Лично мне приходилось в хромиуме писать и динамическое программирование и дихотомию и всякие хитрые структуры данных.

    Из вашего списка скорее подходят бакенд и desktop. Еще очень алгоритмоемкая область - разработка игр. Вот там нужно много чего использовать, потому что надо все делать эффективно, иначе игра будет тормозить.

    По поводу второго вопроса, похоже большинство разработчиков алгоритмы презирают. Считают что это не нужно знать вообще и очень ненавидят алгоритмические интервью в ФААНГах и им подражающим.
    Ответ написан
    5 комментариев
  • Как добавить элемент из файла в ветвящееся дерево?

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    Самый простой вариант - поддерживать вектор из указателей на самые правые узлы во всех доступных уровнях.

    Сначала читаете первую строку и создаете из нее корень дерева.

    А потом в цикле читайте строку и считайте, сколько там пробелов. Их должно быть не больше, чем количество доступных уровней (т.е. элементов в векторе).
    Добавляете текущую строку к узлу, который на уровне равном количеству пробелов (-1, потому что индексация с 0). Укорачиваете вектор до этого узла (все с уровенем ниже та вершина, к которой добавили ребенка - уже недоступно). Добавляете в вектор указатель на только что добавленную вершину.

    В вашем примере.

    Прочитали иван, сделали корень дерева. Вектор будет {"иван"} (указатель на вершину-корень дерева).

    Прочитали алексей. 1 проблел - все хорошо, в векторое 1 элемент, значит может быть до 1 пробела. Добавили "алексей" к вершине "иван". Вектор {"иван", "алексей"}

    Прочитали игорь. Вектор стал {"иван", "алексей", "игорь"}.

    Прочитали андрей. 1 пробел. Может быть до трех пробелов, ведь в векторе 3 элемента. Добавили "андрей" к узлу из вектора по индексу 0 (-1 к количеству пробелов). обрезали вектор до длины 1 и добавили туда новую вершину. Вектор стал {"иван", "андрей"}

    И т.д.

    Для добавления вершины создайте новый TreeNode с нужной строкой и push_back в список детей для нужного отца.
    Ответ написан
    Комментировать
  • Задача на codeforces на проходит по времени?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    У вас решение за O(NM), когда как есть решение за O(N+M).

    Вы считаете сумму всех цен каждый раз. Но это делать не обязательно, ведь вам надо найти сумму всех цен, кроме одной. Можно подсчитать сумму всех один раз и потом вычитать из нее лишнюю цену (но надо аккуратно подумать о переполнениях). Или можно воспользоватся префиксными и постфиксными суммами.
    Ответ написан
    2 комментария
  • Как составить алгоритм выбора монет из ящика на Python?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Это задача размена монет. Решается динамическим программированием. Вот статья на вики. Там даже код есть, похоже, на питоне. Правда, оно там только количество монет считает. Чтобы найти и сами монеты, вам надо завести еще один двумерный массив и везде, где считается массив m запоминать, а каким именно действием текущее значение набирается (или взять текущую монету, или пропустить). В конце вам надо будет от позиции m[-1][-1] циклом while выполнять записанные ранее действия (или пропустить текущую монету и уменьшить r на 1, или взять и тогда уменьшить r на ее размер).
    Ответ написан
    Комментировать
  • Как дополнить двумерную матрицу нулями по краям?

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    Сначала каждую строку resize до размера size()+w0+w1. Потом сдвигайте элементы на w0 позиций вправо (цикл надо гнать с конца). Потом заполните пустые места нулями.

    То же самое в самом векторе векторов. Только вместо чисел надо сдвигать вектора на h0 позиций. На пустые места надо будет записывать std::vector(n+w0+w1, 0);

    Edit: А вообще, тут и добавлять в массив ничего не надо. Вы нужный вам ответ можете нулями прямо во время вывода добить.
    Ответ написан
    Комментировать
  • Как ускорить код на Python?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Я предполагаю, что условие вашей задачи такое - дано куча запросов вида <начало отрезка, конец, значение>. Все ячейки в этом отрезке заполняются заданным значением, если они меньше его. Надо найти сумму всех ячеек в конце.

    Тут есть два решения. Первое - через дерево отрезков с отложенным изменением. Само дерево немного странное получается, потому что оно ничего не считает в промежуточных вершинах, а будет только хранить отложенное изменение. Физический смысл отложенного изменения - "все ячейки в этом поддереве должны быть не меньше этого значения". Релаксация (спуск вниз) отложенного изменения происходит так: отложенное изменение в детях заменяется на максимум из того, что там лежит и отложенного значения в родителе. Значение в родителе заменяется на 0. При запросе спускайтесь рекурсивно по дереву, релаксируя изменения, пока текущее поддерево не будет целиком лежать в запросе. Тогда перезаписывайте отложенное значение в текущей вершине, если оно меньше. В конце обработки запросов релаксируйте все вершины сверху вниз и просуммируйте значения в листьях.

    Второе решение - через метод сканирующей прямой может быть проще в реализации из-за наличия встроенных структур данных. Я думаю, в питоне должна быть структура, которая умеет быстро добавлять число, удалять число и брать максимум из всех чисел. В C++ есть std::set или std::priority_queue.
    Для каждого отрезка-запроса создайте два события вида <координата, отрезок открылся/закрылся, значение> (разберитесь, где там +-1 поставить так, чтобы длина отрезка по координатам равнялась количеству покрытых ячеек). Засуньте их все в один массив и отсортируйте по координате. Потом проходитесь слева-на-право. Применяйте текущее событие - или добавляйте число в вашу структуру данных, или удаляйте оттуда. Между текущим и следующим событием по координатам все ячейки покрыты одним и тем же множеством отрезков, поэтому можно их все быстро посчитать, ведь ваша структура умеет брать максимум. Добавляйте к ответу разность координат между текущим и следующим событиями, умноженную на значение максимума из структуры. Все.
    Ответ написан
    Комментировать
  • Как лучше организовать алгоритм подсчета выгоды?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Вам надо формализовать задачу. Аккуратно, с формулами, расписать все типы промокодов, как они действуют и взаимодействуют.

    Если бы все промокоды давали процентную скидку, то можно было бы брать жадно, но эти абсолютные коды все ломают. Тут можно посмотреть не решение задачи о рюкзаке или о размене монет (динамическое программирование), похоже это позволит ускорить решение. Вроде как - перебрали какие процентные коды вы применяете и вот остается у вас сумма X. Вам надо абсолютными кодами набрать максимальное число не больше X.

    А так полный перебор придется хотябы частично делать. Это рекурсивной функцией придется реализовать - гуглите "полный перебор" хоть даже тут.
    Ответ написан
    Комментировать
  • Каким образом можно привести к единой координатной системе траектории движения точек?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Хватит и метода наименьших квадратов.

    Я так понял, что вам надо отслеживать общий сдвиг и поворот так, что бы индивидуальные изменения в точках были минимальны.

    Сначала для каждой точки в прошлом снимке найдите положение в следующем. Можно брать ближайшую точку, если там изменения от кадра к кадру небольшие. Иначе придется городить какой-нибудь градиентный спуск. Если изменение превосходит некоторое пороговое значение - считаете, что точка пропала и не включаете эту пару в рассмотрение.

    Когда для каждой точки вы знаете где ее прошлое и следующее положение, у вас задача найти минимум функции
    sum_i (xp_i-xp'_i)^2+(yp_i-yp'_i)^2, где
    xp' = xn*cosa - yn*sina + dx
    yp' = xn*sina + yn*cosa + dy.

    Тут (xp, yp) - координаты i-ой точки в прошлом кадре, (xn, yn) - координаты в следующем кадре, cosa,sina,dx,dy - неизвестные. Берете производные по dx, dy и a приравниваете к 0. Получаете 3 уравнения с 3 неизвестными. Их двух первых элементарно выразить dx, dy через cosa/sina. Подставив в последнее вы получите уравнение вида cosa^2 A + sina cosa B + sina^2C + D = 0. Можно домножить D на cosa^2+sina^2, потом поделить все на sin^2 и решать квадратное уравнение относительно тангенса. Потом через арктангенс найти решение.

    Если изменения от кадра к кадру могут быть большими, то надо минимизировать чуть чуть другую функцию:

    sum_i min_j ((xp_j-xp'_i)^2+(yp_j-yp'_i)^2) - для каждой точки берем минимум по всем возможным прообразам и это суммируем. Поскольку оно уже не диффиренцируемо, придется использовать какой-то более хитрый метод оптимизации по dx, dy, a.
    Ответ написан
    Комментировать
  • Какой паттерн, как организовать структуру проекта для разных форматов пикселей RGB и YUV?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Я бы посоветовал делать абстракцию не на уровне пикселя, а на уровне картинки. Ибо так можно оптимальнее организовывать расположение пикселей в памяти да и обрабатывать изображение быстрее. Вместо функции, которая для каждого пикселя проверяет, а что там у него брать R или Y, используют функции, которым передается plane - один канал. Что там конкретно R, G, Y, V - обычно не важно. Если вы ищете контур или сглаживаете изображение, то работа идет абсолютно одинаково в каждом канале.

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

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    FillPolygon работает через обход в ширину.

    Сначала одним циклом покрасьте все точки контура.
    Потом берите любую точку внутри полигона, красьте ее и кладите в очередь. Пока очередь не пуста берете точку оттуда, берете 4 или 8 ее соседей и если они не покрашены еще - красите их и кладете в очередь.

    Может быть сложность с выбором самой первой точки внутри полигона. Но тут можно аккуратно пройтись вдоль полигона против часовой стрелки и взять первую непокрашенную точку слева относительно обхода. Тут можно для каждой точки найти вектора на двух соседей по контуру, потом перебрать 4-8 соседних пиксилей и взять тот непокрашенный, вектор на который лежит между двумя векторами вдоль контура.
    Ответ написан
    Комментировать
  • Перебрать все комбинации массивов строк?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Рекурсивная функция должна принимать текущий набор строк и номер следующего массива. Функция циклом перебирает строку из следующего массива, добавляет эту строку к текущему набору и вызывается рекурсивно. После вызова последнюю строку надо из текущего набора удалить. Если в начале функции вы видите, что обработаны уже все массивы - выводите текущий набор в ответ и возвращайтесь из функции.

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

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    if ((matrix[i][j] < minValue[j]) && (isPartOfOutputTree[j] == false))


    Вот тут ошибка. Ведь i - это номер итерации,а совсем не только что включенная в дерево вершина, относительно которой надо сделать релаксацию.
    Ответ написан
  • Как обвести множество точек на карте?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Вот алгоритм выделения граней планарного графа: https://e-maxx.ru/algo/facets

    Сначала вам придется попересекать отрезки друг с другом и получить граф: вершины - точки пересечения и концы отрезков, ребра - куски отрезков. Потом выделяете алгоритмом выше внешнюю и внутренние грани.

    Потом их сглаживаете. Внешнюю грань - наружу, внутренние - внутрь. Тут придется как-то эвристически действовать. Например, берете любую точку на контуре, если две ее соседние достаточно близки, то выкидываете текущую точку. Если внутренняя грань становится достаточно маленькой по площади - выкидываете ее целиком.

    Upd: Дополнение - выбрасывать можно только точки, "вогнутые" внутрь полигона, такие, что их удаление только сделает внешнюю часть больше, а внутреннюю меньше.

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

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Шансы 1:3:3:1. Генерируйте случайное число от 0 до 7. При 0 - выдавайте случайное число < 50. При 1-3 - случайное число от 50 до 74, при 4-6 - выдывайте ответ от 75 до 89, при 7 выдавайте число от 90 до 100.

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

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    Через битовые операции вы ничего не сделаете, потому что у вас, судя по всему, надо найти общие цифры в десятичной системе счисления. Вообще найти десятичные цифры у вещественных чисел - весьма сложная операция.

    Я думаю, вам остается только вывести оба числа в строки в каком-нибудь фиксированном формате и дальше сравнивать посимвольно.
    Ответ написан
  • Как называются алгоритмы, который показывает пошаговые изменения в слове?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Это про теорию графов и кратчайшие пути. Вам надо найти путь в графе из слов, где ребра есть между словами с одним изменением.
    Ответ написан
    5 комментариев