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

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

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

    Другой вариант, через битовые маски, без рекурсии. Перебирайте число от 0 до 2^n-1. Потом смотрите на него, как на битовую маску. Так вы переберете все подмножества из n элементов. Если i-ый бит установлен, то берите i-ое число в сумму. Если сумма совпала с искомой - вы нашли вариант.

    Ну и самый быстрый вариант: с использованием динамического программирования. Как в задаче о рюкзаке вам надо подсчитать F(i,j) - можно ли числами с i-ого по последнее собрать сумму равную j. Потом рекурсивый перебор оптимизируется с этой информацией. Вы текущее число берете или нет и запускаетесь рекурсивно, если оставшимеся числами можно набрать оставшуюся сумму до ответа.

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

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

    Поэтому иногда имеет смысл написать не самый быстрый алгоритм, но зато гораздо более простой. Если он проходит, то зачем кодить больше?

    В вашем алгоритме еще проблема, что не очевидно, почему он работает. Надо аккуратно рассматреть все 6 случев расположения arr[0], arr[1] и numbers[i] и убедиться, что инваринат "2 минмальных числа лежат в arr" поддерживается. Тут легко накосячить, перепутать 0 и 1, не там проверку поставить и все.

    Обычно, когда такой алгортм реализуют, поддерживают более строгий инвариант "минимальное число в arr[0], следующее минимальное число в arr[1]". Тогда проверки чуть чуть упрощаются и за логикой решения следить проще.
    Ответ написан
    1 комментарий
  • Какой алгоритм использовать для нахождения точки?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Вам уже подсказали: Триангуляция по 4 точкам.

    При чем не надо решать систему в общем виде. Если вы возьмете ваши 4 точки как (0,0,0) и (0,0,1), (0,1,0) и (1, 0, 0) то вы уже можете найти координаты искомой точки, не решая даже квадратных уравнений или систем.

    Например, для первых двух точек:
    x^2+y^2+z^2 = d1^2
    x^2+y^2+(z-1)^2 = d2^2


    Вычтите одно уравнение из другого, сократите все сокращаемое, поделите на 2 и в одно арифмитическое действие найдете z.

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

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

    Тут вообще-то ответ - числа фиббоначи. Подумайте, почему.
    Ответ написан
    Комментировать
  • Обход Dom дерева как то относится к дискретной математике?

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

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

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

    Допустим количество работ (N) и количество людей (M) взаимно просты.

    Тогда сгенерируйте M строчек беря людей подряд:
    1, 2, 3
    4, 5, 1
    2, 3, 4
    5, 1, 2
    3, 4, 5

    Тут каждый человек одинаковое количество раз (по одному разу) будет на каждой работе. И дни, когда он будет работать будут максимально равномерно распределены (минимальное расстояние и максимальное между соседними работами будут различаться максимум на 1 и равны floor(N/M) и ceil(N/M)). Это идеальное с точки зрения равенства расписание. Но у него минус - частоты пар работников будут не одинаковыми. 1 гораздо чаще будет работать с 2 и 5, чем с 3 и 4.

    Теперь, если N и M не взяимно просты. Пусть D = GCD(N,M) - наибольший общий делитель.

    Разбейте всех людей на D групп по N'=N/D человек. N' и M взяимно просты, поэтому можно применить алгоритм выше к каждой группе.

    Дальше эти D расписаний надо перемешать. Для максимальной равномерности - сначала взять все первые строки всех расписаний, потом все вторые, и т.д.

    На i-ом месте будет день i / N' из расписания i % N' (если индексация с 0).

    Так, например, решение для 2 работ и 6 людей:

    N' = 3. 2 группы.
    В первой:
    1 2
    3 1
    2 3

    Во второй:
    4 5
    6 4
    5 6

    В итоге:
    1 2
    4 5
    3 1
    6 4
    2 3
    5 6
    Ответ написан
    Комментировать
  • Какова сложность алгоритма?

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

    Решение со стеком будет линейным.
    Ответ написан
    Комментировать
  • На сколько критичен сдвиг в массиве для алгоритмов?

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

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

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

    Когда подберете параметры, функция будет вычислятся кусочно. Сначала найдите к какому отрезку относится текущее время (или тупо циклом или набором if-else, или, если сделаете отрезки одинаковым количеством часов, то можно поделить время на длину отрезка и округлить вниз, чтобы получить номер отрезка). Потом вычислите значение нужного сплайна, что будет просто вычислением полинома второй или третьей степени.

    Ну, или можете просто задать нексолько ключевых значений, и проинтерполировать полиномом лагранжа. Правда тут сложно будет заставить его идти именно как вам хочется. Через точки-то он точно пройдет, но вот между ними может иметь какие-то левые пики и изгибы. Так что придется поэксперементировать. Можно поиграться, например, в wolframalpha.com (введите "interpolating polynomial calculator", потом задайте значения функции в точках и получите и график и формулу. Ссылку дать не могу, qna ссылки на wolfram банит за одно со спамерскими ссылками по ошибке).
    Ответ написан
    Комментировать
  • Как вернуть первые 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 комментария
  • Как написать кастомный findIndex с бинарным поиском?

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

    Второй вариант - функция должна возвращать 1, если первый элемент строго меньше второго.

    Тогда равнество можно сделать так: !f(a,b) && !f(b,a). А второе условие просто заменяется на один вызов функции.
    Ответ написан
    7 комментариев
  • Нужно ли строго проверять if?

    wataru
    @wataru
    Разработчик на С++, экс-олимпиадник.
    А почему не рассматривается третий вариант? Что-нибудь вроде
    if (ToString(exampleVar)[0].length() == 4) alert(1)


    Умышленно писать === true, конечно может быть иногда оправданно в языках без строгой типизации, но в целом это довольно редко оправданная вещь.
    Ответ написан
    Комментировать
  • Фибоначчи без использования BigInt на javascript?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Без BigInt - никак. Числа-то большие получаются. Если нет библиотеки, придется самостоятельно писать длинную арифметику. Просто храните цифры числа в массиве и длину рядом. Вам надо будет только сложение реализовывать, ну это делается столбиком одним циклом. Храните перенос с младших разрядов в переменной. Можно или исходники BigInt поискать, или вот тут посмотреть
    Ответ написан
    Комментировать
  • Как сделать дерево объектов из массива?

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

    Заведите мап объектов, которые будете собирать. Ключи будудт айдишники, а значения - объекты. У объектов заполните uid, parentUID, пустой Map children и пустой список children_list. Так же запомните куда-то id, у которого null отец.

    Потом еще одним проходом по списку всех элементов заполните children_list у всех обхектов в Map из прошлого шага (кладите текущий id в список для parentUID).

    Потом еще одним проходом по всем элементам этого Map соберите дерево: обойдите список детей и в Map children кладите 'id' => объект из внешнего Map'а по данному ключу. После прохода можно children_list удалить.

    Если я правильно понимаю, как работает JS, то у вас будет не копироваться объект а его ссылка. В итоге в Map будут осодержаться вообще все поддеревья ссылыющееся друг на друга. Можно потом вырвать оттуда объект по ключу id корня и Map удалить.
    Ответ написан
    Комментировать
  • Как из массива рандомных натуральных чисел вычислить две равные суммы?

    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)
    Ответ написан
    Комментировать