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

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

    Она NP-полная - тут нет быстрых и простых решений. В общем случае, возможно только решение полным перебором за N*3^N. Что-то вроде того, что предложил Alexandroppolus, только там вообще не рассматривается случай, что текущее число просто пропускается. Еще можно делать это же без рекурсии на основе битовых масок.

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

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

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

    Так, для генерации всех перестановок "abc", сначала рекурсивно будет получен массив {"bc", "cb"}, потом для каждого его элемента в ответ будет добавлена перестановка с "a" вставленным в позицию 0, 1 и 2: "abc", "bac", "bca" для первого элемента, и "acb", "cab" и "cba" для второго.

    Или вам не понятно, что делают reduce, slice, substring, concat, join?
    Ответ написан
    Комментировать
  • Какой алгоритм использовать для нахождение уравнения поверхности по 3 точками?

    wataru
    @wataru Куратор тега Математика
    Разработчик на С++, экс-олимпиадник.
    Пусть точка p=(x,y,z) принадлежит плоскости. Пусть 3 точки - p1, p2, p3.

    Тогда вектор (p-p1) должен раскладываться на вектора p2-p1 и p3-p1.

    Т.е. определитель матрицы 3x3 из этих трех векторов должен быть нулевым.

    det {{x-p1x, p2x-p1x, p3x-p1x},
     {y-p1y, p2y-p1y, p3y-p1y},
     {z-p1z, p2z-p1z, p3z-p1z}} = 0


    Раскрываете определитель по первому столбцу и получаете
    A = det({{p2y-p1y, p3y-p1y}, {p2z-p1z, p3z-p1z}})
    И т.д.
    D = -p1x*A-p1y*B-p1z*C
    Ответ написан
  • Какой алгоритм вычисления кратности чисел более эффективен?

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

    Если бы были нужны только числа делящееся на 3, то их сумма - f(n, 3)=3*floor(n/3)(floor(n/3)+1)/2. Эта формула получается вынесением 3 за скобки в сумме и дальше применением формулы армфметической прогрессии.

    Чтобы взять сумму делящихся на 3 или 5 надо взять сумму делящихся на 3, прибавить сумму делящихся на 5 и вычесть сумму делящихся на 15. Потому что делящиеся на 15 были подсчитанны 2 раза в первых слагаемых. Т.е. ответ - f(n,3)+f(n,5)-f(n,15)
    Ответ написан
    Комментировать
  • С чего начать изучение алгоритмов?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Почитайте Кнут "искусство программирования" а также Кормен "алгоритмы: построение и анализ".
    Ответ написан
    Комментировать
  • Объявлять переменные внутри или перед циклом?

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

    wataru
    @wataru Куратор тега Математика
    Разработчик на С++, экс-олимпиадник.
    Координаты центра ромба {x,y} - {130/2*(x-y), 84/2*(x+y)}

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

    Далее надо найти координаты нескольких прямых и можно вывести формулу.

    Второй вариант - через геометрию векторов (это линейная алгебра, или еще нет - как это в школе-то называется вообще?). Нарисуйте вектор из ромба {0,0} в ромбы {1,0} и {0,1}. Ясно, что ромб с координатами {x,y} можно получить сложив x раз первый вектор и y раз второй. Подставляя координаты получите ту же формулу.
    Ответ написан
    Комментировать
  • Как перемешать массив в псевдослучайной последовательности?

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

    Или можно сортировать хеши, полученные из id тега и id статьи. Например, можно подсчитать tag_id*article_id % n.
    Ответ написан
  • Как найти самую ближайшую точку из массива?

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

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

    Потом пройдитесь по массиву, поддерживая счетчик открытых интервалов. Встретили "from" - увеличили счетчик. встретили "to" - уменьшили.

    Если изменили счетчик с 0 на 1, то в текущей дате начало отрезка в ответе. Если изменили с 1 на 0, то тут конец.

    Наверно, надо будет еще отрезки разбить по месяцам потом.

    Еще надо разобраться с тем, когда даты совпадают. Если в одну и ту же дату есть to и from - это же должно считаться одним отрезком? Тогда при сортировке ставьте "from" перед "to" на одну и ту же дату (В сравнении при равенстве дат сравнивайте еще и тип события).
    Ответ написан
    Комментировать
  • Как реализовать алгоритм Джарвиса для выпуклых оболочек?

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

    Если вы будете игнорировать точки уже на выпуклой оболочке, то все оставшиеся точки будут лежать в одной полуплоскости относительно данной. А дальше надо выбирать точку, вектор на которую правее. А если вектора коллиниарны - то ближайшую (или самую далекую, если точки на границе выпуклой оболочки вы хотите пропустить.

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

    Вот набросок кода на C++, думайте, что это псевдокод.

    vector<int> ConvexHull(vector<double> x, vector<double> y) {
      int first = ...; // Тут поиск самой нижней-левой точки.
      const int n = x.size();
      int cur = first;
      vector<int> ans{first};
      // Текущий вектор стороны может идти вправо от самой нижней точки.
      double side_x = 1;
      double side_y = 0;
      while (true) { 
        int bsti = -1;
        // Вектор на лучшую точку.
        double bst_x = 0;
        double bst_y = 0;
        // Расстояние до нее.
        double bst_dist = 0;
        for (i = 0; i < n; ++i) {
          if (i == cur) continue;
          // Вектор на текущую точку.
          double cur_x = x[i] - x[cur];
          double cur_y = y[i] - y[cur];
          // Отсекаем точки назад вдоль оболочки на той же стороне.
          // Можно заменить пометкой в bool in_hull[],
          // которая ставится при добавлении точки в ответ (ans).
          if (side_x*cur_y-side_y*cur_x == 0 && side_x*cur_x+side_y*cur_y < 0) continue;
          double vec = bst_x*cur_y-bst_y*cur_x;
          double dist = cur_x*cur_x+cur_y*cur_y;
          // Берем точку, если она правее текущего кандидата. Или на той же прямой, но ближе.
          if (bsti == -1 || vec < 0 || (vec == 0 && dist < bst_dist)) {
            bsti = i;
            bst_dist = dist;
            bst_x = cur_x;
            bst_y = cur_y;
          } 
        }
        // Сделали полный оборот.
        if (bsti == first) break;
        side_x = bst_x;
        side_y = bst_y;
        and.push_back(bsti);
        cur = bsti;
      }
      return ans;
    }
    Ответ написан
    Комментировать
  • Какой проект сделать с применением графов на js?

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

    Ну, или построение остовного дерева среди заданных точек (в графе есть все ребра. Длины - длины отрезков между точками).
    Ответ написан
    Комментировать
  • JavaScript - как проверить, есть ли в объекте циклические ссылки?

    wataru
    @wataru
    Разработчик на С++, экс-олимпиадник.
    Поиск в глубину.

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

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

    Подсказка: тут отлично зайдет цикл do ... while. Одна переменная должна указывать, кто из людей сейчас активный. Вы должны дописать к ответу его букву и перейти к другому человеку взяв соответствующий элемент из массива A. Цикл должен работать, пока вы не вернетесь к первому человеку. Само решение будет буквально 3 строки, если не считать скобки.
    Ответ написан
    Комментировать
  • Как усовершенствовать алгоритм для уравнения Диофанта?

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

    Там по вашей ссылке в задаче есть подсказка: уравнение можно переписать в виде (x-2y)(x+2y)=n

    Отсюда получается решение: Перебирайте все делители n, не превосходащие корень. Пусть делитель d, тогда второй множитель будет n/d.

    Осталось решить систему линейных уравнений:

    x-2y=d
    x+2y=n/d


    Решается в уме - x=(d+n/d)/2, y=(n/d-d)/4

    Отслось только учесть диофантовость уравнения - ответ должен быть неотрицательные целые числа. Значит, надо чтобы оба делителя d, n/d давали одинаковый остаток от деления на 4 и 2. Ну и d<=n/d, но это учтется перебором делителя до корня.

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

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

    Во первых, тут есть неоднозначность. Может быть так что теги A,B,C попарно несовместимы, но заодно попарно несовместимы теги A,D,E - куда относить тег A, в какую группу?

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

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

    Еще есть Алгоритм Брона — Кербоша. Он перебирает все максимальные клики.
    Ответ написан
  • Алгоритм работает не правильно?

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

    Вы же как-то пытаетесь реализовать это только лишь с переменной mid. Если надо идти влево, то вы делите mid пополам, как будто бы текущий отрезок от начала массива (Но это не всегда так: после первого же шага вправо начало массива будет уже выкинуто из расмотрения), Потом, при переходе вправо, у вас какой-то бред написан.
    Math.floor((arr.length - mid) / 2) - это что вообще должно делать? Если mid=9, length = 10, вы вообще уйдете в начало массива, хотя должны идти вправо. Если вы хотели взять середину между mid и length, то там должен стоять "+" внутри.

    Но так все-равно не получится сделать. Заведите 2 переменные l и r, как во всех реализациях бинпоиска, считайте mid как середину отрезка, и при выбрасывании одной из половин просто переписывайте l или r на mid+1 или mid-1 (потому что сам mid элемет вы уже рассмотрели и он точно не нужен).
    Ответ написан
  • Какова сложность алгоритмов (Big(O)) встроенных JS методов?

    wataru
    @wataru
    Разработчик на С++, экс-олимпиадник.
    Похоже документация не указывает сложность методов. Видимо, никто не ожидает от js кода производительности =)

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

    Возможно, можно нагуглить что-то по конкретным методам.

    По описанию метода concat, он возвращает новую строку не меняя аргументы. Поэтому, скорее всего, он работает за линейную сложность от общей длины операндов. Вряд ли там используется rope.
    Ответ написан
    2 комментария
  • Самая быстрая реализация алгоритма Дейкстры на javascript?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Попробуйте переписать с массивами фиксированной длины. Во всех реализациях по вашим ссылкам вершины нумеруются строками и куча массивов типа distance и visited на самом деле являются словарями, или как это в js называется. Это работает сильно медленнее тупого массива, пронумерованного от 0 до n.

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

    И уже на нем гоняйте дейкстру. Должно по карйней мере в пару раз ускорится. А то и во все 10.
    Ответ написан