Задать вопрос
wataru

Wataru

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

  • Как организовать такое поведение?

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

    Могу лишь дать пару советов по реализации.
    Пишите рекурсивную функцию которой передается оставшиеся не распределенные блюда и список уже готовых наборов (наборы из одного блюда - тоже наборы). Пытайтесь куда-то приспособить первое нераспределенное блюдо.

    Если наборы не большие (скажем, не более четырех типов блюд) и всего блюд в заказе не много, то можно делать в тупую - перебирайте в функции все 2-3 блюда, кроме первого, двумя-тремя вложенными циклами. Потом берете типы этих блюд и смотрите, а есть ли у вас такой набор. Наборы можно хранить как список списков и искать там бинарным поиском или линейно. Или можно завести 4-х мерный массив и дополнить короткие наборы заглушкой вида "" до 4-х блюд. Такой ассоциативный набор для каждой комбинации типов блюд будет хранить есть ли такой набор и сколько он стоит.

    Если же наборы могут быть больше или всего блюд многовато и надо бы побыстрее решать, то делайте следующее:
    Для каждого типа блюд заведите список наборов, в которые такой тип входит.
    В функцию передавайте блюда, сгруппированные по типам, и уже собранные наборы. Потом циклом перебирайте какой тип набора будете собирать с первым блюдом (у вас же есть список всех подходящих наборов) и вызывайте вторую рукурсивную функцию, которой передаются несобранные блюда, уже готовые наборы, какой тип набора собирается, и собранная часть текущего набора. Функция2 будет брать следующий неиспользованный тип в текущем наборе и, если блюда такого типа у вас есть, добавлять в цикле одно такое блюдо к набору и вызываться рекурсивно. Если весь набор собран, то рекурсивно вызывайте первую функцию.
    В первой функции, помимо перебора всех наборов, после цикла, просто берите первое блюдо как само себя.

    Когда первая функция получает пустой набор нераспределенных блюд, готовые наборы сравнивайте на оптимальность с глобальным ответом.
    Ответ написан
    Комментировать
    Комментировать

  • Как превратить процент в такое число?

    wataru
    @wataru
    Разработчик на С++, экс-олимпиадник.
    Нужно строить регрессию.
    Например, сделаейте так:
    Заведите таблицу, где у вас первый столбец - ваши значения. Второй столбец - проценты (p). Третий - константа 1. четвертый - квадрат процентов (p^2). Потом логарифмы (log p), корни разных степеней, обратные (1/p).
    Потом прогоните на этой таблице линейную регрессию методом наименьших квадратов (фактически - решить систему линейных уровнений, например, методом Гаусса), она даст вам коэффициенты перед всеми функциями в аналитической формуле. Если не угадали с функциями, то ошибка будет большая. Фукции с мелкими коэффициентами можно будет отбросить и заменять чем-то другим.
    Возможно стоит добавить логарифмов со здвигом вида c1*log(p+c2), как у Rsa97, но тогда при методе наименьщих квадратов будут не только линейные урванения, придется помучиться аналитически.
    Ответ написан
    1 комментарий
    1 комментарий

  • Фибоначчи: Возможно ли найти порядковый номер последовательности Фибоначчи ( x ), исходя из числа ( y )?

    wataru
    @wataru Куратор тега Математика
    Разработчик на С++, экс-олимпиадник.
    Не школьник, но вроде все просто.
    У вас есть y = B^x/A
    Дано y, отсюда x= log_B(A*y) = ln(A*y) / ln(B).

    Надо будет округлить. Формула может давать сбои на мелких числах.
    Ответ написан
    1 комментарий
    1 комментарий

  • Какие существуют алгоритмы поиска равноудаленных прямоуголиников?

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

    1) найти ближайший сверху (слева/снизу/справа) из тех, которые имеют перекрытие.
    2) повторить операцию, найдя следующий сверху. Расстояние между ними взять за d.
    3) продолжить идти вверх. Если следующий ближайший тоже на расстоянии d - нарисовать промежуток. Если нет, то остановится.
    4) Зная ближайший прямоугольник из пункта 1) и расстояние d - можно его отступить вниз и у вас есть точка примагничивания.

    Можно ускорить алгоритм немного. Сначала за один проход выделите все прямоугольники, которые выше данного, но пересекаются с ним по оси X. Отсортируйте их снизу вверх по нижней границе. Теперь в пунктах 1,2,3 надо рассматривать только один следующий прямоугольник из списка.

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

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

  • Алгоритм переворота строки как реализовать?

    wataru
    @wataru
    Разработчик на С++, экс-олимпиадник.
    В вашем решении надо оставить только один цикл. Лучше его заменить на while. i++ и j-- выплняются каждую итерацию.

    var j, i
 while (i < j;) {
      temp = str[i];
      str[i] = str[j];
      str[j] = temp;
      i++; 
      j--;
    }
  }
    Ответ написан
    Комментировать
    Комментировать

  • Как проверить сбалансированность открывающих и закрывающих символов?

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

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

    Для удобства реализации из второго параметра нужно выделить "открывающие" и "закрывающие" символы. Удобно в массиве из 256 элементов пометить все открывающие как-то (например, -1), Все закрывающие надо пометить номером соответствующего открывающиего символа. Т.е. для второго параметра "()[]". Для всех символов в массиве будет 0, но для '(' и '[' - будет -1. Для ')' будет в массиве хранится '(', а для ']' - '['.

    Тогда, при обработке символа из первой строки, если в массиве для него 0, то просто пропускаем. Если -1 - то кладем в стек. Если что-то другое, то проверяем, что это значение лежит в стеке на вершине.

    Ваше решение по ссылке на работает на тесте "())("
    Ответ написан
    Комментировать
    Комментировать